千锋教育Java入门全套视频教程(java核心技术，适合java零基础，Java

HashMap的底层实现原理简单分析:

1.在使用无参构造方法创建一个新的HashMap时,系统自动分配了一个阈值为0.75.该阈值的含义指的是,当HashMap中存放的键值对总数超过桶数(无参构造时,默认有16个桶)*阈值时,桶数将自动进行扩容.而进行带参构造时,可以传只传一个数,在经过特定的位运算后,得到2的n次方的一个数即作为桶的数量,传入两个数时,第一个数的作用与只传入一个参数时一直,第二个参数则作为阈值.

2.在向该HashMap中通过put增加元素时,先通过计算一个特殊的算法值,由key的哈希值与该值右移16位的值做异或运算.当key为null时,返回0.

3.第一次通过put方法时,会创造出长度为桶数的的链表数组.将之前提到的特殊算法值与桶数-1作位与运算.得到0-桶数-1之间的一个数,将该键值对,放在对应的下标的链表数组下

4.后续添加过程为,先计算key的特殊算法值,并放在指定的链表数组处,如果该链表处为空,之间将键值对放置于此.如果不为空,判断该链表为节点,树,还是链表,

1)如果是单节点,比较key值与特殊算法值,如果相同,则用新的value替换旧的value

2)如果是树,就将该键值对加入

3)如果是链表,将该key与链表中所有的key值对比,当该key与所有key都不同时,放在最后一个节点上,如果节点的数量达到9个,则开始判断是否树化,树化时判断长度是否大于32,不满足则使桶的长度翻倍.