Java Core系列之HashMap实现

最近在看guava中的cache的源码，它的实现基于concurrenthashmap，前段时间组里招人，据说很多看起来很牛掰的简历，一个hashmap就能刷掉很多，所以顺便把hashmap和concurrenthashmap的源码复习一遍。先从hashmap开始（另：hashtable是hashmap的线程安全版本，它的实现和hashmap实现基本一致，除了它不能包含null值的key和value，并且它在计算hash值和数组索引值的方式要稍微简单一些。对于线程安全的实现，hashtable简单的将所有操作都标记成synchronized，即对当前实例的锁，这样容易引起一些性能问题，所以目前一般使用性能更好的concurrenthashmap）。

map是对键值对存储的抽象，因而其最主要的方法有：

1. 添加新的键值对(key,value)；

2. 通过键(key)查找关联的值(value)；

3. 通过键(key)移除关联的值(value)；

4. 判断键(key)或值(value)的存在性。

其他的方法有：判断键值对的空属性以及目前的键值对数，获取所有键、所有值或者所有键值对的集合，批量添加，清除所有键值对等。在map中，一个键值对用entry接口来表示。因而在java中，对map接口的定义如下：

public interface map<k,v> {

    boolean isempty();

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

    interface entry<k,v> {

        k getkey();

        v getvalue();

        v setvalue(v value);

        boolean equals(object o);

        int hashcode();

    }

    boolean equals(object o);

    int hashcode();

}

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作为初始值，不了解这些算法的具体缘由，就这样浅尝辄止了。

    final int hash(object k) {

        int h = 0;

        if (usealthashing) {

            if (k instanceof string) {

                return sun.misc.hashing.stringhash32((string) k);

            }

            h = hashseed;

        }

        h ^= k.hashcode();

        h ^= (h >>> 20) ^ (h >>> 12);

        return h ^ (h >>> 7) ^ (h >>> 4);

    static int indexfor(int h, int length) {

        return h & (length-1);

同样在上述的数据结构书中关于冲突处理提供了几个方法：1. 开放定址法；2. 再哈希法；3.链地址法；4. 建立一个公共溢出区法。在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实现，实现比较简单，不细讲。

注：clear()操作引起的内存问题-由于clear()操作只是将数组中的所有项置为null，数组本身大小并不改变，因而当某个hashmap已存储过较大的数据时，调用clear()有些时候不是一个好的做法。

最后吐槽一下，即使jdk内部的hashmap也有很多的代码重复。。。。。