Java集合-HashMap

以前写过一篇源码分析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值。