Liuxboy

1、JDK中HashMap类的说明

JDK7.0中HashMap的doc
public class java.util.HashMap<K, V>
extends java.util.AbstractMap<K, V>
implements java.util.Map<K, V>, java.lang.Cloneable, java.io.Serializable

Hash table是基本Map接口的实现。该实现提供了map的可选所有操作，也允许空value和空key，(HashMap类相当于HashTable类，除了它是非同步的且允许空value与空key)。这个类不保证映射的顺序；特殊情况下，也不保证映射的顺序不会随着时间变化。假设hash函数在槽中尽可能地打散各元素，则该实现对于基本操作(put和get)提供的运行时间是常量。遍历集合的时间取决于HashMap的容积(槽的数量)与映射元素的数量的乘积(key-value对的数量)。因此，如果很看重其遍历效率的话，就不应该在初始化时，将容积设得太高(或者装载因低)，这点很重要。

一个HashMap实例有两个参数影响其性能：初始容积与装载因子。容积是hash表中槽的数量，初始容积就是当hash表刚创建时的容积。装载因子是衡量hash表允许装多满的一个尺度，便于在hash表的容积可以得到自动增加。当槽中的实体数量超过装载因子允许的范围或者当前的容积，这个hash表会重新hash一次(那即是，内建的数据结构会重建)以使得这个新hash表大致相当于原hash表的两倍。

作为一个普遍的准则，默认的装载因子是0.75，能在时间和空间花费上提供一个较好折中方案的。减少空间花费更具价值，但又增加了查询的代价(这一点反应在绝大多数HashMap类的操作中，包括get和put)。在设置映射的初始容量时，映射中的预计实体数量和装载因子应慎重考虑，以减少rehash操作的次数。如果初始化容量比实体数量的最大值除以装载因子还要大，那rehash操作就不必发生。如果许多映射都由HashMap实例装填，创建一个足够容量的HashMap，这比起当表需要增长时，让其自动执行rehash来说，映射会被装填得更有效率。

需要注意的是，HashMap是非同步的。如果多线程同时访问HashMap的话，且其中至少一个线程结构性的修改map，那必须在外部加上同步(synchronized)控制。(一个结构性的修改指任何添加或者删除一个或多个映射；仅仅改变该实体包含的key对应的值，这不叫结构性改变。) 对对象的自然封装，这是一种典型的成熟的同步方法，如果没有这种对象存在，这个映射应该用Collections.synchronizedMap方法进行封装。在某些情况下这是最好的办法，为了保护非同步访问map不发生意外： Map m = Collections.synchronizedMap(new HashMap(…)); 类所有的"集合视图方法"所返回的迭代器都具有fail-fast特性：当迭代器被创建好后，如果map在任何时候被结构性地改变，除了这个迭代器自身的remove方法之外的其他任何形式，都会抛出ConcurrentModificationException。因此，在面对并发修改时，这个迭代器是最快且最干脆地发出失败信号的，而不必为将来在某个不确定的时间的某个不确定行为进行冒险。

注意迭代器的fail-fast行为并不能保证这种情形，一般说来，在面对不同步的并发修改时，要做出绝对保证，这是不可能的。 Fail-fast迭代器在最优的基础上抛出 ConcurrentModificationException。所以，依赖于这个异常的正确性去编程也是错误的：迭代器的fail-fast行为只能用在探测bugs时。

2、HashMap结构

1、首先看Entity<K, V>，Entity<K，V>是实现了Map接口里的Entity<K，V>接口：

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    int hash;
    /**
    * Creates new entry.
    */
    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }
    ... ...
}

有四个属性：key, value, next, hash。其中key是final类型的，因为Map最重要的就是key，key决定值，且是唯一的不允许重复。再来看看最重要的equals方法，决定两个实体是否相等。

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

从该方法来看，是典型的判断对象相等的方法：首先判断比较对象是否是Map.Entity的实例，然后再与被比较key与value比较，重用了对象的 equals()方法。

2、再看HashMap的结构。

public HashMap(int initialCapacity, float loadFactor){
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
    //Find a power of 2 >= initialCapacity
    int capacity = 1;
    while (capacity < initialCapacity)
        capacity <<= 1;
    this.loadFactor = loadFactor;
    threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];
    useAltHashing = sun.misc.VM.isBooted() && (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    init();
}

首先判断传入的两个参数是否合法，其中声明了一个局部变量capacity初始值为1，如果传入的参数initialCapacity大于1,则将capacity左移，直到 capacity等于或大于传入参数initialCapacity，那么此时的capacity为大于或等于initialCapacity的2次幂，将装载因子修改为传入的参数loadFactor。最后，新建一个Entity数组，长度为capacity赋值给table(最终存储对象的Hash表)。

其它两个构造函数为HashMap()和HashMap(int initialCapacity)都是初始化成默认的长度(16),默认的装载因子0.75

3、再看HashMap中重要的两个方法，put和get

先来看put(K key, V value)方法

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        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++;
    addEntry(hash, key, value, i);
    return null;
}

首先判断是否为空key，是则调用专门处理key为null的情况；其次，计算key的hash值和该hash值在table中的index(其实就是返回hash & (length-1);)，遍历table[i]槽位处的链表，看是否有相同的Key,Value实体。如果有，则覆盖之，并返回旧值，否则计数加1，并添加新Entry，其方法为addEntry()，具体实现如下：

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

检查size是否大于了预定义的装载尺寸(capacity*loadFactor)，而table[index]处是否不为空，如果都满足，则需要重新构造HashMap,调用resize() 重新扩充至hash表两倍长度，重新将Key的hash值与换算成table中的index；如果不满足，则直接创建Entry

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];
    boolean oldAltHashing = useAltHashing;
    useAltHashing |= sun.misc.VM.isBooted() &&
        (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    boolean rehash = oldAltHashing ^ useAltHashing;
    transfer(newTable, rehash);
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

重新拓展HashMap的空间，如果oldCapacity已经为2的30次方了，则直接将下一次将要拓展的尺寸调到int的最大范围，然后以新的capacity长度新建一个table，将当前hash表中的Entry传送到新建的hash表中

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

直接在table[bucketIndex]处新建一个Entry，size加1.

再看get(K key)方法：

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

    return null == entry ? null : entry.getValue();
}

先依然是判断是否key是否为null，如果是则返回getForNullKey(),然后调用getEntry(key)，判断其结果是否为null，是则返回null，否则返回该Entry的value

private V getForNullKey() {
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null)
            return e.value;
    }
    return null;
}

key为null的Entry都是放在table[0]这个槽中，遍历链表，返回key为null对应的value，否则返回null

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

计算key的hash，然后计算从table槽中的Entry开始遍历链表，如果遍历到某个Entry的hash跟key的hash相等，且其key与参数key相等，则返回该Entry的value, 否则循环完成后仍没有返回，则返回null

Liuxboy

while(true) coding

HashMap详解

1、JDK中HashMap类的说明

2、HashMap结构