一篇文章深入理解 JDK7 HashMap

int index = HashCode(key) % Array.length

// 该构造方法是第二第三构造方法的底层实现，该构造方法对初始化容量和负载因子进行了一个校验// 然后将传入的负载因子复制给了loadFactor成员变量// 将初始化容量赋值给了扩容阈值（扩容临界数值）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);
    this.loadFactor = loadFactor;    threshold = initialCapacity;    init();}
// 指定容量来创建HashMap对象，该变量initialCapacity不一定是初始化哈希表的长度public HashMap(int initialCapacity) {    this(initialCapacity, DEFAULT_LOAD_FACTOR);}
// 使用默认的容量16和默认的负载因子0.75f来创建HashMap对象public HashMap() {    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);}
// 传入一个Map将其转化为HashMappublic HashMap(Map<? extends K, ? extends V> m) {	// 创建一个HashMap    this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,                  DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);    // 初始化HashMap，重点方法，后面详细介绍    inflateTable(threshold);	// 将Map转化为HashMap的具体实现    putAllForCreate(m);}

private void inflateTable(int toSize) {    // 计算大于toSize的且最接近toSize的2的N次幂    // 比如toSize=27，那么大于27且最接近27的2的N次幂是32，N=5    int capacity = roundUpToPowerOf2(toSize);
	// 这里重新计算了threshold，由代码可知，threshold = capacity * loadFactor    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);    // 初始化了哈希表（桶数组）    table = new Entry[capacity];    initHashSeedAsNeeded(capacity);}
private static int roundUpToPowerOf2(int number) {    // assert number >= 0 : "number must be non-negative";    return number >= MAXIMUM_CAPACITY            ? MAXIMUM_CAPACITY            : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;}

// 这就是将指定Map转换为HashMap的方法，循环遍历，主要看下面的putForCreate方法private void putAllForCreate(Map<? extends K, ? extends V> m) {    for (Map.Entry<? extends K, ? extends V> e : m.entrySet())        putForCreate(e.getKey(), e.getValue());}

private void putForCreate(K key, V value) {	// 计算hash值，如果key==null，那么hash值为0    int hash = null == key ? 0 : hash(key);    // 利用hash值和哈希表长度计算当前k-v应在数组的索引下标    int i = indexFor(hash, table.length);
   	// 由于table[i]处可能不止有一个元素（多个会形成一个链表），因此，此处写这样一个循环遍历链表    // 当key存在的时候，直接将key的值设置为新值    for (Entry<K,V> e = table[i]; e != null; e = e.next) {        Object k;        if (e.hash == hash &&            ((k = e.key) == key || (key != null && key.equals(k)))) {            e.value = value;            return;        }    }
	// 当key在当前数组和所有链表中不存在的时候，就在table的指定位置创建一个Entry    createEntry(hash, key, value, i);}
void createEntry(int hash, K key, V value, int bucketIndex) {	// 获取当前数组的Entry链表头节点，并赋值给Entry<K,V> e    Entry<K,V> e = table[bucketIndex];    // 创建一个新的Entry节点对象，并作为新的头节点，将老的头节点赋值给新头节点的next属性    // 这一点很重要，可以看Entry的构造方法，这表明了JDK7是头节点插入链表    table[bucketIndex] = new Entry<>(hash, key, value, e);    // Entry对象数量+1    size++;}

public V put(K key, V value) {	// 首先判断哈希表table是否是空表，第一次put的时候，必然是空表，那么就进行初始化	// 如果我们使用的是HashMap的无参构造方法创建的对象，那么threshold就是16，	// 上面已经分析过inflateTable方法了，它主要是计算了最合适的capacity=16，threshold=12	// 并创建了一个新的Entry<K, V>[16]赋值给了table，也就是开辟了内存空间	// 从第二次put开始，table就不再是空数组了    if (table == EMPTY_TABLE) {        inflateTable(threshold);    }    // 判断key是否为null，如果为null，那么就执行存储key为null的逻辑，后续分析putForNullKey方法    if (key == null)        return putForNullKey(value);    // 计算key的hash值    int hash = hash(key);    // 根据hash值和哈希表长度来计算当前K-V在哈希表中的索引下标    int i = indexFor(hash, table.length);    // 找到下标之后，获取当前下标对应的是否有Entry对象，如果有，那么就遍历这个链表    // 判断链表中是否已经包含当前key了，如果包含，那么就将key对应的值替换成新值，并返回旧值    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;        }    }	// 能运行到这一步，说明上述链表不存在或者链表中没有对应的key	// 那么就需要添加新的Entry对象到指定的索引位置i上	// 记住这里也是头节点插入    modCount++;    // 新增Entry，不仅新增，而且还担任了扩容的担子，后续详细分析    addEntry(hash, key, value, i);    // 新增Entry对象，返回null    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;}

void addEntry(int hash, K key, V value, int bucketIndex) {	// 扩容的条件：1. size >= threshold	// 2. null != table[bucketIndex]	// 两个条件同时满足才会进行扩容    if ((size >= threshold) && (null != table[bucketIndex])) {    	// 扩容为原来容量的两倍，具体代码后续分析        resize(2 * table.length);        // 重新计算当前要新增的K-V对在新的哈希表中的索引位置        hash = (null != key) ? hash(key) : 0;        bucketIndex = indexFor(hash, table.length);    }
	// 创建Entry对象，并插入到指定位置的头节点    createEntry(hash, key, value, bucketIndex);}

void resize(int newCapacity) {    Entry[] oldTable = table;    int oldCapacity = oldTable.length;    // 如果老数组的容量达到了最大，那么就将threshold设置为最大值，且不会再发生扩容    if (oldCapacity == MAXIMUM_CAPACITY) {        threshold = Integer.MAX_VALUE;        return;    }
	// 创建一个新的哈希表，容量是原来哈希表的两倍，也就是newCapacity = 2 * oldCapacity    Entry[] newTable = new Entry[newCapacity];    // 将重新计算所有Entry对象的下标，并重新排列各个Entry对象的位置，稍后分析transfer方法实现    transfer(newTable, initHashSeedAsNeeded(newCapacity));    table = newTable;    // 重新计算新的扩容阈值threshold    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);}

void transfer(Entry[] newTable, boolean rehash) {    int newCapacity = newTable.length;    // 遍历老的table，遍历到每一个bucket的时候，都会将bucket上链表的节点都遍历一遍    for (Entry<K,V> e : table) {        while(null != e) {            Entry<K,V> next = e.next;            // 重新计算hash            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;        }    }}

public V get(Object key) {	// 首先判断key是否为null，如果为null，那么直接获取哈希表的下标为0的位置的Entry对象    if (key == null)        return getForNullKey();        // 当key != null，命中到哈希表中的某个下标位置后，遍历链表来获取key相同的entry对象    Entry<K,V> entry = getEntry(key);
	// 处理结果并返回，如果找到就返回对应的值，如果没有匹配到直接返回null    return null == entry ? null : entry.getValue();}
// 处理key = null的值问题private V getForNullKey() {    if (size == 0) {        return null;    }    // 返回哈希表中下标为0的Entry对象并处理返回结果    for (Entry<K,V> e = table[0]; e != null; e = e.next) {        if (e.key == null)            return e.value;    }    return null;}
// 遍历链表匹配到相同key的Entry对象并返回该Entry对象的value值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;}

Map<String, String> map = new HashMap<>(16);Iterator<Map.Entry<String, String>> iterator = map.entrySet().iterator();while (iterator.hasNext()) {    Map.Entry<String, String> next = iterator.next();    System.out.println(next.getKey() + ":" + next.getValue());}

Map<String, String> map = new HashMap<>(16);for (Map.Entry<String, String> entry : map.entrySet()) {    System.out.println(entry.getKey() + ":" + entry.getValue());}

Map<String, String> map = new HashMap<>(16);map.forEach((key, value) -> System.out.println(key + ":" + value));

Map<String, String> map = new HashMap<>(16);Iterator<String> keyIterator = map.keySet().iterator();while (keyIterator.hasNext()) {    String key = keyIterator.next();    System.out.println(key + ":" + map.get(key));}