简要描述HashMap和HashSet的实现原理

HashMap

HashMap基于Hash算法实现的，我们通过put(key,value)存储，get(key)来获取。 当传入key时，HashMap会根据key. hashCode()计算出hash值，根据hash值将value保存在bucket里。当计算出的hash值相同时，我们称之为hash冲突，HashMap的做法是用链表和红黑树存储相同hash值的键值对。当hash冲突的个数比较少时，使用链表否则使用红黑树（当链表元素超过八个，且数组元素超过64时，就会转换成红黑树，当红黑树节点个数小于6时，转换为链表）。 注意：

1. bucket：当系统开始初始化 HashMap 时，系统会创建一个长度为 capacity 的 Entry 数组，这个数组里可以存储元素的位置被称为“桶（bucket）”，每个 bucket 都有其指定索引，系统可以根据其索引快速访问该 bucket 里存储的元素。
2. HashMap中存在两种节点：普通Node（链表）和TreeNode（红黑树）

static class Node<K,V> implements Map.Entry<K,V> {
          
   //链表节点
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
}
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
          
   //红黑树节点
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // 需要在下一次删除时断开链接
        boolean red;
}
//LinkedHashMap.Entry<K,V>的父类是就是HashMap.Node，所以说TreeNode也是一种Node

HashSet

HashSet是基于HashMap实现的，HashSet底层使用HashMap来保存所有元素，因此HashSet的实现比较简单，相关HashSet的操作，基本上都是直接调用底层HashMap的相关方法来完成，HashSet不允许重复的值（使用hashmap的key来存储set）。

hashset部分源码

private transient HashMap<E,Object> map;

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

public boolean add(E e) {
          
   
        return map.put(e, PRESENT)==null;
}