对于hashmap 其实我之前已有一些了解，一种键值对结构的存储方案，不过在使用时并没有对其进行深入的了解，那么今天我就和大家一起进入HashMap的世界.
首先我们来说一下HashMap的数据结构:
HashMap 使用数组 + 链表的结构来进行数据存储.
image.png
如上图所示,数组中每个元素都是自身链表的入口元素,每个node都包含next字段用于保存下个元素。
接下来我们看看HashMap如何将数据写入，先看put源码如下：
HashMap hashMap = new HashMap();
System.out.println(hashMap.put("1", "123"));
如以上两行代码所示, 我定义了hashmap 并调用其put方法，那么要了解其运行逻辑咱们就得进入put函数看源码了 如下：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
这里其实可以看到,put 函数调用了hashmap对象的putVal函数，putVal有五个参数，每个参数的解释如下：
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
我们继续往下来看putVal的详细代码：
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) //将table赋值给tab并判断是否为空
n = (tab = resize()).length; //若为空,初始化tab数组
if ((p = tab[i = (n - 1) & hash]) == null) //根据数组长度与hash值进行&运算决定当前数据存储下标,并判断当前下标是否有元素存在
tab[i] = newNode(hash, key, value, null); //若没有元素则新建node并保存
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) //若下标冲突，判断其hash以及key是否一致
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else { //若不一致,需要遍历p链表，找出相应的位置存放
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) { //这里e对象已经被赋值了哦 这对于后面的理解很重要
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash); //若循环次数达到8次 则这里会转换数据结构为平衡树结构
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) //若hash值与key相同则退出循环
break;
p = e; //若都不满足 则将p赋值为e(e = p.next)
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null) //这里根据入参以及oldValue来决定是否覆盖老数据
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize(); //这里是对map的扩容，当tab元素的数量大于阈值
afterNodeInsertion(evict);
return null;
}
流程如下：
1，首先，判断当前hashmap对象是否有值，如果没有值那么初始化tab 并指定容量
2，通过 & hash运算获取对应下标元素并赋值到p，如果p为null 则新建node并赋值到tab当前index
3，若前两个条件都不满足，那么表示该hashmap数据有值且出现了下标冲突，
那么这个时候首先判断出现冲突的两个node对象的hash值以及key是否一致，若为true,那么更新key对应的value(这里是否要更新取决于参数onlyIfAbsent 默认为false)
4.若hash值或者key不一致，那么判断p元素是否是TreeNode实例，
若是则put到平衡树结构。
5，若p不是TreeNode实例，那么这里又要去遍历p 这个链表, 若有相同的key以及hash则停止遍历,若没有那么将生成新的node放入链表最后
阈值threshold的计算默认是map长度 * 0.75.
可以通过new HashMap(int capacity, double flator)的构造函数设置
这里是对于put的一些分析，后面会继续写get函数的分析。
有不足之处请及时指出.
网友评论