2016-06-28

集合容器学习之HashMap

无论在面试还是应用中，HashMap都是一个很重要的知识点。作为一个容器，HashMap具有优秀的性能，应用十分广泛。同时，HashMap的知识点具有一定的深度，可以考察一定的水平。此外，ConcurrentHashMap等同步集合的引入让HashMap更加复杂。我们需要认真地学习这个容器。我的机器安装的是JDK1.7，所以暂时以1.7为标准来进行学习。后面会继续在学习JDK1.8的HashMap。

HashMap源码解析

初探HashMap

eclipse中观察的HashMap结构
我们可以观察到，键值对储存在table这个数据结构当中。再往下看，可以发现每个node具有key、value、hash、next这几个内容，和链表非常相似。而前面的[]标号是什么呢？其实，HashMap是不同哈希值的桶中存放单链表来保存数据来实现的。
官方文档是这样描述HashMap的：

Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

我们要注意几个关键的信息：基于Map接口实现、允许null键/值、非同步、不保证有序(比如插入的顺序)、也不保证序不随时间变化。

两个重要的参数

HashMap有两个非常重要的参数： 容量(Capacity) 和 负载因子(Load factor) 。API中这样说：

Initial capacity The capacity is the number of buckets in the hash table, The initial capacity is simply the capacity at the time the hash table is created.
Load factor The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased.

简单的说，Capacity就是bucket的大小(即哈希组的长度)，Load factor就是bucket填满程度的最大比例。如果对迭代性能要求很高的话不要把capacity设置过大，也不要把load factor设置过小。当bucket中的entries的数目大于capacity*load factor时就需要调整bucket的大小为当前的2倍。
源码是这样初始化这两个参数的：

1
2
3

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;

从这里可以看出，初始容量是16，负载因子是0.75，最大容量是2^30。对于负载因子，如果负载因子越大，对空间的利用会更充分，但是查找效率会降低（链表长度会越来越长）；如果加载因子太小，那么表中的数据将过于稀疏（很多空间还没用，就开始扩容了），对空间造成严重浪费。如果我们在构造方法中不指定，则系统默认加载因子0.75是一个比较理想的值，一般情况下我们是无需修改的。此外，无论我们指定的容量为多少，构造方法都会将实际容量设为不小于指定容量的2的次方的一个数，即最大值不能超过2的30次方。

HashMap的构造方法

Hashcode有4个构造方法，但其实内部都是实现了

1	public HashMap(int initialCapacity, float loadFactor) {}

这个方法。不同的是分别允许客户端更改初始容量和负载因子。

链表节点的数据结构

我们首先来看一看链表Entry的数据结构：

//Entry是单向链表。HashMap链式储存使用的就是这个链表。
//实现了Map.Entry<K,V>这个接口，即get、put方法等
static class Entry<K,V> implements Map.Entry<K,V> {
    //链表内四个属性：键、值、哈希值、下一节点
    final K key;
    V value;
    Entry<K,V> next;
    int hash;

    //Constructor
    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }

    public final K getKey() {
        return key;
    }

    public final V getValue() {
        return value;
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    //判断两个Entry是否相等
    public final boolean equals(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry e = (Map.Entry)o;
        Object k1 = getKey();
        Object k2 = e.getKey();
        if (k1 == k2 || (k1 != null && k1.equals(k2))) {
            Object v1 = getValue();
            Object v2 = e.getValue();
            if (v1 == v2 || (v1 != null && v1.equals(v2)))
                return true;
        }
        return false;
    }

    //实现hashcode
    public final int hashCode() {
        return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
    }

    public final String toString() {
        return getKey() + "=" + getValue();
    }

    //当向HashMap添加元素时会调用这个方法，而在此不做处理
    void recordAccess(HashMap<K,V> m) {
    }

    //删除元素的方法
    void recordRemoval(HashMap<K,V> m) {
    }
}

Entry的结构相对简单。内部重写了equals方法和hashcode方法。

get方法的实现

对于HashMap，最重要的逻辑特性大概就是存和取了。因此，我们接下来就开始学习get和put方法。先从简单一点的get开始：

public V get(Object key) {
    if (key == null)
        return getForNullKey();
    Entry<K,V> entry = getEntry(key);
    return null == entry ? null : entry.getValue();
}

final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
        return null;
    }
    //获取key的hash值
    int hash = (key == null) ? 0 : hash(key);
    //在该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;
}
//获取key值为null的元素，HashMap将key为null的元素储存在table[0]的位置。
private V getForNullKey() {
    if (size == 0) {
        return null;
    }
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null)
            return e.value;
    }
    return null;
}

如果key为null，则直接从hash表第一个位置table[0]的链表进行查找。否则，先求出对应的hash值，然后根据hash值在table中找到所在链表，然后在链表中查找是否有键值对应的key与目标key相等。

put方法

put方法比较复杂，代码如下：

public V put(K key, V value) {
	//如果table为空，初始化
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    if (key == null)
        return putForNullKey(value);
    //如果key不是null，计算key的哈希值，并插入到该哈希值对应的链表中
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        //如果key值重复，那么更新value，并返回旧value
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    //如果key值是一个新值，则添加到对应的table中
    //addEntry方法会检测是否达到负载系数，达到了就会扩容
    addEntry(hash, key, value, i);
    return null;
}
//对key=null的处理办法
private V putForNullKey(V value) {
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    addEntry(0, null, value, 0);
    return null;
}
//添加新key-value对的方法
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);
}
//增加新的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);
    size++;
}

put的思路大概是这样的：

检测key是否为null，如果是则使用单独方法；
计算key的hash值，并找到对应的table链表；
遍历table链表，查找是否已经存在对应的key值；
如果已经存在key值，则更新value并返回原value；
否则向table链表中增加新的key；
如果此时达到负载因子，则进行扩容。

resize方法

resize扩容方法非常重要。我们知道，初始的最大容量默认是16，而负载系数是0.75，那么HashMap中最多可以存放12个元素。如果超过12个元素怎么办？这时候就需要对map的容量进行扩容。在put方法中接触到了扩容，现在就来看看具体是如何实现的：

//重新调整HashMap大小，newCapacity是调整后的大小
void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    //新建一个HashMap，将原HashMap中的元素添加到新的之中，然后新的替换旧的
    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

可以看出，新建了一个HashMap底层数组，然后调用transfer方法，将HashMap的全部元素添加到新的HashMap中。而且重要的一点是，添加的过程中需要重新计算元素在新的数组中的索引位置。transfer源码：

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    //依次对每个链表进行遍历，并将元素放入新的HashMap中
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            //将e放到newTable[i]链表最前，然后将e.next重新赋值为e
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

transfer这一过程需要遍历所有的元素，如果HashMap中储存很多元素，那么这一过程将会非常的耗时。所以，在使用HashMap前最好对元素数量有一个大致的估计，这样可以减少频繁扩容导致的性能损耗，提高性能。

containsKey和containsValue方法

HashMap利用hash存储数据，containsKey方法直接在对应的table链表中依次查找数据。而containsValue则不然，并没有合适的机制能直接定位到value的地方，所以只能对整个HashMap进行遍历来寻找目标元素。

求hash值和索引值的方法

以上几个重点基本上涵盖了HashMap的基本用法。最核心的利用散列表求hash值和求索引值的方法我们放的最后来学习。
计算哈希值的方法如下：

final int hash(Object k) {
	//判断哈希种子是否为0，如果不是则重新设置
    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);
}

这是一个哈希算法，可以使得哈希值分布比较均匀。在此我们看到了大量的位操作，这是因为位操作效率很高。
由哈希值查找索引的方法如下：

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

一般来说，对于哈希表的散列运算我们都会想到利用hash对length取模，这种方法会使得哈希表比较均匀。但取模是除法运算，效率很低，而与操作完全可以取代除法，同样实现均匀的散列，但效率高了许多。
此外，从这里我们也可以看出为何容量要取到2的整数倍了。2的整数倍的2进制表示是100…，减一后变为111…，与哈希值相与能准确的取到后几位，即保证散列的均匀，又可以保证效率。如果容量用普通的数字，那么与操作会产生若干个0，那么这一位的空间就浪费了。因此，length取2的整数幂，是为了使不同hash发生碰撞的概率减小，同时保证效率最优。

参考HashMap源码剖析

JDK1.8中的HashMap

JDK1.8对HashMap有很大的修改，最主要的部分就是当table链表达到一定的长度(默认为8)，就将其转变为红黑树。利用红黑树快速增删改查的特点提高HashMap的性能，其中会用到红黑树的插入、删除、查找等算法。

关于哈希运算

1.8中哈希算法是这样的：

static final int hash(Object key) {
    int h;
    //首先赋值，h = key.hashCode()，然后高位运算
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//接下来调用老方法，取后几位
return h & (length-1);

从这里可以看出，1.8哈希算法与1.7略有不同，简化了哈希运算，通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。
举例说明运算过程

put和get方法

这是put方法的图解，可以发现与JDK1.7没有太大的变化，每次都判断是否为红黑树以及是否需要将链表转为红黑树。
put图解
get方法也是融入了红黑树元素，每次取值进行判断。此外，与旧方法没多大区别。

resize扩展方法

JDK1.8对resize进行了很大的优化。首先我们观察扩容时的状态：
resize扩容
HashMap扩容是二次幂扩展，所以，扩展后的元素要么不变，要么比原来多了前面的1位。看图说话，n是table的长度，图（a）表示扩容前的key1和key2两种key确定索引位置的示例，图（b）表示扩容后key1和key2两种key确定索引位置的示例，其中hash1是key1对应的哈希与高位运算结果。
元素在重新计算hash之后，因为n变为2倍，那么n-1的范围在高位多1bit(红色)，因此新的index就会发生这样的变化：

因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。
这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的table了。这一块就是JDK1.8新增的优化点。有一点注意区别，JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，但是JDK1.8不会倒置。JDK1.8的resize源码，写的非常漂亮，这里就不贴了，可以在源码学习。

参考Java8系列之重新认识HashMap

小结

扩容是一个特别耗性能的操作，所以使用HashMap的时候，估算map的大小，初始化的时候给一个大致的数值，避免map进行频繁的扩容。
负载因子是可以修改的，也可以大于1，但是建议不要轻易修改，除非情况非常特殊。
HashMap是线程不安全的，不要在并发的环境中同时操作HashMap，建议使用ConcurrentHashMap。
JDK1.8引入红黑树大程度优化了HashMap的性能。

这里有一些比较经典的题目，可以快速回想HashMap的知识点：

什么时候会使用HashMap？有什么特点？
是基于Map接口的实现，存储键值对时，它可以接收null的键值，是非同步的，HashMap存储着Entry(hash, key, value, next)对象。
你知道HashMap的工作原理吗？
通过hash的方法，通过put和get存储和获取对象。存储对象时，我们将K/V传给put方法时，它调用hashCode计算hash从而得到bucket位置，进一步存储，HashMap会根据当前bucket的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)。获取对象时，我们将K传给get，它调用hashCode计算hash从而得到bucket位置，并进一步调用equals()方法确定键值对。如果发生碰撞的时候，Hashmap通过链表将产生碰撞冲突的元素组织起来，在Java 8中，如果一个bucket中碰撞冲突的元素超过某个限制(默认是8)，则使用红黑树来替换链表，从而提高速度。
你知道get和put的原理吗？equals()和hashCode()的都有什么作用？
通过对key的hashCode()进行hashing，并计算下标( n-1 & hash)，从而获得buckets的位置。如果产生碰撞，则利用key.equals()方法去链表或树中去查找对应的节点
你知道hash的实现吗？为什么要这样实现？
在Java 1.8的实现中，是通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在bucket的n比较小的时候，也能保证考虑到高低bit都参与到hash的计算中，同时不会有太大的开销。
如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？
如果超过了负载因子(默认0.75)，则会重新resize一个原来长度两倍的HashMap，并且重新调用hash方法。

other

看源码的过程中，经常看到这样的赋值手段：

null == a

感觉很别扭。后来查了查，原来是这样：a == null这种写法偶尔会写成 a = null，出错了也很难查出来。而将常量放在前面，编译器就会检查出来错误。这是一个良好的编程习惯。