HashMap 分享

数据结构(数组、链表、树)

• 数组：采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为 O(1)，但在数组中间以及头部插入数据时，需要复制移动后面的元素。
• 链表：一种在物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
• 树：由 n（n≥1）个有限结点组成的一个具有层次关系的集合，就像是一棵倒挂的树。
• 哈希表：根据关键码值（Key value）直接进行访问的数据结构。通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数，存放记录的数组就叫做哈希表。

Hashmap的数据结构图

                         

 

负载因子

• Hashmap中的loadFactor的字段，主要用来计算map扩容的阈值，如果构造参数不设置的话，它默认的容量是16，loadFactor为0.75，所以计算查来map发生扩容的阈值为：12个，只要达到这个阈值，map的数据组就会发生扩容，及调用resize（）方法。
• 对于一个map查询效率最高的情况肯定是数组中每个地方都有值，且无链表状态，这种理想状态的查询效率是最高的，但毕竟是理想状态，首先map中数组下标的计算规则是(n-1) & hash 原因后面解释，所以显示情况中我们很难避免不同的key计算出相同的下标值，这就是哈希冲突，解决方案有很多，hashmap采用的是在发生冲突的时候维护一个单向链表将数值维护到链表中。
• 至于负载因子为什么默认是0.75，肯定是默认情况下在容量与效率之前取的均衡数，在0.75的时候在大多数的情况下是比较优的，理想的情况上边已经说了，多数还是达不到理想的情况的，比如容量16个，如果这16个的hash值算出来的下标全是一个值，将从数组变成链表结构，所以负载因子主要是用来综合这个链表跟数组长度的职能。

索引计算

       数组下标的计算规则是(n-1) & hash，针对计算的结果直接对数组进行随机访问，这是效率高的原因，所以有效的索引计算方案，尽最大可能减少hash冲突是非常重要的，那么问题来了，为啥选用(n-1) & hash的计算规则呢？

       首先map的size为2的n次方，所以说size必然是偶数，n-1必为单数，即二进制的最低为必然是1，与hash值做与运算的结果有单数也有双数，反之的化得到的索引必然为偶数，导致一半数组位置必然为空，造成空间的浪费。

       第二hashmap重写了hash算法，见下表，可以看到他对hash只做了无符号右移16为的操作，也就是取 int 类型的一半，刚好可以将该二进制数对半切开，并且使用位异或运算（如果两个数对应的位置相反，则结果为 1，反之为 0），这样的话，就能避免上面的情况发生。这就是 hash() 方法的具体实现方式。简而言之，就是尽量打乱 hashCode 真正参与运算的低 16 位

static final int hash(Object key) {         int h;      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

 

Resize优化

        再谈hashmap的扩容的优点；再1.7后的优化点主要是再扩容后的数组索引的在即 计算上，在1.7中扩容后是重新计算的entity的索引，1.8后的计算逻辑优化为：在size 为4的map扩容后size为8;二进制为0010变为0100即为像左移动一位，在扩容中只 用判断原来的 hash 值和左移动的一位（newtable 的值）按位与操作是 0 或 1 就行， 0 的话索引不变，1 的话索引变成原索引加上扩容前数组。

元素的获取优化

• Hashmap查询逻辑在上图也可以看出来，拿到一个key后首先根据key计算出它的对应的数组的下标(这里多说一句，为什么map要用string作为它的key,因为java中所有的string数组都保留在jvm的常量池中,即使new的对象的value值也是从常量池中获取的，且string为final修饰不会被修改，他的hash值是恒定不变的，所以可以做map的key)，获取node的链表，再去循环链表获取相同key对应的value.链表的长度将直接影响查询的效率；
• 在1.8优化中，在链表长度达到8且存储数量达到64以后会将链表维护成一个红黑树。
• 红黑树与二叉树的区别就是他允许局部的不平衡，所以可以减少二叉树的左旋次数与右旋次数，效率上要优与二叉树。