HashMap的put方法

大体流程：

  1. key通过hash算法与与运算得出数组下标

  2. 如果数组下标位置元素为空，则key和value封装成Entry对象，放入该位置

    JDK1.7是Entry对象，1.8是Node对象

  3. 如果数组下标元素不为空，则需要分情况讨论

如果是JDK1.7， 先判断是否需要扩容，如果需要扩容就先扩容后，如果不需要扩容则生成Entry对象 ，并使用头插法添加到当前位置的链表中。
如果是JDK1.8，则先判断当前位置上的Node的类型，看是红黑树的Node，还是链表Node

  • 如果是红黑树Node，则将 key 和 value封装成一个红黑树节点并添加到红黑树中，在这个过程会判断红黑树中是否存在当前key，如果存在则更新value
  • 如果此位置上的Node对象是链表节点，则将key和value封装成一个链表Node并通过尾插法插入到链表的最后位置去，因为是尾插法，所以需要遍历链表，在遍历链表的过程中会判断是否存在当前key，如果存在则更新value，当遍历完链表后，将新链表Node插入到链表中，插入到链表后，会看当前链表二点节点个数，如果超过了8，则会将该链表转换成红黑树，

  • 将key和value封装位的Node插入到链表或红黑树中后，再判断是否需要进行扩容，如果需要就扩容。

    hashMap在1.8中做了哪些优化？

    数据结构

  • 1.7 采用的数组+单向链表， 1.8采用的是数组+单向链表+红黑树

  • 链表插入节点的方式：1.7采用头插法，1.8采用尾插法

  • hash函数，1.8将hash值高位的（前16位）参与到取模的运算中，使得计算结果的不确定性增强，降低发生哈希碰撞的概率

    扩容优化

    扩容以后，1.7对元素进行rehash算法，计算原来的每个元素在扩容之后的哈希表的位置。1.8借助2倍扩容机制，元素不需要重新计算位置
    1.8 扩容不像1.7那样还要重新计算每个元素的哈希值，而是通过高位运算(e.hash & oldCap)判断元素是否需要移动

    HashMap线程安全的方式

  • 通过Collections.synchronizedMap返回了一个新的map

采用了Synchronized 基于代理模式实现了一个新的SynchronizedMap
缺点：

  • ConcurrentHashMap

采用了NonfairSync CAS确保原子性和互斥性

为什么hashMap扩容的时候是2倍？

  • 1.8 扩容之后，需要重新确定元素位置。 （n-1）& hash
  • 降低hash冲突

    hashMap为什么使用红黑树不用普通的AVL树？

    | 平衡二叉树类型 | 平衡度 | 调整频率 | 适用场景 | | —- | —- | —- | —- | | AVL树 | 高 | 高 | 查询多，增删少 | | 红黑树 | 低 | 低 | 增删频繁 |

AVL树：
一般用平衡因子判断是否平衡并通过旋转来实现平衡，左右子树树高不超过1， 与红黑树相比，AVL是高度平衡的二叉树，平衡条件必须满足所有节点的左右子树高度差不超过1.
红黑树：
是一种弱平衡二叉树，红黑树从根到叶子节点的最长路径不会超过最短路径的2倍。由于是弱平衡，可以看到，在相同节点的情况下，AVL树的高度 <= 红黑树。相对于严格的AVL树来说，它的旋转次数少，所以对于搜索、插入、删除操作较多的情况下，用红黑树。