以前写过一篇源码分析HashMap数据结构的，现在找不回了，重新简单的分析一下HashMap的数据结构增强一下自己的记忆，好久不写博，语言组织会比较差。
首先HashMap简单的理解应该是一种“数组”加“链表的结构”，先贴一个简单的数据结构的图参考一下：
image
!
其中，图中显示的Entry，表示的是
Entry<K,V>
里面的属性为：
final K key;
V value;
Entry<K,V> next;
int hash;
可以看到，Entry中存有hash值，当前Entry的键值对(K,V),指向下一个Entry的指针next。
我们先分析左侧初始化的Entry数组。
transient Entry[] table;
那么初始化大小的为：
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
接着，怎么确定数据存放到数组中的哪一个Entry中呢？那么我们先看put方法：
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
首先put方法会计算当前key值的hash值，并将hash值传入到putVal方法。
putVal方法首先判断表中该hash值的Table[hash & Entry[].length]位置上是否有entry，如果没有，就将当前的entry放置于此，如有，就将该位置的entry值设成当前值，并将next指向原来桶的值。
参考第一个图中的展示。
get的方法可以反向推理，通过hash值找到entry在数组的位置，然后通过链表不断的往后寻找对应的key值。
那么这里有一个问题，当table初始定义的大小太小，hashmap存取的数据多的时候，hash值碰撞会增高，每一个桶中的存取的链表就会很深。
所以，当：size >= threshold，其中
threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
static final float DEFAULT_LOAD_FACTOR = 0.75f;
最后延伸一个问题，为什么HashMap线程是不安全的？
因为在链表中，next指向有可能同时有两个线程同时修改next的值，造成数据被覆盖的情况，丢失entry值。
网友评论