HashMap 1.8 源码分析
1.HashMap的底层数据结构---数组+单向链表
2.一个完整的节点存数数据,在java中一切皆对象,所以在HashMap中应该存在一个类
public class Node{
int hash;
String key;
Object value;
Node next;
}
3.当想要往HashMap中存数数据的时候,肯定需要初始化,初始化时,会遇到几个问题?
1)要知道数组的容量是多少
默认大小为:static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
2)需要存储的数据放到数组的哪个位置
通过计算hash值来确定位置,java采用的算法是:
a:如果key = null ,则 hash值为0,
如果key不等于null ,则首先 得到 int h = key.hashCode(),然后让h的高16位和低16位做异或运算
b:假设数组的容量是 n = 16,那么最终的存储位置 为 (n - 1)&hash<a步骤得到的结果>
说明:如果n = 16 ,那么 n-1 = 15 其二进制为 000001111,那么和这个二进制&得到的结果永远只能保留后四位,也就是在0-15之间的数字
由此可以得到结论:HashMap扩容或者初始化一定要是是2的n次方,不然会存在永远不会存储数据的位置,极端情况,HashMap变成单向链表或者红黑树了
3)随着数据的越来越多,HashMap需要扩容,这个达到什么标准才会扩容?
在HashMap类中存在一个变量 : int threshold;
这个变量的值等于 数组的容量*负载因子
说明:当HashMap中节点的数量大于 threshold时,就扩容,重新分配HashMap中的节点
4.当计算得到数组需要存储的位置 i 时,会出现两种情况
1)当前位置 i 还没有值,那么直接把数据存储到这个位置就可以了
2)当前位置已经存在值
a:新的key值和老的key值相等,则直接把当前位置的的value值替换即可
b:当前链表的节点类型是红黑数即属性节点,则进入红黑树添加逻辑中去
c:新的key值和老的key值不相等,则往下单向链表查找
如果在链表中找到和新的key值相等并且两个节点的hash值也相等的话,则把该节点替换成新的节点,
如果没有找到和新的key值且hash值相等的节点,则把新的节点放到链表的最后
当完成替换或者放到链表的最后,则需要判断当前链表的长度,是否超出一定的值,如果超出,则需要把链表转成红黑树