【转】HashMap源码解读

1、HashMap的存储结构 
2、HashMap的初始化 
3、元素Hash值获取及通过hash值找到talbe下标索引 
4、元素添加方法addEntry 
5、HashMap扩容 
6、老table重新hash成新table 
7、key为null，存到哪去了 
8、查找元素get(Object key) 
9、根据key删除元素 


1、HashMap的存储结构 

  在HashMap的Field中有： 

transient Entry[] table;

  而Entry的定义如下： 

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        final int hash;
 .........
}

简单说就是一个数组+链表，结构如下图： 

 


2、HashMap的初始化 

public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold=(int)(DEFAULT_INITIAL_CAPACITY*DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}

    构造方法中出现的几个关键字段：loadFactor ，threshold，CAPACITY，table 
其中table上面讲了，是HashMap的存储结构。CAPACITY这个是构建HashMap的时候的容量，这里使用了系统默认的初始容量，loadFactor 是加载因子，用处是和CAPACITY相乘获得threshold，这个文档的说明如下：The next size value at which to resize (capacity * load factor)。其实就是HashMap扩容的临界值，超过这个值，则重新扩容。 
    这样就说明了loadFactor 的用处了。这里有人要问了。为什么要这个东西。这里就涉及到HashMap的原理了。HashMap中存储元素的时候，首先得先通过其自己的hash算法找到存储在talbe数组的索引值。但是这个hash算法并不能保证，每一个元素对应不同的talbe数组的索引值，当放入HashMap的元素过多的时候，就容易出现相同的索引值，在算法里叫冲突，这时候元素就会被加到该索引值下的链表当中，这样查找的效率就会大大降低，这显然违背了HashMap快速查找的初衷了。所有HashMap在设计的时候，就是用了这样一个加载因子，如果存储的元素个数占table长度的比例大于loadFactor 加载因子的时候，冲突加剧，这样我们就得扩容解决这样的问题。 
    所以总结影响HashMap效率的两个因素：1.初始容量 2.加载因子。解决的本质无非就是减少hash冲突。 

3、元素Hash值获取及通过hash值找到talbe下标索引 

static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

    这个不深究，结果是获得一个随机点的hash值 

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

    这个就是获得元素对应table下标索引的方法，h是通过上面的hash(int h)方法获得，length是table的长度 

4、元素添加方法addEntry 

void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    if (size++ >= threshold)
        resize(2 * table.length);
}
//Entry的构造方法
Entry(int h, K k, V v, Entry<K,V> n) {
    value = v;
    next = n;
    key = k;
    hash = h;
}

    addEntry方法里出现的几个参数分别是：hash-->元素key的hash值，key，value不用说了，bucketIndex是计算出来的该元素对应的table下标索引。方法的前两句是，根据传入的参数生成一个Entry元素，他的next为现有table[bucketIndex]。 
    说白了就是将新元素加到该元素对应table[bucketIndex]链表的表头。流程如下图： 
 

5、HashMap扩容 

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

在元素添加方法addEntry中，添加完元素后，有下面两行代码： 

if (size++ >= threshold)
    resize(2 * table.length);

    size表示的是HashMap中有多少个元素，当元素的个数超过临界值时，会自动调用扩容方法，可以看出HashMap的扩容是翻番的扩2 * table.length。我们在来看看resize扩容方法。 
    前面几行是判断扩容后是否好过了最大的int值。后面几行是将原来的table中的元素，重新hash放到新的扩容后的table中。可能大家对transfer(newTable)这个方法很困惑。接下来，我们来解读这个方法的实现。 

6、老table重新hash成新table 

void transfer(Entry[] newTable) {
    Entry[] src = table;
    int newCapacity = newTable.length;
    for (int j = 0; j < src.length; j++) {
        Entry<K,V> e = src[j];
        if (e != null) {
            src[j] = null;
            do {
                Entry<K,V> next = e.next;
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            } while (e != null);
        }
    }
}

    这个方法的主要作用就是，将老的table中的所有不为空的元素，重新hash放到新的table中去。估计在do之前的大家能很好理解。就是遍历table中不为空的元素。这时候找出来的e = src[j]是一个Entry链表。所以，如果不为空，还要遍历这个链表中的每一个元素，并将这些元素重新hash到新table中。下面我们对于代码讲解。 
//将第一个元素e后的链表截取出来 
Entry<K,V> next = e.next; 
//找到e对应新table的下标索引 
int i = indexFor(e.hash, newCapacity); 
//将e插入到新table下标索引链表的表头 
e.next = newTable[i]; 
//将该新table下标索引重新定位为e，这样就完成了一个元素的重新hash 
newTable[i] = e; 
//将截取的剩余的链表继续hash 
e = next; 
示意图如下： 
1、Entry<K,V> next = e.next; 
 
2、e.next = newTable[i]; 
 
    即这里的e就是Entry[j]，也就是 
 
3、newTable[i] = e; 
    因为newTable[i]本身是一个指向浅蓝色Entry[i]的引用，这个时候，我们在将这个引用指向红色Entry[j]，这样就完成了老table中一个元素的重新hash到新table中。 
 

7、key为null，存到哪去了 
    在put方法里头，其实第一行就处理了key=null的情况。 

if (key == null)
    return putForNullKey(value);
//那就看看这个putForNullKey是怎么处理的吧。
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;
}

    可以看到，前面那个for循环，是在talbe[0]链表中查找key为null的元素，如果找到，则将value重新赋值给这个元素的value，并返回原来的value。 
    如果上面for循环没找到。则将这个元素添加到talbe[0]链表的表头。 

8、查找元素get(Object key) 

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

    前面两行是找key为null的元素，前面说过，key为null的元素，是放在table[0]这个链表的。所以要找的话，直接到table[0]中查找就行了。 
    如果没找到的话。则根据key的hash值找到元素所在table中下标索引，根据其在找到元素所在链表，在遍历链表，找到该元素并返回其value，否则返回null。 

9、根据key删除元素 

public V remove(Object key) {
    Entry<K,V> e = removeEntryForKey(key);
    return (e == null ? null : e.value);
}
调用的还是下面的方法
final Entry<K,V> removeEntryForKey(Object key) {
        int hash = (key == null) ? 0 : hash(key.hashCode());
        int i = indexFor(hash, table.length);
        Entry<K,V> prev = table[i];
        Entry<K,V> e = prev;
        while (e != null) {
            Entry<K,V> next = e.next;
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) {
                modCount++;
                size--;
                if (prev == e)
                    table[i] = next;
                else
                    prev.next = next;
                e.recordRemoval(this);
                return e;
            }
            prev = e;
            e = next;
        }
        return e;
    }

    这里while循环外面的很好看懂，我们讨论while循环里的。 
Entry<K,V> next = e.next;把原有的链表截出表头元素，然后判断这个表头元素的key是否就是我们要找的key。如果找出的第一个元素就是的话，我们直接将这个链表的第一个元素删除就OK。 
if (prev == e) 
      table[i] = next; 
    如果不是，则遍历这个链表，下图展示了这个过程： 
 
步骤1、初始情况 
Entry<K,V> prev = table[i]; 
Entry<K,V> e = prev; 
 
步骤2、没找到 
Entry<K,V> next = e.next; 
…….. 
prev = e; 
e = next; 
如果e这个元素不是要删除的话，则遍历下一个元素。 
 
步骤3、找到 
prev.next = next; 
return e; 
将prev的下一个元素指向e.next。这样就相当于删除了e 
最后的结果如下：