HashMap原理

有一次被问到HashMap的实现原理，没回答出来。今天看了一下源码，记录如下：

 

首先看get方法，看其如何找到值对象。

1. 得到key的哈希值
2. 根据哈希值计算得到索引
3. 从数组里取得一个Entry，并且该entry是一个链表。

 

public V get(Object key) {
        if (key == null)
            return getForNullKey();
        int hash = hash(key.hashCode());//获取哈希值
        for (Entry<K,V> e = table[indexFor(hash, table.length)];//根据哈希值得到索引
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e.value;
        }
        return null;
    }

 

由此可知HashMap的基本数据结构就是一个一维数组，并且数组上每个元素都可能是一个单向链表的头。每个链表上存放的元素都是Key的哈希值相同的对象。（由此基本可以回答面试问题了）

 

继续看hash方法：

/**
     * Applies a supplemental hash function to a given hashCode, which
     * defends against poor quality hash functions.  This is critical
     * because HashMap uses power-of-two length hash tables, that
     * otherwise encounter collisions for hashCodes that do not differ
     * in lower bits. Note: Null keys always map to hash 0, thus index 0.
     */
    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);
    }

 

这个方法很奇特，用到了“>>>”这样的无符号右移位操作符，不管什么花招，目的只有一个：为了防止某些hashcode算法太糟糕，低位不变化（从二进制角度看），所以进行移位操作，把高位和低位的数据进行混乱合并，最终把高位反映到低位部分来。为什么要这么做呢？因为hashmap的另一个函数indexFor只管低位数据。

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

 这个计算索引的方法，简单粗暴的用本质上就是求余数的方法，得到索引。虽然这里用了位操作，我想那是为了效率。

 

接着看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);
        table = newTable;
        threshold = (int)(newCapacity * loadFactor);
    }

 看过以后，发现其实也很简单，分配一个新的数组，把数据都转移到新的数组里。resize既管扩大，也管缩小。