HashMap，HashTable，ConcurrentHashMap面试笔记

• HashMap

HashMap（java8以前）：数组+链表
HashMap数据长度默认是16，每个元素存储链表头节点，通过位运算的方式计算出元素要存放数组的位置，极端的情况：如果添加的元素通过hash散列运算总是得出相同的值及分配到同一个桶中，这样会使得某个桶的链表会变得很长，链表查询需要从头部逐步遍历，因此性能从O(1)变成O(n)。
HashMap（java8以后）：数组+链表+红黑树性能O(n)提高到O(logn)
HashMap是非synchronized，所以HashMap很快。

java8以后的HashMap数据结构：

HashMap源码解析：
Node<k,v>[]由hash值，键key，值value，指向下一个节点next组成。
数组被分为一个个bucket即“桶”，通过hash值决定了这个数据的寻址，hash值相同的键值对以链表的形式来存储，如果链表的大小超过TREEIFY_THRESHOLD（默认8），就会被改成红黑树。当某个桶上面的总数低于UNTREEIFY_THRESHOLD阈值（默认6），红黑树又被转化为链表，以保证更高的性能。
（HashMap是按照lasyLoad的原则，在首次使用时才会被初始化。）

put方法：
1.当HashMap未被初始化时调用resize()方法初始化；
2.对key求hash值，依据hash值计算下标；
3.如果通过hash运算得到的位置没有元素，即未发生碰撞，直接放入桶中；
4.如果计算出的位置已经存在元素，且键和存入进来的一致，则直接替换数组里的元素；
5.否则判断当前位置是否已经是树化了之后的节点，如果已树化尝试存储键值对，如果不是树化则按照链表的方式往链表后面添加元素；
6.若链表的长度超过阈值，且HashMap元素超过最低树化容量，则将链表转化为红黑树，默认最低阈值：THREEIFY_THRSHOLD=8，默认最低树化容量：MIN_THREEIFY_CAPACITY=64；
7.若节点已经存在，则用新值替换旧值；
8.若桶满了（默认容量16x扩容因子0.75），就需要resize（扩容2倍之后重排）。

get方法：
使用键对象的hashcode，通过hash算法找到bucket的位置，之后key.equals()方法找到链表中正确的节点，最终找到值并返回。

HashMap如何减少碰撞：
①扰动函数：使元素位置分配均匀，减少碰撞的几率
②使用final对象，并采用合适的equals()和hashCode()方式

HashMap扩容机制：
使用新的比较大的数组代替现有的比较小的数组。默认负载因子DEFAULT_LOAD_FACTOR是0.75，当一个hashMap填满了75%的bucket时，将会加粗样式去创建原来hashMap大小的两倍的bucket数据来重新调整map的大小，并将原来的对象放入新的bucket数组中，即rehashing。
扩容存在问题：
多线程下，调整大小会存在条件竞争，容易造成死锁。rehashing是一个比较耗时的过程。

• HashTable

①早期java类提供的哈希表的实现
②线程安全：涉及到修改hashTable的方法使用synchronized修饰
③串行化的方式运行的，性能较差

HashMap实现线程安全时使用的Collections.synchronizedMap(hashMap);synchronizedMap同hashTable相同，实现线程安全都是串行的，性能较低，为了实现多线程下的性能提升，引用了ConcurrentHashMap。

思考：
如何优化hashTable？通过锁的细粒度化，将锁拆成多个锁进行优化，将一个锁拆解成多个不会相互制约的锁。

• ConcurrentHashMap：CAS+synchronized使锁更细化

早期的ConcurrentHashMap的实现：通过分段锁Segment来实现，将锁一段一段地去存储，给每一段数据配一把锁及Segment，当一个线程占用一把锁及Segment访问其中一段数据，位于其他Segment的数据也能被其他线程访问，默认会分配16个Segment，所以理论上效率比HashTable提高16倍。

当前的ConcurrentHashMap取消了Segment分段锁，而采用CAS+synchronized而保证并发安全，同时还做了进一步的优化，数据结构和HashMap1.8的结构一样，都是数组+链表+红黑树，synchronized只锁定当前链表或红黑树的首节点，这样只要hash不冲突，就不会产生并发，效率得到提高。

put方法：
1.判断Node[]数组是否初始化，没有则进行初始化操作；
2.通过hash定位数组的索引坐标，是否有Node节点，如果没有则使用CAS进行添加（链表的头节点进行操作），添加失败会进入到下一次循环，继续尝试添加；
3.检查内部是够正在扩容，如果正在扩容，就调用helpTransfer()方法帮助它一块扩容；
4.如果头节点不为空（f!=null），则使用synchronized锁住头节点元素对象（链表、红黑二叉树的头元素）；
4.1如果是Node（链表结构），则执行链表的添加操作
4.2如果是TreeNode（树型结构），则执行树添加操作
5.判断链表的长度已经达到临界值8，当节点数超过这个值需要把链表转化为树结构。

ConcurrentHashMap总结：
比起Segment，锁拆得更细首先使用无所操作CAS插入头节点，如果插入失败，就说明已经有其他线程操作头节点了，那么需要再次循环进行操作。若头节点已经存在则通过synchronized获得头节点的锁进行后续的操作。

HashMap，HashTable，ConcurrentHashMap三者的区别：
1.HashMap线程不安全，数组+链表+红黑树
2.HashTable线程安全，锁住整个对象，数组+链表
3.ConcurrentHashMap线程安全，CAS+同步锁，数组+链表+红黑树
4.HashMap的key，value均可为null，其他两个类不支持。