JDK源码分析(三)——HashMap 上（基于JDK7） (3)

  构造方法HashMap(Map<? extends K, ? extends V> m)调用的是putAll方法，putAll方法把传入的Map对象保存的元素插入到HashMap里面。

public void putAll(Map<? extends K, ? extends V> m) { int numKeysToBeAdded = m.size(); if (numKeysToBeAdded == 0) return; //如果Map包含的键值对个数大于thrshold,先扩容 if (numKeysToBeAdded > threshold) { int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1); if (targetCapacity > MAXIMUM_CAPACITY) targetCapacity = MAXIMUM_CAPACITY; int newCapacity = table.length; while (newCapacity < targetCapacity) newCapacity <<= 1; if (newCapacity > table.length) resize(newCapacity); } //调用put方法将键值对放入HashMap总 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) put(e.getKey(), e.getValue()); } 扩容 resize(int newCapacity)

  risize扩容方法没有访问修饰符修饰，我们在外部是无法调用的。每次扩容在以前的容量的基础上扩大两倍（从addEntry方法可以看出），扩容分为两部，构建一个新的Entry数组（桶），调用transfer方法将老数组oldTable的数据转移到新数组newTable中。
  transfer源码如下，for循环遍历每一个桶，while循环遍历桶中链表，如果桶中键值对e不为空（e!=null）,先保存e的下一个键值对next，重新计算e的索引，把e的next指向整个newTable[i]保存的数据，在把e放到新的桶中，下面table[0]元素转移到新桶做了简单的图帮助理解：

由于新插入的元素e的next指向桶中元素，所以新的桶中的元素顺序会倒过来。其实这个图并不严谨，因为元素从旧桶转移到新桶会按照新桶的容量重新计算索引，所以老桶中table[0]并不一定会被映射到新桶的table[0]。
  可以看到，HashMap使用riseize扩容，在原来的容量基础上扩大两倍，对原来每一个键值对键重新计算哈希值和索引，然后再移到新桶中，这是很消耗性能的。另外，由于HashMap是线程不安全的，在多线程环境下transfer可能会引发死循环问题，有兴趣的可以了解一下:不正确地使用HashMap引发死循环及元素丢失。

void resize(int newCapacity) { //保存扩容前的桶 Entry[] oldTable = table; int oldCapacity = oldTable.length; //如果目前的容量已经达到了MAXIMUM_CAPACITY，不会扩容，把threshold设置为Integer.MAX_VALUE 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); } 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]保存的数据 e.next = newTable[i]; //把e放到桶中。 newTable[i] = e; e = next; } } } 取出元素 get(Object key)

  之前我们在分析ArrayList源码的时候，因为ArrayList基于数组实现的所以根据索引查找非常快。而HashMap根据键值对键的哈希值计算得到一个索引，在不考虑哈希冲突的情况下，也能够以O(1)的时间复杂度找到键值对，具有很高的性能。

public V get(Object key) { //若键为null if (key == null) return getForNullKey(); Entry<K,V> entry = getEntry(key); return null == entry ? null : entry.getValue(); } private V getForNullKey() { //规定null的hash为0，在table[0]这个桶里面找键为null的键值对 for (Entry<K,V> e = table[0]; e != null; e = e.next) { //遍历寻找键为null的键值对 if (e.key == null) return e.value; } return 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; //条件：比较键的hash值是否相等且键是否==或equals if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } return null; } 删除元素 remove(Object key)