四、构造方法
HashMap一共有四个构造方法
4.1 HashMap()
空参构造，构造一个空的HashMap，初始容量默认为16，负载因子默认0.75。
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted }
4.2 HashMap(int initialCapacity, float loadFactor)
指定初始容量和负载因子，构造一个空的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); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); }
4.3 HashMap(int initialCapacity)
指定初始容量，负载因子为默认值（0.75），构造一个空的HashMap。
public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); }
4.4 HashMap (Map<? extends K, ? extends V> m)
负载因子为默认值（0.75），调用putMapEntries将传入的Map拷贝到当前的Map。
public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }
五、方法
5.1 put & putVal
put方法通过调用putVal来插入数据，在调用putVal之前会先调用hash方法。
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }
先来看看hsah方法是怎么实现的。
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
首先判断key是否为null，前面已经说过了在HashMap中，key是可以为null的，如果为null，直接返回0。
如果key不为null，先获取key的hashCode，再将hashCode与hashCode本身的高16位异或运算，这样做的目的是为了减少哈希碰撞。
接下来看看putVal方法，首先看看putVal的参数
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)
- hash：key的hash值
- key：待插入的key
- value：待插入的value
- onlyIfAbsent：当存在重复key时，是否覆盖旧值，false为覆盖，true为不覆盖
- evict：如果为false表示table为创建状态
putVal方法的实现：
/** * Implements Map.put and related methods * * @param hash hash for key * @param key the key * @param value the value to put * @param onlyIfAbsent if true, don't change existing value * @param evict if false, the table is in creation mode. * @return previous value, or null if none */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; // 如果table未初始化，调用resize()方法进行初始化 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 将hash值和数组长度相与，得到数组下标，如果该下标的值为null，直接创建一个Node放在该下标 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); // 发生hash冲突的情况 else { Node<K,V> e; K k; // 第一种，头节点的hash值与待插入的hash值相同，并且key值相同 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 第二种，待插入的key与头节点的key不相同，并且该节点是红黑树节点 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 第三种，待插入的key与头节点的key不相同，并且该节点是链表节点 else { // 遍历链表，并统计hash碰撞次数 for (int binCount = 0; ; ++binCount) { // 如果遍历到结尾，说明没有重复的key，则在结尾插入一个Node if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); // 判断是否需要将链表转为红黑树 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } // 如果链表中存在和待插入的key相同的情况，则退出循环 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // 如果e不等于null，则说明存在相同的key if (e != null) { // existing mapping for key V oldValue = e.value; // onlyIfAbsent等于false，或者oldValue等于null时，覆盖旧值 if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; // 判断是否需要扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }
5.2 resize()
resize()方法用于初始化和扩容数组。因为JDK1.8引入了红黑树，resize()方法也变得更加复杂，先来看看JDK1.7中resize()方法是怎么实现的。
void resize(int newCapacity) { Entry[] oldTable = table; // 当前的数组长度 int oldCapacity = oldTable.length; // 如果当前数组长度已经到了最大容量（2^30) if (oldCapacity == MAXIMUM_CAPACITY) { // 将阈值修改为int的最大值（2^31 - 1) threshold = Integer.MAX_VALUE; return; } // 创建一个新的数组 Entry[] newTable = new Entry[newCapacity]; // 调用transfer方法将旧数组的元素复制到新数组 transfer(newTable, initHashSeedAsNeeded(newCapacity)); table = newTable; // 修改阈值 threshold = (int) Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); }
transfer方法的实现：
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; // 是否重新计算hash值 if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } // 根据hash值获取key在新数组的下标 int i = indexFor(e.hash, newCapacity); // 使用头插法将节点插入到新数组对应的下标 e.next = newTable[i]; newTable[i] = e; e = next; } } }
再来看看JDK1.8中resize()方法的实现
final Node<K,V>[] resize() { // ----------数组扩容部分---------- Node<K,V>[] oldTab = table; // 旧数组的长度 int oldCap = (oldTab == null) ? 0 : oldTab.length; // 旧的扩容阈值 int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { // 如果旧数组已经达到最大容量，将阈值修改为int最大值(2^31 - 1)，不再扩容 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } // 如果新的数组容量（旧容量的两倍）小于最大容量，并且原数组长度大于等于16 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) // 新阈值为原来的两倍 newThr = oldThr << 1; } // 旧数组长度等于0，并且阈值大于0，直接将新数组长度赋值为旧阈值的值 else if (oldThr > 0) newCap = oldThr; else { // 旧容量和旧阈值都为0 // 新容量为默认初始容量（16） newCap = DEFAULT_INITIAL_CAPACITY; // 新阈值为默认负载因子(0.75) * 默认初始容量(16) = 12 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 如果新的阈值等于0 if (newThr == 0) { float ft = (float)newCap * loadFactor; // 如果新的容量小于最大容量，并且新的容量 * 负载因子小于最大容量，则新的阈值等于新的容量 * 负载因子 // 否则新的阈值等于int的最大值(2^32 - 1) 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 = newTab; if (oldTab != null) { // 遍历旧数组 for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; // 当前下标只有一个节点，计算该节点在新数组的下标，并将节点放到这个新下标下 if (e.next == null) newTab[e.hash & (newCap - 1)] = e; // 该节点红黑树节点 else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // 链表节点，将链表分为两个链表，其中一个链表在新数组中的下标保持不变，另一个下标将变为原下标+旧数组长度 else { // 下标不变的链表头节点和尾节点 Node<K,V> loHead = null, loTail = null; // 下标需要改变的链表头节点和尾节点 Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; // 如果该节点hash值与上旧容量等于0，加入到下标不需要改变的链表中 if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } // 否则将节点加入到下标需要改变的链表中 else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); // 将两个链表分别放到新数组对应的下标下 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }
