深度认识HashMap

什么是HashMap？

HashMap可以看成做数组和链表结合组成的复合结构，数组被分为一个个桶（bucket），通过哈希值决定了键值对在这个数组的寻址；哈希值相同的键值对，则以链表形式存储，如果链表大小超过阈值（TREEIFY_THRESHOLD,默认 8），链表就会被改造成树形结构（红黑树）。转化成红黑树这一过程叫做树形化

---

树形化还是扩容？

• 根据哈希表中元素个数确定是扩容还是树形化
  
  • 如果容量MIN_TREEIFY_CAPACITY，只会进行简单的扩容
  • 如果容量大MIN_TREEIFY_CAPACITY ，则会进行树化改造。

为什么要进行树形化？

本质上是个安全问题，因为在元素放置过程中。如果一个对象哈希冲突，都会被放置在同一个桶里面，则会形成一个链表。我们知道链表查询是线性的，会严重影响存取的性能。

什么是哈希冲突？

就是键(key)经过hash函数得到的结果作为地址去存放当前的键值对(key-value)(这个是hashmap的存值方式)，但是却发现该键值不为空，这个冲突就是hash冲突了。

什么是容量？

容量 是哈希表中桶的数量，初始容量 只是哈希表在创建时的容量。

什么是负载因子？

负载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。默认加载因子是 0.75

容量和负载因子的重要性

容量与负载系数决定了可用的桶的数量，空桶太多会浪费空间，如果使用的太满则会严重影响操作的性能。极端情况下，假设只有一个桶，那么他就会退化成了链表，完全不能提供所谓的常数时间存在的性能。

在实践中应该如何选择呢？

如果能够知道 HashMap 要存取的键值对数量，可以考虑预先设置合适的容量大小。具体数值我们可以根据扩容发生的条件来做简单预估，根据前面的代码分析，我们知道它需要符合计算条件：
负载因子 * 容量 > 元素数量
所以，预先设置的容量需要满足，大于“预估元素数量 / 负载因子”，同时它是 2 的幂数，

---

HashMap的put方法

①.判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；
②.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；
③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals；
④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；
⑤.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
⑥.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容

如何扩容？

随着HashMap中元素的数量越来越多，发生碰撞的概率将越来越大，所产生的子链长度就会越来越长，这样势必会影响HashMap的存取速度。为了保证HashMap的效率，系统必须要在某个临界点进行扩容处理，该临界点就是HashMap中元素的数量在数值上等于threshold（table数组长度*负载因子）。但是，不得不说，扩容是一个非常耗时的过程，因为它需要重新计算这些元素在新table数组中的位置并进行复制处理。所以，如果我们能够提前预知HashMap 中元素的个数，那么在构造HashMap时预设元素的个数能够有效的提高HashMap的性能。