hashmap基本原理

• 根据的hashCode值存储数据。由数组+链表组成的，Entnr数组是HashMap的主体，数组中每个元素是一个单向链表。链表则是1/1解哈希冲突而存在的。在lava8中，使用红黑树优化。当链表长度大于8并且元素个数大于64，转为红黑树。 找长度是logn， log8=3,8/2=4.
• 链表转红黑树阈值是8—hash碰撞8次的概率很低，8够用了。
• 红黑树转链表是6–如果在8附近，会发生链表和红黑树相互转化。

构造函数

• 默认；指定初始容量；指初始容量和负载因子；包含子map的构造函数。

hashmap数据插入原理

1. 首先判断数组是否为空，为空进行初始化；
2. 计算k的hashcode值进而得到hash值，计算应该存储的下标index；
3. 如果tablelindex为空，直接插入:否则判断k是否相等，相等就罗盖value值:(hashCode,eauals)
4. 否则判断是树形节点，是的话就插入；否则就插入链表中，判断长度是否大于8，大于转化为红黑树。
5. 插入后，判断节点数是否大于阈值，大于就扩容。

HashMap使用第0个桶存放键为null的键值对。

hashmap初始容量的设置

• 默认容量16，负载因子0.75.如果自己传入c，容量大小是大于c的2的次方，例如，传入12，容量为16.
• 具体:把高位为1的后面全变为1，最后再进行+1操作。(让初始二进制右移1，2,4,8,16位，位或，要先减去1，如果cap已经是2的次幂，不减1最后得到的cap是cap的两倍)

为什么hashmap容量是2的整数次？

• 这样length-1相当于低位掩码，高位全部为0，只保留低位值(相当于对容量取模操作，位运算更快)

hashmap的hash函数

• 先得到K的hashcode0值，32位的int；右移16位，与自己异或。也就是高16和低16位异或。增大低位的随机性，降低hash碰撞(扰动函数)

为什么hashcode之后还要hash？

• 因为int型散列范围很大，40亿长度数组太大了.

怎么得到下标index？

• 把散列值h和数组长度length-1做”与“操作。位运算&比%要快。