HashMap 数据结构为数组+链表结构 jdk1.8改为数组+链表+红黑树结构
一. 主要参数有：
int size：hashmap数组长度
float loadFactor：负载因子
int threshold：扩容
1. int size：hashmap数组长度
size长度为2的n次幂 默认长度为16
原因：长度为2的n次幂是 size-1的值所有二进制位全为1，这时只要key值计算的HashCode本身分布均匀，得出的index就分布均匀，有效降低了hash碰撞的几率
index值计算规则：
对key值进行hash取值然后与数组长度进行位运算
2. float loadFactor：负载因子
默认取值0.75，原因为在默认数组长度为16且加载因子为0.75时，数组在后续进行的rehash次数最少，性能最优
3. int threshold：扩容
扩容过程分两步：
1.对原有数组进行扩容，长度为原有数组两倍
2.对原有数组中数据重新进行对象插入位置index值计算
原因：在扩容后，index值计算规则发生变化，需重新计算
二. 操作原理
2.1 put操作
2.1.1 根据key值计算出在数组中的下标，由key的hashcode求出hash值，index=HashCode（Key） & （Length - 1）
2.1.2 判断是否达到扩容条件
2.1.3 若index对应位置为null，直接存入数据
2.1.4 若index对应位置不为null则发生了hash碰撞，判断插入key与碰撞key是否相同 相同则进行数据替换，不同则取下一节点重复上述步骤
2.1.5 插入节点后计算当前size是否需要扩容，如果大于阀门值需要扩容
resize
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果table为空或长度为0 就通过resize方法创建一个 Node<K,V>[] 赋值给tab
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//(n - 1) & hash] 计算插入key下标 判断对应位置是否null
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//hash冲突时 key相同 直接进行数据替换
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//判断数据结构是否为红黑树，如果是则用putTreeVal方法进行数据插入
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//当前数据结构为链表，进行节点循环判断
for (int binCount = 0; ; ++binCount) {
//下一节点为空时 将当前数据插入
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//若数据长度超过8 将链表转化为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//判断扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
2.2 get操作
2.2.1 计算index的位置，根据key的hashcode求出hash值，位置index = hash%length。
2.2.2 无论是数值，链表还是红黑树，for循环判断 如果hash值冲突就比对key是否相等，相等就返回对应的value，不同继续寻找下一节点
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//如果第一个值就是 则返回链表头
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
//判断当前是否为红黑树，如果是就通过getTreeNode获取
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
//循环从链表查询 找到hash值相同且key相同的数据
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
2.3 resize操作
（后续待更新）
写的有些杂乱，基本是想到哪就写到哪
网友评论