Java集合-HashMap的实现原理


1.HashMap工作原理　　

　　当我们往hashmap中put元素的时候，先根据key的hash值得到这个元素在数组中的位置（即下标），然后就可以把这个元素放到对应的位置中了。如果这个元素所在的位子上已经存放有其他元素了（两个 Entry 的 key 的 hashCode() 返回值相同，即发生了哈希冲突），如果这两个 Entry 的 key 通过 equals 比较返回 true，新添加 Entry 的 value 将覆盖集合中原有 Entry的 value；如果这两个 Entry 的 key 通过 equals 比较返回 false，那么在同一个位子上的元素将以链表的形式存放，Java1.7及以前版本采用头插法，java1.8开始采用尾插法。并且java1.8中，如果链表长度超过阈值（TREEIFY THRESHOLD==8），就把链表转成红黑树，链表长度低于6，就把红黑树转回链表。如果桶满了（容量16 * 加载因子0.75），就需要 resize（扩容2倍后重排） 　　我们调用 get() 方法，HashMap 会使用键对象的 hashcode 找到 bucket 位置，找到 bucket 位置之后，会调用 keys.equals() 方法去找到链表中正确的节点，最终找到要找的值对象。从这里我们可以想象得到，如果每个位置上的链表只有一个元素，那么hashmap的get效率将是最高的，但是理想总是美好的，现实总是有困难需要我们去克服。

2.HashMap容量为2次幂的原因

　　我们先来说一下hash算法，我们可以看到在hashmap中要找到某个元素，需要根据key的hash值来求得对应数组中的位置。如何计算这个位置就是hash算法。前面说过hashmap的数据结构是数组和链表的结合，所以我们当然希望这个hashmap里面的元素位置尽量的分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，而不用再去遍历链表。 

所以我们首先想到的就是把hashcode对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。但是，“模”运算的消耗还是比较大的，能不能找一种更快速，消耗更小的方式那？java中时这样做的：

1 https://www.linuxboy.net/topicnews.aspx?tid=19


linuxboy的RSS地址：https://www.linuxboy.net/rssFeed.aspx


本文永久更新链接地址：https://www.linuxboy.net/Linux/2020-03/162763.htm

相关内容