转载

Java集合系列之---HashMap

先看下HashMap的继承体系，它继承自抽象类AbstractMap，实现了Map、Cloneable、Serializable接口，还有较常用的子类LinkedHashMap也实现了Map接口。

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable{...
public abstract class AbstractMap<K,V> implements Map<K,V> {...
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>{...
复制代码

再看看HashMap的成员变量和一些默认值：

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认的初始化数组大小，16
static final int MAXIMUM_CAPACITY = 1 << 30; // HashMap的最大长度
static final float DEFAULT_LOAD_FACTOR = 0.75f; // 负载因子的默认值
static final Entry<?,?>[] EMPTY_TABLE = {}; // Entry数组默认为空
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE; // Entry数组
transient int size; // map中key-value 键值对的数量
int threshold; // 阈值，即table.length 乘 loadFactor
final float loadFactor; //负载因子，默认值为 DEFAULT_LOAD_FACTOR = 0.75 
transient int modCount; // HashMap结构被修改的次数
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE; // 阈值的默认值
HashMap.Holder.trasient int hashSeed;//翻译过来叫哈希种子，是一个随机数，它能够减小hashCode碰撞
// 的几率，默认为0，表示不能进行选择性哈希（我也不知道是啥意思）
复制代码

所以我们用默认构造方法new 出来的HashMap()，长度默认为16，阈值为12，并且size达到threshold，就会resize为原来的2倍。

再看下HashMap的一些重要的内部类：

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    int hash;
    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }
}
复制代码

Entry实现了Map的内部接口Entry，它有四个属性，key、value、Entry、hash，是HashMap内数组每个位置上真正存放元素的数据结构。

private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
    public Iterator<Map.Entry<K,V>> iterator() {
        return newEntryIterator();
    }
    public boolean contains(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry<K,V> e = (Map.Entry<K,V>) o;
        Entry<K,V> candidate = getEntry(e.getKey());
        return candidate != null && candidate.equals(e);
    }
    public boolean remove(Object o) {
        return removeMapping(o) != null;
    }
    public int size() {
        return size;
    }
    public void clear() {
        HashMap.this.clear();
    }
}
复制代码

EntrySet 继承了AbstractSet，它内部有个迭代器iterator，可以获取Entry对象，方法contains用来判断所给的对象是否包含在当前EntrySet中。

put、get、resize方法源码分析

我们知道HashMap，在jdk1.8之前底层用数组+链表实现的，jdk1.8改成了数组+链表+红黑树实现，以避免长链表带来的遍历效率低问题。

JDK-1.7下的源码

put()方法

public V put(K key, V value) {        
  if (table == EMPTY_TABLE) { // 首先判断数组若为空，则创建一个新的数组
    inflateTable(threshold);
   }
   if (key == null) // 如果key为null，遍历table数组，如果找出key=null的位置，将value覆 
   // 盖，并返回旧的value，否则调用addEntry()将它保存到table[0]位
       return putForNullKey(value);
   int hash = hash(key); // 若key!=null，则计算出hashCode，算出下标 index，遍历table
   int i = indexFor(hash, table.length);
   for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        // 若找到hashCode与当前key的hashCode相等，并且key值也相同，
        // 那就覆盖value的值，并且放回oldValue
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
   }
   modCount++;
   // 若没满足(4）中的条件，则调用方法addEntry(...)
   addEntry(hash, key, value, i); 
        return 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;
}

static int indexFor(int h, int length) {
   // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2"; 
   // 长度必须是2的非零幂
    return h & (length-1); //table数组的下标计算：hashCode与(table数组长度减一)做与(&)运算
}

&运算，即同是1才为1，否则为0
例如：h1=3 h2=20 length=16
     h1:        0011
    h2:       10100
    length-1:  1111
     h1(index): 0011 = 3
    h2(index): 0100 = 4
这样运算得出的index就是舍弃了hashCode一部分高位的hash的值

复制代码

若indexFor计算出来的下标在数组中不为空并且size达到阈值，则扩容，然后在index位置创建一个Entry，将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; // null的hashCode为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++;
}
复制代码

get()方法

public V get(Object key) {
    if (key == null) // 如果key为null，则判断HashMap中是否有值，若没有直接返回null
        return getForNullKey();
    Entry<K,V> entry = getEntry(key); return null == entry ? null : entry.getValue(); 
    // 最后获取Entry的value，并返回
}

private V getForNullKey() { // 若有就遍历table数组，找到null对应的value并返回
    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，则获取Entry，也就是一个遍历table数组命中的过程
final Entry<K,V> getEntry(Object key) { 
    if (size == 0) {
        return null;
    }
    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;
}
复制代码

resize()方法

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
// 首先将当前对象的一些属性保存起来，如果当前HashMap的容量达到最大值，那就无法扩容了，将阈值 
// 设置为Integer的最大值并结束方法
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    
// 否则创建新的Entry数组，长度为newCapacity，在addEntry()方法中，
// 我们知道 newCapacity = 2  * table.length
    Entry[] newTable = new Entry[newCapacity]; 
    
// 然后调用transfer()方法，此方法的作用是将当前数组中的Entry转移到新数组中
    transfer(newTable, initHashSeedAsNeeded(newCapacity)); 
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
复制代码

在存入key-value时会调用initHashSeedAsNeeded()方法判断是否需要rehash，该方法的过程见注释，好吧，我也不知道为什么这样处理得出的结果就能判断是否需要rehash，后面就是根据rehash重新计算下标，并将key-value存入新的table中。

/**
 * Transfers all entries from current table to newTable.
 */
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    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.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}
/**
 * Initialize the hashing mask value. We defer initialization until we really need it.
 */
final boolean initHashSeedAsNeeded(int capacity) { 
    boolean currentAltHashing = hashSeed != 0; // 当前哈希种子是否为0
    boolean useAltHashing = sun.misc.VM.isBooted() && 
                 // 虚拟机是否启动，当前数组容量是否大于阈值
                (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    boolean switching = currentAltHashing ^ useAltHashing; // 做异或运算
    if (switching) { 
        // 重置哈希种子
        hashSeed = useAltHashing ? sun.misc.Hashing.randomHashSeed(this) : 0; 
    }
    return switching; // 返回异或运算的结果，作为是否rehash的标准
}
复制代码

JDK-1.8下的源码

jdk1.8中将Entry改为Node节点来实现的，属性都是一样的。

put()方法

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
 }

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    
    // 如果数组是null或者数组为空，就调用resize()进行初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length; 
        
        // （n-1）&hash 算出下表，这个和1.7是一样的
    if ((p = tab[i = (n - 1) & hash]) == null)
    
    // 如果当前计算出来的位置为null，就新建一个节点
        tab[i] = newNode(hash, key, value, null);  
    else {
        Node<K,V> e; K k;
        if (p.hash == hash && ((k = p.key) == key || 
        
    // 若计算出来的位置上不为null，它和传入的key相比，hashCode相等并且key也相等
    (key != null && key.equals(k))))
    // 那么将p赋给e
      e = p; 
        
        // 如果p是树类型
        else if (p instanceof TreeNode) 
        
            // 则按照红黑树的结构存入进去
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); 
        else {
        
            // 遍历p，p是链表
            for (int binCount = 0; ; ++binCount) { 
            
                // 如果p的下一个节点是尾节点（尾节点.next=null）
                if ((e = p.next) == null) {
                
    // 在p的后面创建一个节点，存放key/value（尾插法，多线程并发不会形成循环链表）
                    p.next = newNode(hash, key, value, null); 
                    
// TREEIFY_THRESHOLD =  8，即当binCount达到7时转换成红黑树数据结构，因为binCount是从0开始 
// 的，达到7时p链表上就有8个节点了，所以是链表上达到8个节点时会转变成红黑树。
                    if (binCount >= TREEIFY_THRESHOLD - 1) 
                    
                // 这里先就不展开了，红黑树不会，有时间再研究
                        treeifyBin(tab, hash); 
                    break;
                }
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                    
// 若上面两个条件都不满足，此时e=p.next，也就是将p的下一个节点赋给p，进入下一次循环
                p = e; 
            }
        }
// existing mapping for key，jdk这段注释意思是存在key的映射，我的理解是传入的key 在p位置找 
// 到它自己的坑被别人占了
        if (e != null) { 
            V oldValue = e.value;
            
            // 下面就是将value存入被占的位置，并将旧的value返回
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e); 
            return oldValue;
        }
    }
    
    // 修改次数加一
    ++modCount; 
    
    // 若已有的键值对数大于阈值，就扩容
    if (++size > threshold) 
        resize();
    afterNodeInsertion(evict);
    return null;
}
复制代码

put方法流程图如下：

get()方法

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}
复制代码

get()方法也没什么，就是根据key的hashCode算出下标，找到对应位置上key与参数key是否相等，hash是否相等，如果是树就获取树的节点，如果是链表就遍历直到找到为止，找不到就返回null。

resize()方法

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table; 
    
    // oldCap就是原数组的长度
    int oldCap = (oldTab == null) ? 0 : oldTab.length; 
    
    // 原阈值
    int oldThr = threshold; 
    int newCap, newThr = 0;
    if (oldCap > 0) { 
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                  oldCap >= DEFAULT_INITIAL_CAPACITY)
                  
            // double threshold 扩容成两倍
            newThr = oldThr << 1; 
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
// zero initial threshold signifies using defaults, 这里表示初始化resize的另一个作用
    else {       
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    
        // 创建新数组，容量为原数组的两倍
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; 
        
    // 将它指向table变量
    table = newTab; 
    if (oldTab != null) {
    
        // 遍历原数组
        for (int j = 0; j < oldCap; ++j) { 
            Node<K,V> e;
            
            // 将不为null的j位置的元素指向e节点
            if ((e = oldTab[j]) != null) { 
                oldTab[j] = null;
                if (e.next == null)
                
    // 若e是尾节点，或者说e后面没有节点了，就将e指向新数组的e.hash&(newCap-1)位置
                    newTab[e.hash & (newCap - 1)] = e; 
                    
                else if (e instanceof TreeNode)
                
                    // 如果是树节点，就按红黑树处理，这里不展开
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); 
                else { // preserve order
                
                    // 存放新数组中原位置的节点，这里后面展开说
                    Node<K,V> loHead = null, loTail = null; 
                    
                    // 存放新数组中原位置+原数组长度的节点
                    Node<K,V> hiHead = null, hiTail = null; 
                    Node<K,V> next;
                    do {
                        next = e.next;
                        
                        // e.hash&oldCap 的值要么是0要么是oldCap ###
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                            // 第一次进来，先确定头节点，以后都走else，loHead指向e
                                loHead = e; 
                            else
                            
// 第二次进来时loTail的next指向e(e=e.next)，注意此时loHead的地址和loTail还是一样的，
// 所以loHead也指向e，也就是说e被挂在了loHead的后面（尾插法，不会形成循环链表），
// 以此类推，后面遍历的e都会被挂在loHead的后面。
                               loTail.next = e;
                               
// loTail指向e,第一次进来时头和尾在内存中的指向是一样的都是e，第二次进来时，
// loTail指向了e(e=e.next)，这时和loHead.next指向的对象是一样的，所以下一次
// 进来的时候loHead可以找到loTail.next，并将e挂在后面。
// 这段不明白的可以参考：https://blog.csdn.net/u013494765/article/details/77837338。
                            loTail = e;  
                        }
                        else { // 和if里面的原理是一样的
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) { 
                        loTail.next = null;
                        newTab[j] = loHead; // 将loHead节点存到新数组中原下标位置
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        // 将hiHead节点存到新数组中 [原下标+原数组长度] 的位置
                        newTab[j + oldCap] = hiHead; 
                    }
                }
            }
        }
    }
    return newTab;
}
复制代码

这里争对 ### 标注的代码详细讲下：

为什么(e.hash&oldCap) == 0为true或false就能判断存放的位置是newTab[原下标]，还是newTab[原下标+原数组长度]，而不用像jdk1.7那样每次都要rehash？