转载

扯扯HashMap

HashMap是我们比较常用的数据结构，是有数组和链表组合构成的数据结构。

数组里面每个地方都是以Key-Value的方式存储的，Java7里面叫Entry在Java8里面叫Node。在put的时候会根据key的hash去计算index的值。

举例：需要向HashMap中put熊猫（key:Panda）或猫熊(key:Pando(就当写错了，嘿嘿))两个数据。

put熊猫过程：

put猫熊过程：

put(Pando,猫熊)
HashMap同样通过哈希算法对Pando，最终得出index值，因为hash计算本来就是概率性问题，就有可能计算出来的index也是2，这种情况就会产生链表2:Panda|熊猫---->Pando|猫熊

每一个节点都会保存自身的hash、key、value、以及下个节点(Node<K,V> next)(说明链表是单向链表)

说到这里，可以说说Entry和Node链表插入的方式：

java8之前（也就是Entry）是头插法，也就是说新来的数据会取代原有的值，原来的数据就顺推到链表中去（考虑到后来的数据被查到可能性更大一点，这样就可以提高查询效率），但是缺点是有可能形成环链。

java8之后（包括java8），都是用尾部插入方式了（哇~为啥要改成尾部插入的方式呢？）

改成尾部插入方式肯定是有期原因的了，首先我们来看一下HashMap的扩容机制：

数组的容量是有限的，数据的多次插入，等到达一定的数量就会进行扩容，就是我们的resize操作;触发resize的因素有两个：
- 一个是Capacity: HashMap当前的长度；
- 一个是LoadFactor: 负载因子，默认值0.75f。
当触发扩容的时候，扩容的动作有两步
- 扩容：创建一个新的Entry空数组，长度是原来数组的2倍
- ReHash：遍历原Entry数组，把所有的Entry重新Hash到新数组

备注：扩容是因为达到了负载因子的长度，然后重新hash是因为hash公式里面有长度因子的原因

我们来看看Hash找索引的计算公式：

index = HashCode(Key) & (Length - 1)

我们来看看这个公式的运算逻辑以及目的(比如数组的长度是8（HashMap的初始长度最好是原来的2的幂次方）),hash值是1010010100101010001111100：

1010010100101010001111100
& 0000000000000000000000111
---------------------------
  0000000000000000000000100

这样就是保证了数据能够均匀分配

之前提到HashMap的容量大小是2的幂次方，通过源码我们知道HashMap的默认值大小是16，是2的幂次方，会是16主要应该是考虑16会是用的比较频繁的大小吧。

原文 https://segmentfault.com/a/1190000022499183

正文到此结束

所属分类： Java 编程技术

本站定位：个人技术类博客

本站作用：写博客、记日志、闲聊扯淡鼓捣技术。