HashMap 实现详解

HashMap是哈希表对Map非线程安全版本的实现，它允许key为null，也允许value为null。所谓哈希表就是通过一个哈希函数计算出一个key的哈希值，然后使用该哈希值定位对应的value所在的位置；如果出现哈希值冲突（多个key产生相同的哈希值），则采用一定的冲突处理方法定位到正真value位置，然后返回查找到的value值。一般哈希表内部使用一个数组实现，使用哈希函数计算出key对应数组中的位置，然后使用处理冲突法找到真正的value，并返回。因而实现哈希表最主要的问题在于选择哈希函数和冲突处理方法，好的哈希函数能使数据分布更加零散，从而减少冲突的可能性，而好的冲突处理方法能使冲突处理更快，尽量让数据分布更加零散，从而不会影响将来的冲突处理方法。

在严蔚敏、吴伟明版本的《数据结构（C语言版）》中提供的哈希函数有：1. 直接定址法（线性函数法）；2. 数字分析法；3. 平方取中法；4. 折叠法；5. 除留余数法；6. 随机数法。在JDK的HashMap中采用了移位异或法后除留余数（和2的n次方'&'操作）。HashMap内部的数据结构是一个Entry<K, V>的数组，在使用key查找value时，先使用key实例计算hash值，然后对计算出的hash值做各种移位和异或操作，然后取其数组的最大索引值的余数（'&'操作，一般其容量值都是2的倍数，因而可以认为是除留余数）。在JDK 1.7中对String类型采用了内部hash算法（当数组容量超过一定的阀值，使用“jdk.map.althashing.threshold”设置该阀值，默认为Integer.MAX_VALUE，即关闭该功能），并且使用了一个hashSeed作为初始值，不了解这些算法的具体缘由，就这样浅尝辄止了。
在JDK的HashMap中采用了链地址法，即每个数组bucket中存放的是一个Entry链，每次新添加一个键值对，就是向链头添加一个Entry实例，新添加的Entry的下一个元素是原有的链头（如果该数组bucket不存在Entry链，则原有链头值为null，不影响逻辑）。每个Entry包含key、value、hash值和指向下一个Entry的next指针。

static class Entry<K,V> implements Map.Entry<K,V> {

    final K key;

    V value;

    Entry<K,V> next;

    int hash;

}

添加
从以上描述中，我们可以知道添加新的键值对可以分成两部分：
1. 使用key计算出内部数组的索引值（index）。
2. 如果该索引的数组bucket中已经存在Entry链，并且该链中已经存在新添加的key的值，则将原有的值设置成新添加的值，并返回旧值。
3. 否则，创建新的Entry实例，将该实例插入到原有链的头部。
4. 在新添加Entry实例时，如果当前size超过阀值（capacity * loadFactor），数组容量将会自动扩大两倍，在数组扩容时，所有原存在的Entry会重新计算索引值，并且Entry链的顺序也会发生颠倒（如果还在同一个链中的话）；而该新添加的Entry的索引值也会重新计算。
5. 对key为null时，默认数组的索引值为0，其他逻辑不变。

void addEntry(int hash, K key, V value, int bucketIndex) {

    if ((size >= threshold) && (null != table[bucketIndex])) {

        resize(2 * table.length);

        hash = (null != key) ? hash(key) : 0;

        bucketIndex = indexFor(hash, table.length);

    }

    createEntry(hash, key, value, bucketIndex);

  }

void createEntry(int hash, K key, V value, int bucketIndex) {

    Entry<K,V> e = table[bucketIndex];

    table[bucketIndex] = new Entry<>(hash, key, value, e);

    size++;

    }

查找
查找和添加类似，首先根据key计算出数组的索引值（如果key为null，则索引值为0），然后顺序查找该索引值对应的Entry链，如果在Entry链中找到相等的key，则表示找到相应的Entry记录，否则，表示没找到，返回null。对get()操作返回Entry中的Value值，对于containsKey()操作，则判断是否存在记录，两个方法都调用getEntry()方法：

final Entry<K,V> getEntry(Object key) {

    int hash = (key == null) ? 0 : hash(key);

    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 != null && key.equals(k))))

    return e;

    }

    return null;

}

而对于value查找（如containsValue()操作）则需要整个表遍历（数组遍历和数组中的Entry链遍历），因而这种查找的效率比较低，代码实现也比较简单。

移除
移除操作（remove()）也是先通过key值计算数组中的索引号（当key为null时索引号为0），从而找到Entry链，查找Entry链中的Entry，并将该Entry删除。

遍历
HashMap中实现了一个HashIterator，它首先遍历数组，查找到一个非null的Entry实例，记录该Entry所在数组索引，然后在下一个next()操作中，继续查找下一个非null的Entry，并将之前查找到的非null Entry返回。为实现遍历时不能修改HashMap的内容（可以更新已存在的记录的值，但是不可以添加、删除原有记录），HashMap记录一个modCount字段，在每次添加或删除操作起效时，将modCount自增，而在创建HashIterator时记录当前的modCount值（expectedModCount），如果在遍历过程中（next()、remove()）操作时，HashMap中的modCount和已存储的expectedModCount不一样，表示HashMap已经被修改，抛出ConcurrentModificationException。即所谓的fail fast原则。
在HashMap中返回的key、value、Entry集合都是基于该Iterator实现，实现比较简单，不细讲。

注：1.clear()操作引起的内存问题-由于clear()操作只是将数组中的所有项置为null，数组本身大小并不改变，因而当某个HashMap已存储过较大的数据时，调用clear()有些时候不是一个好的做法。
2. Buckets是代码中的table数组，它的每个元素是一个Entry链，所以叫buckets

总结

HashMap.hash(int n)是为了对作为key的对象提供的hashCode()做进一步混淆，增加其“随机度”，试图减少插入hash map时的hash冲突。所谓“hash冲突”就跟下面的indexFor()有关。

HashMap.indexFor(int n, int length)则是根据计算出来的hash值从HashMap的“骨干”——bucket数组（实现为HashMap.Entry数组）找到对应的bucket。由于java.util.HashMap保证bucket数组的长度是2的幂方，所以本来应该写成：
index = n % length

的，变为可以写成：
index = n & (length - 1)

两者在length为2的幂方时等价。

当两个hash值算出同一个index时，就出现了“hash冲突”——两个键值对要被插在同一个bucket里了。常见解法有两种：

* 开放式hash map：用一个bucket数组作为骨干，然后每个bucket上挂着一个链表来存放hash一样的键值对。有变种不用链表而用例如说二叉树的，反正只要是“开放”的、可以添加元素的数据结构就行；

* 封闭式hash map：bucket数组就是主体了，冲突的话就线性向后在数组里找下一个空的bucket插入；查找操作亦然。

java.util.HashMap用的是开放式设计。Hash冲突越多越影响访问效率，所以要尽量避免。

hashcode也取决于VM，有VM用对象内存地址。

HashMap 与 HashTable默认大小的区别:

Hashtable默认大小是11是因为除（近似）质数求余的分散效果好：java - Why initialCapacity of Hashtable is 11 while the DEFAULT_INITIAL_CAPACITY in HashMap is 16 and requires a power of 2Hashtable的扩容是这样做的：

    int oldCapacity = table.length;

    int newCapacity = oldCapacity * 2 + 1;

虽然不保证capacity是一个质数，但至少保证它是一个奇数。Hashtable的寻址是这样做的： Entry tab[] = table;

    int hash = key.hashCode();

    int index = (hash & 0x7FFFFFFF) % tab.length;

直接用key的hashCode()，不像HashMap里为了增强hash的分散效果而要做二次hash（这里例子用JDK6版，老一点方便）：

/**

* 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);

    }

    int hash = (key == null) ? 0 : hash(key.hashCode()); // 二次hash

    table[indexFor(hash, table.length)]

巴特西

HashMap 实现详解

总结

最新文章

热门文章