HashMap

2014-07-09

这篇笔记是为了记录一下HashMap的在jdk中是如何实现的，以前也瞥过几眼代码，自以为有所了解，这次从头到尾看了一遍，发现以前确实还有很多遗漏的地方，这次一并总结出来。

HashMap实现了Map接口那么我们就来看看Map总共提供了哪些接口：

public interface Map<K,V> {

    boolean containsKey(Object key);

    boolean containsValue(Object value);

    V get(Object key);

    V put(K key, V value);

    V remove(Object key);

    void putAll(Map<? extends K, ? extends V> m);

    void clear();

    Set<K> keySet();

    Collection<V> values();

    Set<Map.Entry<K, V>> entrySet();
}

HashMap实现了Map接口，在逐个分析这些关键方法之前，先要来看一下HashMap的容量是怎么确定的，因为这和这些方法的具体实现有很大关系。

 /**
 * The default initial capacity - MUST be a power of two.
 */
 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

当我们new HashMap的时候，不指定容量的大小，那么会使用这个默认大小。正如注释所说，容量的大小必须是2得n次方，为什么必须是2得n次方？后面会有详尽解释。

当然和所有数据结构的初始化方式一样。我们也可以手动指定初始化的容量：

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

事实上在调用构造方法时时不会对初始化大小做限制的，当我们调用put方法往hashMap中放入键值对时，才会真正对hashMap中的hashTable进行初始化：

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {//如果table还未进行初始化，则调用inflateTable方法对table扩容
        inflateTable(threshold);
    }
    if (key == null)//如果key为null则直接调用putForNullKey方法，把value放入table[0]中
        return putForNullKey(value);
    int hash = hash(key);//没有直接用key.hashCode，使用自己的hash函数
    int i = indexFor(hash, table.length);//找到hash值在table中的位置
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {//查找有相同key值（==或equals）则替换为新的value返回旧的value
        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++;//modCount代表hashMap结构变更的次数，当对hashMap进行遍历时遇到另一个线程对hashMap进行了修改，则会fast fail
    addEntry(hash, key, value, i);//添加元素到table[i]中
    return null;
}

这个put方法中包含了很多需要注意的细节，例如inflateTable方法，只有在往map中put键值对时才会真正初始化hashTable：

private void inflateTable(int toSize) {
    // Find a power of 2 >= toSize
    int capacity = roundUpToPowerOf2(toSize);//根据初始化参数传入的size，找到一个2的n次方大于这个size

    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);//设置threshold的值，为下一次扩容做准备
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);
}

仔细看看roundUpToPowerOf2这个方法，其实逻辑很清晰：

private static int roundUpToPowerOf2(int number) {
    // assert number >= 0 : "number must be non-negative";
    int rounded = number >= MAXIMUM_CAPACITY
            ? MAXIMUM_CAPACITY
            : (rounded = Integer.highestOneBit(number)) != 0
                ? (Integer.bitCount(number) > 1) ? rounded << 1 : rounded
                : 1;

    return rounded;
}

如果所给的number大于hashMap容量最大值，则取最大值；否则判断如果如果这个int值得最高位的1的位置不存在的话，即这个int为0的话，则设置rounded为1；否则判断二进制的number存在多少个1，如果只有一个1的话，肯定是2的n次方直接返回，如果不只有一个1的话，左移一位保证rounded为2的n次方，返回。

再来看initHashSeedAsNeeded(capacity)方法

final boolean initHashSeedAsNeeded(int capacity) {
    boolean currentAltHashing = hashSeed != 0;//当前是否使用了altHash
    boolean useAltHashing = sun.misc.VM.isBooted() &&
            (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);//是否使用了系统hash，通过内部类Hold在jvm启动时初始化Holder.ALTERNATIVE_HASHING_THRESHOLD
    boolean switching = currentAltHashing ^ useAltHashing;//如果两者有一个为真
    if (switching) {
        hashSeed = useAltHashing
            ? sun.misc.Hashing.randomHashSeed(this)
            : 0;
    }//则重新初始化hashSeed
    return switching;
}

inflateTable方法大概就是这样，接下来看一下hash函数究竟做了些什么？

为什么需要这个hash函数呢，明明每个key都有其对应的hashCode了。在具体了解hash函数之前先来看一下indexFor方法：

static int indexFor(int h, int length) {
    // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    return h & (length-1);
}

为什么indexFor方法不是h % length，而是h & (length-1)呢。考虑到hashMap的length永远是2的n次方，h & (length-1)与h % length相等，而位运算显然有更高的效率。

在达成以上共识的情况下，让我们来考虑这样一种情况：

按默认大小初始化一个HashMap，length = 15，然后尝试把key为31、63和95的三个键值对放入map中，结果如何呢？分别对这key值执行h & (length - 1)：

31=00000000000000000000000000011111 => 1111=15 63=00000000000000000000000000111111 => 1111=15 95=00000000000000000000000001011111 => 1111=15

得到的结果相同，也就是说这三个数会造成hash冲突。也就是说(2ⁿ-1)总会是一个1的序列，因此不管怎样，最后会执行0&1的于然后得出0。上面的例子，也就解释了凡是在末尾全是1111的都返回相同的index，因此，尽管我们有不同的hashcode，对象却都被存在table中index为15的位置。

所以需要hash函数来规避这个问题，下面来看一下hash函数都做了些什么：

final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    h ^= k.hashCode();

    // 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);
}

首先会对String类型的key值应用sun.misc.Hashing.stringHash32来获取他的hash值。下面的一系列位运算我只能说根据注释来看会让hashmap的元素能够均匀的分布在hashTable里，降低发生hash冲突的可能性，但具体为什么这个算法能带来这样的效果，我也没有深入研究。

接下来再开看看put方法中最后调用addEntry把元素放入hashTable中是怎么做的：

void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {//如果size超过阈值，并且当前这个key值的位置已经有元素占据了
        resize(2 * table.length);//则进行扩容，容量为之前hashTable的两倍
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }

    createEntry(hash, key, value, bucketIndex);//如果无需扩容这直接创建entry
}

void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);//new Entry的过程中会把链表中上一个元素和当前元素关联起来，并且把当前元素放置在链表的顶部，出于新添加的元素有可能会更频繁的被访问到的原则
    size++;
}

这样就把put方法的主流成解析完了，下面来看一下resize是怎么做的：

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }

    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

resize方法没有任何特别之处，直接看看transfer是怎么做的：

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {//遍历老得hashTable
        while(null != e) {//如果table中的元素不为null
            Entry<K,V> next = e.next;//暂存e.next
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];//把newTable[i]赋予e.next
            newTable[i] = e;//把e元素放置在newTable[i]上
            e = next;//把e.next赋到e上
        }
    }
}

就这样完成了hashTable中所有元素，包括每个链表中的所有元素的重新分配。