1、HashMap

HashMap 是存储key，value双列数据的集合。他的底层结构主要是 数组+ 链表+ 红黑树实现的 。

HashMap中hash数组默认大小是16，增加的方式是 old*2。加载因子是0.75，是线程不安全的。

当put一个节点数据时，会根据key进行一个hash操作，也就是说通过将key的hashcode值进行二进制转换得到一个32位的二进制数，然后再将key的hashcode无符号右移16位也得到一个32位的二进制数 ，将这两个32位的二进制数进行异或操作（相同为0不同为1），会得到一个hash值，然后再将得到的hash值与数组的长度进行一个按位与操作（相同为1不同为0） 然后得到数组的下标，如果数组的下标处不存在数据，则直接添加，如果存在数据，会进行hashcode值和equal方法的比较，如果相等则覆盖value，如果不相同的话，则将数据添加链表的后面，当数组的容量占比超过0.75时，会进行扩容，扩容为原来容量的2倍，然后在对里面的值进行hash计算，在填充数据。当数组的长度大于64，并且链表长度超过阀值( TREEIFY THRESHOLD==8)，就把链表转成红黑树，元素长度低于6，就把红黑树转回链表。

当通过key获取元素的时候，也会对key进行hash计算，找到对应数组的索引，然后再通过key是否相等来获取value。

2、LinkedHashMap

大致结构和HashMap相似，只不过LinkedHashMap使用entry继承了hashmap中的node节点，并增加了两个属性，before和after，用来记录每次添加时前一个和后一个引用，在遍历的时候效率更高。

3、hashSet

hashset的底层 就是一个hashMap，当hashset添加一个元素的时候，key就是添加的数据，value是object对象。

4、HashTable

HashTable中hash数组默认大小是11，增加的方式是 old*2+1。加载因子是0.75 。更新数据的方法被synchronized修饰，是线程安全的。

put数据

HashTable通过put方法添加数据时，也会根据key计算hash值，然后在获取存放数据地 数组下标，不过hashtable的hash计算和hashMap的有些区别，hashtable的hash计算是直接获取key的hashcode值，然后在与0x7FFFFFFF进行按位与运算，然后在和数组的长度进行取模运算，得到存放数组的下标。&0x7FFFFFFF的目的是为了将负的hash值转化为正值，因为hash值有可能为负数，而&0x7FFFFFFF后，只有符号外改变，而后面的位都不变。进行扩容的时候也会进行再次hash计算。

5、ConcurrentHashMap

ConCurrentHashMap的目标是实现支持高并发,高吞吐量的线程安全的HashMap。

他的底层结构主要是 ndoe数组+ 链表+ 红黑树实现的 。 利用 CAS + synchronized 来保证并发更新的安全

默认大小是16，加载因子是0.75，是线程安全的。ConcurrentHashMap的键和值不能为空。

当put一个数据时，

1、会根据key计算hash值，然后在获取存放数据地 数组下标，hash值计算的方式是将key的hashcode值进行二进制转换得到一个32位的二进制数，然后再将key的hashcode无符号右移16位也得到一个32位的二进制数 ，将这两个32位的二进制数进行异或操作（相同为0不同为1），会得到一个值，然后这个值在和0x7fffffff进行按位与操作，得到最后的hash值。

2、然后再将得到的hash值与数组的长度进行一个按位与操作（相同为1不同为0） 然后得到数组的下标。

3、将数据插入到该索引位置，如果没有hash冲突就直接以CAS方式插入，

4、如果还在进行扩容操作就先进行扩容，

5、如果存在hash冲突，就加锁来保证线程安全，

​ 这里有两种情况，

• 一种是链表形式就直接遍历到尾端插入，
• 一种是红黑树就按照红黑树结构插入

6、最后一个如果该链表的数量大于阈值8，就要先转换成黑红树的结构。

什么时候会扩容？

如果新增节点之后，所在链表的元素个数达到了阈值 8，并且如果长度n小于阈值MIN_TREEIFY_CAPACITY，默认是64，会进行扩容，数组长度扩大到原来的两倍，对数组中的数据会重新再次进行计算。链表长度达到 8 个或者以上，并且数组长度为 64 以上时只会将链表转为红黑树 。

当get一个元素时

会根据key计算hash值，然后在获取存放数据地 数组下标，如果是首节点符合就返回，如果遇到扩容的时候，会调用标志正在扩容节点ForwardingNode的find方法，查找该节点，匹配就返回。以上都不符合的话，就往下遍历节点，匹配就返回，否则最后就返回null。

​