hashmap内部实现
hashmap内部实现
写此篇，是因为面试的时候经常被问道hashmap原理，我的回答通常是不知道（内心的os是这些不就是网上一抓一把的面试题么），
但是还是不想丢人。于是花点时间看了一下hashcode的源码，其中有两个不太的明白的地方，一个是
tableSizeFor这个方法一个是这段代码tab[(n - 1) & hash]。由于我对几乎不会用到位运算所以不太理解方法是用来干嘛的，于是百度了一下相关的内容
1）先简要概况一下hashmap是如何实现的，hashmap是通过散列码映射到一个Node类型数组，
这个node数据类型很简单，具有链表数据结构的特点，有next属性指向下一个node数据
存储的时候，根据对象的散列码（hashcode）对数组最大长度取模得到数组下标，如果相应的数组位置没有数据，则直接存到
数组的位置。如果相应的位置有数据，则使用该数据的next属性指向新数据
所以 整个的数据结构是无序的映射，也就是说 通过hashcode取模得到数组下标，映射到相应的数组位置。每个数组的数据都可以形成一个小的链表
（当hashcode对数组最大长度取 模的相同位置有数据的情况，会形成链表）是二维数据，只不过第二维是链表
而这个链表的结构在高版本java中又进行了优化，当长度超过8以后会使用另一个新的数据结构TreeNode（同时具有红黑树与链表特性）来替换原有数据结构，
而上面我不明白的部分就是 由于 如果一个数a对一个二的整数幂的数字b取模 那么结果和 (b-1)&a结果相同。而位与操作执行速度比取模快
所以hashmap中node数组的长度是通过tableSizeFor这个算法来计算。为了返回最接近当前长度的二的整数幂的数字
2）相应的源码释意 ，直接看put方法就可以说明原理了，这里的table就是node数组， 如果table为null或者是长度为零的情况，直接调用resize方法，
resize方法中判断了如果table的长度为0 则返回 DEFAULT_INITIAL_CAPACITY默认的大小，
然年后tab[i=(n-1)&hash]是根据hashcode找到相应位置的数据，如果为空就创建一个新的Node对象
如果不为空，判断key值是否与传参的key值相同，如果相同 把 e（声明的一个node对象，最终修改的就是他的值，也就是value是要存到这个数据的）
指向p，简而言之如果key相同后面就直接修改p的值。
如果不同判断p是不是一个TreeNode对象，如果是。调用putTreeVal方法把当前数据添加到p的next的位置
如果不是创建一个新的node对象存放当前的数据将p的next指向这个新的node对象，
当遍历链表的循环超过了7次就替换成TreeNode对象
TreeNode 和Node 的源码在hashmap中都有。红黑树的特性我也没有去看。看了可能会有空再更新一篇吧
以上是自己看源码的理解。如果有遗漏或者错的地方，欢迎指正
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
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);
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;
}
————————————————
版权声明：本文为CSDN博主「雨痕消失」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/u011334510/article/details/114745005