先上图,图片来自于此处
152128351581.png搜索了一些资料硬是没搞明白为什么table数组中有的存了好几个数据,有的存了一个,table里面搞了一个链表,为什么有链表呢,是因为hash碰撞导致的,详细请阅读此处,
public V put(K key, V value) {
//当key为null,调用putForNullKey方法,保存null与table第一个位置中,这是HashMap允许为null的原因
if (key == null)
return putForNullKey(value);
//计算key的hash值
int hash = hash(key.hashCode()); ------(1)
//计算key hash 值在 table 数组中的位置
int i = indexFor(hash, table.length); ------(2)
//从i出开始迭代 e,找到 key 保存的位置
for (Entry<K, V> e = table[i]; e != null; e = e.next) {
Object k;
//判断该条链上是否有hash值相同的(key相同)
//若存在相同,则直接覆盖value,返回旧value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value; //旧值 = 新值
e.value = value;
e.recordAccess(this);
return oldValue; //返回旧值
}
}
//修改次数增加1
modCount++;
//将key、value添加至i位置处
addEntry(hash, key, value, i);
return null;
}
根据这段put
源码来理解一下,key
为null
,保存一个键为null
的键值对,当然下回还可以再put
一个键为null
的值,HashMap
会帮你覆盖的,HashMap
利用键的hashcode
处理put
,get
操作大家都知道,key
不为null
我们计算key
的hash
值,然后根据hash
值获取在table
数组中的位置,根据数组下标获取到对应位置的Entry
对象,我们在table
中存储的hashMap
的一个内部类Entry
,其包含属性key
,value
,hash
值,next
节点,这个好处很多,一是在发生hash
碰撞时保持在table同一个位置保持链表结构,二是在get时非常方便获取value值。然后我们在第一次找到的Entry节点不为空是,然后根据key和节点中保存的相关信息进行多条件比对,如果命中,直接返回Entry对应的value,如果没有命中,继续根据节点的next属性寻找下一个Entry节点,根据key进行命中比对,若命中找到对应key的value进行覆盖,没有命中将该元素保存在链头(最先保存的元素放在链尾)。
若根据table[i]找到的节点为空,则直接进行保存。
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K, V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
}
此处代码我们可以看到,我们始终会让新加入的Entry在保存在table中,替换之前已有的元素,最新元素指向上一个元素,这样就形成了一个指向链,当然前提是我们计算出来的bucktIndex处有元素存在,若不存在则直接保存,指向的也就是空了,后面如果此处刚好发生hash碰撞则会产生指向链。
有序map主要是两大类,TreeMap和LinkedHashMap,
TreeMap会对插入的元素进行自然排序,也可以自定义comparator自定义排序规则。
LinkedHashMap遍历元素时会按照插入的顺序循环,linkedhashmap主要靠双向循环列表来实现顺序的,其内部数据结构和hashmap基本一致,数组中不同内存地址中的链表互相连接,从而保证我们在迭代的时候按照链表顺序取出数据
网友评论