HashMap的扩容机制
目录
一、HashMap的底层
底层：采用数组+链表(JDK1.7)，采用数组+链表+红黑树(JDK1.8)。线程不安全。
容器：HashMap默认容器长度为16，扩容因子为0.75，以2的n次方扩容，最高可扩容30次。如第一次是长度达到16*0.75=12的时候开始扩容，16*2^1=32。
二、HashMap的扩容机制原理
1、JDK1.7版本扩容
①：先生成新数组；
②：遍历老数组中的每个位置上的链表上的每个元素；
③：获取每个元素的key，并基于新数组长度，计算出每个元素在新数组中的下标；
④：将元素添加到新数组中去；
⑤：所有元素转移完之后，将新数组赋值给HashMap对象的table属性。
2、JDK1.8版本扩容
①：先生成新数组；
②：遍历老数组中的每个位置上的链表或红黑树；
③：如果是链表，则直接将链表中的每个元素重新计算下标，并添加到新数组中去；
④：如果是红黑树，则先遍历红黑树，先计算出红黑树中每个元素对应在新数组中的下标位置；
a：统计每个下标位置的元素个数；
b：如果该位置下的元素个数超过了8，则生成一个新的红黑树，并将根节点添加到新数组的对应位置；
c：如果该位置下的元素个数没有超过8，那么则生成一个链表，并将链表的头节点添加到新数组的对应位置；
⑤：所有元素转移完了之后，将新数组赋值给HashMap对象的table属性。
三、HashMap底层JDK1.7到JDK1.8的变化
JDK1.8相较与JDK1.7在数组+链表的基础上添加了红黑树，加红黑树的目的时提高HashMap插入和查询的整体效率；
JDK1.7中链表插入采用的是头插法，JDK1.8中插入使用的是尾插法，因为JDK1.8中插入key和value时需要判断链表元素个数，所以需要遍历链表统计链表元素个数，所以正好直接使用尾插法；
JDK1.7哈希算法比较复杂，存在各种右移与异或运算，JDK1.8进行了简化，因为复杂的哈希算法目的就是提高散列性，来提供HashMap的整体效率，而1.8新增了红黑树，所以可以适当的简化哈希算法，节省CPU资源。
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
