好久没更博了，因为这段时间实在是太忙了，做了几个公司的战略项目，更骚的是公司实行了一周打卡60个小时（低配版996），导致这段时间下班回家后基本上十点多了，洗个澡基本进被窝就是一顿美梦，现在项目基本上做完了，还算有点时间，也是时候写点东西了~_~
这段时间要写java基础了，先从集合开始吧，而在面试中经常问的集合最多的就是HashMap，那就先拿它开刀。
一、什么是HashMap？
HashMap是一个用于存储Key-Value键值对的集合，每一个键值对也叫做Entry。这些个键值对（Entry）分散存储在一个数组当中，这个数组就是HashMap的主干，HashMap数组每一个元素的初始值都是Null。
下面我们看下java7中HashMap的源码：
package java.util;import java.io.*;public class HashMap<K,V>extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable{/*** 1、默认的初始化容量大小，必须是2的次幂，默认是16*/static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16/*** 最大的容量，最大不能超过2的30次幂*/static final int MAXIMUM_CAPACITY = 1 << 30;/*** 2、加载因子，默认0.75,浮点数*/static final float DEFAULT_LOAD_FACTOR = 0.75f;/*** 当表没有膨胀时要共享的空表实例*/static final Entry<?,?>[] EMPTY_TABLE = {};/*** 表，根据需要调整大小。长度必须是2的幂。*/transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;/*** 此映射中包含的键-值映射的数量。*/transient int size;/*** 要调整大小的下一个大小值(容量*负载系数)。*/// 如果table == EMPTY_TABLE，那么这是表膨胀时创建的初始容量。int threshold;/*** 哈希表的加载因子。** @serial*/final float loadFactor;/*** 3、结构修改是指改变HashMap中映射的数量或以其他方式修改其内部结构(例如，rehash)。该字段用于使HashMap的集合视图上的迭代器快速失效。(见ConcurrentModificationException)。*/transient int modCount;/*** map容量的默认阈值，超过该阈值将对字符串键使用可选散列。替代哈希可以减少由于字符串键的弱哈希代码计算而引起的冲突。这个值可以通过定义系统属性{@code jdk.map.althashing.threshold}来覆盖。属性值{@code 1}强制在任何时候都使用备选哈希，而{@code -1}值则确保永远不使用备选哈希。*/static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;/*** 保存VM启动后才能初始化的值。*/private static class Holder {/*** 表容量超过这个容量，可以切换到其他哈希表。*/static final int ALTERNATIVE_HASHING_THRESHOLD;static {String altThreshold = java.security.AccessController.doPrivileged(new sun.security.action.GetPropertyAction("jdk.map.althashing.threshold"));int threshold;try {threshold = (null != altThreshold)? Integer.parseInt(altThreshold): ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;// disable alternative hashing if -1if (threshold == -1) {threshold = Integer.MAX_VALUE;}if (threshold < 0) {throw new IllegalArgumentException("value must be positive integer.");}} catch(IllegalArgumentException failed) {throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);}ALTERNATIVE_HASHING_THRESHOLD = threshold;}}/*** 与此实例关联的随机值，应用于键的哈希代码，使哈希冲突更难找到。如果为0，则禁用备选哈希。*/transient int hashSeed = 0;/*** 构造一个空的HashMap具有指定的初始容量和加载因子。** @param initialCapacity 初始化容量* @param loadFactor 加载因子* @throws 如果初始容量是负的或者负载因子是非正的，则返回IllegalArgumentException*/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，具有指定的初始容量和默认的加载因子(0.75)。** @param initialCapacity 初始化容量.* @throws 如果初始容量为负，则返回IllegalArgumentException*/public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);}/*** 构造一个空的HashMap，具有默认的初始容量(16)和默认的负载系数(0.75)。*/public HashMap() {this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);}/*** 构造一个新的HashMap与指定的Map相同的映射。HashMap是用默认的负载因子(0.75)创建的，初始容量足以容纳指定的Map中的映射。** @param m映射将被放置到这个映射中的映射* @throws 如果指定的映射为空，则为NullPointerException*/public HashMap(Map<? extends K, ? extends V> m) {this(Math.max((int) (m.size() DEFAULT_LOAD_FACTOR) + 1,DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);inflateTable(threshold);putAllForCreate(m);}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;}/*** 膨胀。*/private void inflateTable(int toSize) {// Find a power of 2 >= toSizeint capacity = roundUpToPowerOf2(toSize);threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);table = new Entry[capacity];initHashSeedAsNeeded(capacity);}// internal utilities/*** 子类的初始化钩子。在HashMap初始化后但插入任何条目之前，在所有构造函数和伪构造函数(clone、readObject)中调用此方法。(如果没有这个方法，readObject将需要明确的子类知识。)*/void init() {}/*** 初始化散列掩码值。我们推迟初始化，直到我们真正需要它。*/final boolean initHashSeedAsNeeded(int capacity) {boolean currentAltHashing = hashSeed != 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;}/*** 4、检索对象哈希代码并对结果哈希应用补充哈希函数，以防止质量较差的哈希函数。这是至关重要的，因为HashMap使用2的次方长度的哈希表，否则就会遇到在较低位上没有区别的哈希码冲突。注意:空键总是映射到哈希0，因此索引0。*/final int hash(Object k) {int h = hashSeed;if (0 != h && k instanceof String) {return sun.misc.Hashing.stringHash32((String) k);}h ^= k.hashCode();// This function ensures that hashCodes that differ only by// constant multiples at each bit position have a bounded// number of collisions (approximately 8 at default load factor).h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);}/*** 返回哈希码h的索引。*/static int indexFor(int h, int length) {// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";return h & (length-1);}/*** 返回map中元素的多少*/public int size() {return size;}/*** map是否是空的*/public boolean isEmpty() {return size == 0;}/*** 通过key去获取value*/public V get(Object key) {if (key == null)return getForNullKey();Entry<K,V> entry = getEntry(key);return null == entry ? null : entry.getValue();}/*** get()的卸载版本来查找空键。Null键映射到索引0。为了在两种最常用的操作(get和put)中提高性能，这个空情况被拆分为单独的方法，但在其他操作中与条件合并。*/private V getForNullKey() {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;}/*** 判断map中是否包含某个key*/public boolean containsKey(Object key) {return getEntry(key) != null;}/*** 根据key*/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里存放元素*/public V put(K key, V value) {if (table == EMPTY_TABLE) {inflateTable(threshold);}if (key == null)return putForNullKey(value);int hash = hash(key);int i = indexFor(hash, table.length);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;}}modCount++;addEntry(hash, key, value, i);return null;}/*** 卸载版本的put为空键*/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;}/*** 这个方法被构造函数和伪构造函数(clone, readObject)代替put。它不会调整表的大小，检查是否有变质等。它调用createEntry而不是addEntry。*/private void putForCreate(K key, V value) {int hash = null == key ? 0 : hash(key);int i = indexFor(hash, table.length);/*** 查找键的预先存在的条目。这永远不会发生在克隆或反序列化。它只会发生在构造时，如果输入映射是一个排序的映射，其顺序是不一致的w/ equals。*/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;}}createEntry(hash, key, value, i);}private void putAllForCreate(Map<? extends K, ? extends V> m) {for (Map.Entry<? extends K, ? extends V> e : m.entrySet())putForCreate(e.getKey(), e.getValue());}/*** 5、扩容*/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, initHashSeedAsNeeded(newCapacity));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];newTable[i] = e;e = next;}}}/*** 批量存入元素*/public void putAll(Map<? extends K, ? extends V> m) {int numKeysToBeAdded = m.size();if (numKeysToBeAdded == 0)return;if (table == EMPTY_TABLE) {inflateTable((int) Math.max(numKeysToBeAdded * loadFactor, threshold));}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);}for (Map.Entry<? extends K, ? extends V> e : m.entrySet())put(e.getKey(), e.getValue());}/*** 删除某个key对应的元素*/public V remove(Object key) {Entry<K,V> e = removeEntryForKey(key);return (e == null ? null : e.value);}/*** 根据key删除键值对*/final Entry<K,V> removeEntryForKey(Object key) {if (size == 0) {return null;}int hash = (key == null) ? 0 : hash(key);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;elseprev.next = next;e.recordRemoval(this);return e;}prev = e;e = next;}return e;}/*** 使用{@code Map.Entry.equals()}进行匹配的特殊版本的EntrySet的remove。*/final Entry<K,V> removeMapping(Object o) {if (size == 0 || !(o instanceof Map.Entry))return null;Map.Entry<K,V> entry = (Map.Entry<K,V>) o;Object key = entry.getKey();int hash = (key == null) ? 0 : hash(key);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;if (e.hash == hash && e.equals(entry)) {modCount++;size--;if (prev == e)table[i] = next;elseprev.next = next;e.recordRemoval(this);return e;}prev = e;e = next;}return e;}/*** 清空map中的元素*/public void clear() {modCount++;Arrays.fill(table, null);size = 0;}/*** 判断map中是否包含某个值，注意这个和包含某个key不同*/public boolean containsValue(Object value) {if (value == null)return containsNullValue();Entry[] tab = table;for (int i = 0; i < tab.length ; i++)for (Entry e = tab[i] ; e != null ; e = e.next)if (value.equals(e.value))return true;return false;}/*** 是否包含null值*/private boolean containsNullValue() {Entry[] tab = table;for (int i = 0; i < tab.length ; i++)for (Entry e = tab[i] ; e != null ; e = e.next)if (e.value == null)return true;return false;}/*** 克隆一个新的map*/public Object clone() {HashMap<K,V> result = null;try {result = (HashMap<K,V>)super.clone();} catch (CloneNotSupportedException e) {// assert false;}if (result.table != EMPTY_TABLE) {result.inflateTable(Math.min((int) Math.min(size * Math.min(1 loadFactor, 4.0f),// we have limits...HashMap.MAXIMUM_CAPACITY),table.length));}result.entrySet = null;result.modCount = 0;result.size = 0;result.init();result.putAllForCreate(this);return result;}/*** 键值对，实现Map接口*/static class Entry<K,V> implements Map.Entry<K,V> {final K key;V value;Entry<K,V> next;int hash;/*** Creates new entry.*/Entry(int h, K k, V v, Entry<K,V> n) {value = v;next = n;key = k;hash = h;}public final K getKey() {return key;}public final V getValue() {return value;}public final V setValue(V newValue) {V oldValue = value;value = newValue;return oldValue;}public final boolean equals(Object o) {if (!(o instanceof Map.Entry))return false;Map.Entry e = (Map.Entry)o;Object k1 = getKey();Object k2 = e.getKey();if (k1 == k2 || (k1 != null && k1.equals(k2))) {Object v1 = getValue();Object v2 = e.getValue();if (v1 == v2 || (v1 != null && v1.equals(v2)))return true;}return false;}public final int hashCode() {return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());}public final String toString() {return getKey() + "=" + getValue();}/*** 每当对HashMap中已经存在的键k调用put(k,v)覆盖条目中的值时，就会调用这个方法。*/void recordAccess(HashMap<K,V> m) {}/*** 只要从表中删除条目，就会调用此方法。*/void recordRemoval(HashMap<K,V> m) {}}/*** 添加键值对，入参支持索引，就是将键值对添加到哪个位置*/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;bucketIndex = indexFor(hash, table.length);}createEntry(hash, key, value, bucketIndex);}/*** 创建键值对，用于addEntry方法*/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++;}private abstract class HashIterator<E> implements Iterator<E> {Entry<K,V> next; // next entry to returnint expectedModCount; // For fast-failint index; // current slotEntry<K,V> current; // current entryHashIterator() {expectedModCount = modCount;if (size > 0) { // advance to first entryEntry[] t = table;while (index < t.length && (next = t[index++]) == null);}}public final boolean hasNext() {return next != null;}final Entry<K,V> nextEntry() {if (modCount != expectedModCount)throw new ConcurrentModificationException();Entry<K,V> e = next;if (e == null)throw new NoSuchElementException();if ((next = e.next) == null) {Entry[] t = table;while (index < t.length && (next = t[index++]) == null);}current = e;return e;}public void remove() {if (current == null)throw new IllegalStateException();if (modCount != expectedModCount)throw new ConcurrentModificationException();Object k = current.key;current = null;HashMap.this.removeEntryForKey(k);expectedModCount = modCount;}}private final class ValueIterator extends HashIterator<V> {public V next() {return nextEntry().value;}}private final class KeyIterator extends HashIterator<K> {public K next() {return nextEntry().getKey();}}private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {public Map.Entry<K,V> next() {return nextEntry();}}// Subclass overrides these to alter behavior of views' iterator() methodIterator<K> newKeyIterator() {return new KeyIterator();}Iterator<V> newValueIterator() {return new ValueIterator();}Iterator<Map.Entry<K,V>> newEntryIterator() {return new EntryIterator();}// Viewsprivate transient Set<Map.Entry<K,V>> entrySet = null;/*** 返回key的集合*/public Set<K> keySet() {Set<K> ks = keySet;return (ks != null ? ks : (keySet = new KeySet()));}private final class KeySet extends AbstractSet<K> {public Iterator<K> iterator() {return newKeyIterator();}public int size() {return size;}public boolean contains(Object o) {return containsKey(o);}public boolean remove(Object o) {return HashMap.this.removeEntryForKey(o) != null;}public void clear() {HashMap.this.clear();}}/*** 返回value的集合*/public Collection<V> values() {Collection<V> vs = values;return (vs != null ? vs : (values = new Values()));}private final class Values extends AbstractCollection<V> {public Iterator<V> iterator() {return newValueIterator();}public int size() {return size;}public boolean contains(Object o) {return containsValue(o);}public void clear() {HashMap.this.clear();}}/*** 返回键值对的集合*/public Set<Map.Entry<K,V>> entrySet() {return entrySet0();}private Set<Map.Entry<K,V>> entrySet0() {Set<Map.Entry<K,V>> es = entrySet;return es != null ? es : (entrySet = new EntrySet());}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();}}/*** 序列化 写*/private void writeObject(java.io.ObjectOutputStream s)throws IOException{// Write out the threshold, loadfactor, and any hidden stuffs.defaultWriteObject();// Write out number of bucketsif (table==EMPTY_TABLE) {s.writeInt(roundUpToPowerOf2(threshold));} else {s.writeInt(table.length);}// Write out size (number of Mappings)s.writeInt(size);// Write out keys and values (alternating)if (size > 0) {for(Map.Entry<K,V> e : entrySet0()) {s.writeObject(e.getKey());s.writeObject(e.getValue());}}}private static final long serialVersionUID = 362498820763181265L;/*** 序列化 读*/private void readObject(java.io.ObjectInputStream s)throws IOException, ClassNotFoundException{// Read in the threshold (ignored), loadfactor, and any hidden stuffs.defaultReadObject();if (loadFactor <= 0 || Float.isNaN(loadFactor)) {throw new InvalidObjectException("Illegal load factor: " +loadFactor);}// set other fields that need valuestable = (Entry<K,V>[]) EMPTY_TABLE;// Read in number of bucketss.readInt(); // ignored.// Read number of mappingsint mappings = s.readInt();if (mappings < 0)throw new InvalidObjectException("Illegal mappings count: " +mappings);// capacity chosen by number of mappings and desired load (if >= 0.25)int capacity = (int) Math.min(mappings * Math.min(1 loadFactor, 4.0f),// we have limits...HashMap.MAXIMUM_CAPACITY);// allocate the bucket array;if (mappings > 0) {inflateTable(capacity);} else {threshold = capacity;}init(); // Give subclass a chance to do its thing.// Read the keys and values, and put the mappings in the HashMapfor (int i = 0; i < mappings; i++) {K key = (K) s.readObject();V value = (V) s.readObject();putForCreate(key, value);}}// These methods are used when serializing HashSetsint capacity() { return table.length; }float loadFactor() { return loadFactor; }}
以上是java7中的HashMap源码，内容还是不少的，但是有很多方法都不重要，甚至有点废，这里标出了5个重要的点，如果你能把这5个点弄懂了，HashMap你就算掌握了95%了，起码面试得时候别人再问你，你不虚的。
二、重要的5个知识点
1、为什么初始化容量大小必须是2的次幂，默认是16？
其实我们在用HashMap的时候大多数是在put/get，谁平时没事天天研究什么加载因子，容量这玩意，那咱就先看看HashMap的put方法：
public V put(K key, V value) {if (table == EMPTY_TABLE) {inflateTable(threshold);}if (key == null)return putForNullKey(value);//对key进行hash返回一个int类型的数int hash = hash(key);//根据key的hash值和哈希表（map的容量）的长度，调用一个叫indexFor的方法计算出又一个整数int i = indexFor(hash, table.length);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;}}modCount++;addEntry(hash, key, value, i);return null;}
关键点就在indexFor方法了，带它上来：
static int indexFor(int h, int length) {// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";return h & (length-1);
就一句代码，h&（length-1），其中h表示的就是key的hashCode值，length标识HashMap的容量，有的人可能看不懂，其实这是一种位运算，&表示按位与运算，这是一种二进制数据的运算方式，为了让你明白，这里插点内容。
这里说下按位与运算，运算规则：只有两个数的二进制同时为1，结果才为1，否则为0（负数按补码形式参加按位与运算）。
即 0 & 0= 0 ，0 & 1= 0，1 & 0= 0， 1 & 1= 1。
例：3 &5 即 00000011 & 00000101 = 00000001 ，所以 3 & 5的值为1。
明白了什么是按位与运算后面，再接着看上面的h&（length-1），这里假设length的值是8，那8-1就是7，7用二进制数表示就是0111，然后假如h的值是6，转换为二进制是0110，0110&0111的结果是0110，转换成10进制就是6，那如果h是10呢，10转换成二进制是1010，1010&0111的结果是0010，转换成10进制是2，，再如果h是12呢，1100&0111的结果是0100，转换成10进制是4，直观点表示如下：
6&（8-1）=6；
10&（8-1）=2；
12&（8-1）=4；
......
这TM也没规律啊，没错，确实没有规律，但是JDK为什么要这么算呢？其实JDK的初衷是这样的，用key哈希出来的值对map的容量取模，算出来下标，也就是说JDK是想这么干：
6%8=8；
10%8=2；
12%8=4；
......
然后它发现上面的按位与运算和下面的取模预算是等价的，所以用上面的方式装了波逼，真的只是为了装逼吗？too young，too simple！如果你学过那么一点计算机基础的话就会知道数据在计算机中都是以二进制的方式存在的，所以按位与相对取模来说省去了二进制到十进制的转换，性能优化就是这么做的。现在知道为什么初始化容量大小为什么是2的次幂了吧，只要保证length的大小是2的次幂，就可以通过按位与运算去实现取模运算了。
那为什么默认大小是16呢，这个JDK官方没有给出解释，网上那些野鸡解释就别看了，这里你可以理解为太小的话有可能频繁引起扩容，太大了浪费内存，把它当成一个经验值吧。
2、加载因子是什么，为什么默认是0.75f？
所谓加载因子，表示的是哈希表中元素填满的程度，比如HashMap的容量大小是16，那么它里面只能存放16*0.75=12个元素，超过12个它就要扩容了，为什么有这个玩意，存16个它不香吗？不知道你对hash函数了解有多少，hash这个方法有可能会发生hash冲突的，没错，加载因为这个东西就是为了减少hash冲突的，我存的元素少了，冲突的概率也就低了，但是内存利用率低了，我存的元素多了，冲突的概率也就高了，但是内存利用率高了，鱼和熊掌不可兼得，专家根据泊松分布计算出了0.75是最佳的加载因子大小，有兴趣的可以搜下泊松分布。
3、modCount
看下我加的注释：该HashMap被结构修改的次数。结构修改是指改变HashMap中映射的数量或修改其内部结构(例如，rehash)。该字段用于使HashMap的集合视图上的迭代器快速失效。(见ConcurrentModificationException)。如果在遍历map中元素的时候对元素进行了增删改，这个值都是会变得。这个估计会触到某些人的知识盲区，java.util包里的集合类里都有这个变量，不信你可以去看看，这里上端代码看下这个变量是个啥玩意？
private abstract class HashIterator<E> implements Iterator<E> {Entry<K,V> next; // next entry to returnint expectedModCount; // For fast-fail 快速失败int index; // current slotEntry<K,V> current; // current entryHashIterator() {//初始化iterator的时候将modCount的值赋给expectedModCountexpectedModCount = modCount;if (size > 0) { // advance to first entryEntry[] t = table;while (index < t.length && (next = t[index++]) == null);}}public final boolean hasNext() {return next != null;}final Entry<K,V> nextEntry() {//判断两个值是否相等，如果不相等就会抛出并发修改的异常if (modCount != expectedModCount)throw new ConcurrentModificationException();Entry<K,V> e = next;if (e == null)throw new NoSuchElementException();if ((next = e.next) == null) {Entry[] t = table;while (index < t.length && (next = t[index++]) == null);}current = e;return e;}public void remove() {if (current == null)throw new IllegalStateException();if (modCount != expectedModCount)throw new ConcurrentModificationException();Object k = current.key;current = null;HashMap.this.removeEntryForKey(k);expectedModCount = modCount;}}
综上可以看出，在遍历下一个元素之前，都会检测modCount是否被改变过，如果没被改变过就返回元素，如果被改变过的话就抛出异常了，这种机制叫做快速失败：其实就是不允许多个线程在集合遍历的时候去并发操作元素，其实这是一种安全机制，就是不允许你并发修改数据。
4、HashMap中的hash方法
final int hash(Object k) {int h = hashSeed;if (0 != h && k instanceof String) {return sun.misc.Hashing.stringHash32((String) k);}//对key进行hashh ^= k.hashCode();// This function ensures that hashCodes that differ only by// constant multiples at each bit position have a bounded// number of collisions (approximately 8 at default load factor).h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);}
如果现在有两个不同的key值，通过key.hashCode方法计算出来的值一样怎么办，这就冲突了啊，这么容易冲突的吗？别急，下面不还有两行代码呢吗，下面那两行代码的作用是扰动运算，经过扰动运算（将Hash值的高16位右移并与原Hash值取异或运算（^），混合高16位和低16位的值，得到一个更加散列的低16位的Hash值）后得到的值就不同了，HashMap就是这样解决hash冲突的，你有兴趣的话可以专门研究下这个扰动算法，这里不再赘述。
5、扩容
最后一个知识点了，但也是最重要的知识点，先写个程序看下HashMap的扩容：
public V put(K key, V value) {if (table == EMPTY_TABLE) {inflateTable(threshold);}if (key == null)return putForNullKey(value);int hash = hash(key);int i = indexFor(hash, table.length);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;}}modCount++;//添加键值对addEntry(hash, key, value, i);return null;}
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;bucketIndex = indexFor(hash, table.length);}createEntry(hash, key, value, bucketIndex);}
void resize(int newCapacity) {Entry[] oldTable = table;int oldCapacity = oldTable.length;if (oldCapacity == MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return;}//新建一个entry数组Entry[] newTable = new Entry[newCapacity];//将元素转移到新entry数组中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) {//获取链表的头节点ewhile(null != e) {//获取要转移的下一个节点nextEntry<K,V> next = e.next;if (rehash) {e.hash = null == e.key ? 0 : hash(e.key);}//计算要转移的节点在新的Entry数组newTable中的位置int i = indexFor(e.hash, newCapacity);//使用头插法将要转移的节点插入到newTable原有的单链表中e.next = newTable[i];//将newTable的hash桶的指针指向要转移的节点newTable[i] = e;//转移下一个需要转移的节点ee = next;}}}
由于是头插法，所以在元素转移后，位置会倒置，多线程情况下进行扩容会有形成一个环，导致get的时候死循环，一直打满cpu，关于这个过程就不具体描述了，这里推荐一篇文章，讲的很详细：https://www.jianshu.com/p/1e9cf0ac07f4，jdk8中扩容和7是有区别的，8中是尾插法，所以不会造成环，但是都会存在元素覆盖的问题，因为put方法没有加锁，还有一点区别是JDK8中当链表中的数据超过8个的时候会转化为红黑树，这样更有利于查找。
文章转载自Java Miraculous，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
