初识HashMap

之前的List，讲了ArrayList、LinkedList，最后讲到了CopyOnWriteArrayList，就前两者而言，软件开发，反应的是两种思想：

（1）ArrayList以数组形式实现，顺序插入、查找快，插入、删除较慢

（2）LinkedList以链表形式实现，顺序插入、查找较慢，插入、删除利便

那么是否有一种数据布局可以或许团结上面两种的利益呢？有，谜底就是HashMap。

HashMap是一种非经常见、利便和有用的荟萃，是一种键值对（K-V）形式的存储布局，下面将照旧用图示的方法解读HashMap的实现道理。

四个存眷点在HashMap上的谜底

添加数据

首先看一下HashMap的一个存储单位Entry：

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    int hash;
    ...
}

之前一篇写LinkedList的文章，内里写到LinkedList是一个双向链表，从HashMap的Entry看得出，Entry构成的是一个单向链表，因为内里只有Entry的后继Entry，而没有Entry的前驱Entry。用图暗示应该是这么一个数据布局：

接下来，假设我有这么一段代码：

public static void main(String[] args)
{
     Map<String, String> map = new HashMap<String, String>();
     map.put("111", "111");
     map.put("222", "222");
}

看一下做了什么。首先从第3行开始，new了一个HashMap出来：

public HashMap() {
     this.loadFactor = DEFAULT_LOAD_FACTOR;
     threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
     table = new Entry[DEFAULT_INITIAL_CAPACITY];
     init();
}

留意一下第5行的init()是个空要领，它是HashMap的子类好比LinkedHashMap结构的时候利用的。DEFAULT_INITIAL_CAPACITY为16，也就是说，HashMap在new的时候结构出了一个巨细为16的Entry数组，Entry内所有数据都取默认值，如图示为：

看到new出了一个巨细为16的Entry数组来。接着第4行，put了一个Key和Value同为111的字符串，看一下put的时候底层做了什么：

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key.hashCode());
    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;
}

static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

static int indexFor(int h, int length) {
     return h & (length-1);
 }

看一下put要领的几个步调：

1、第2行~第3行就是HashMap答允Key值为空的原因，空的Key会默认放在第0位的数组位置上

2、第4行拿到Key值的HashCode，由于HashCode是Object的要领，因此每个工具都有一个HashCode，对这个HashCode做一次hash计较。凭据JDK源码注释的说法，这次hash的浸染是按照给定的HashCode对它做一次打乱的操纵，防备一些糟糕的Hash算法发生的糟糕的Hash值，至于为什么要防备糟糕的Hash值，HashMap添加元素的最后会讲到

3、第5行按照从头计较的HashCode，对Entry数组的巨细取模获得一个Entry数组的位置。看到这里利用了&，移位加速一点代码运行效率。别的，这个取模操纵的正确性依赖于length必需是2的N次幂，这个熟悉二进制的伴侣必然领略，因此留意HashMap结构函数中，假如你指定HashMap初始数组的巨细initialCapacity，假如initialCapacity不是2的N次幂，HashMap会算出大于initialCapacity的最小2的N次幂的值，作为Entry数组的初始化巨细。这里为了讲授利便，我们假定字符串111和字符串222算出来的i都是1