hashMap实现Map接口，基于hashing原理，以键值对形式存储，允许null键/值，非同步的集合类型；
hashmap的底层存储结构是基于数组和链表的
一、put方法
public Object put(Object key,Object value);
1、因为hashmap存储的底层结构是数组和链表，所以，当我们put时，需要计算出数组的下标：
1）执行key.hashCode()方法，得到哈希码：hashCode=key.hashCode();
2）用哈希码做hash运算，得到一个散列值:int hash = hash(hashCode);
3）散列值与数组的长度做indexFor运算，得到数组下标。
2、了解了这个过程，我们很容易能发现，即使key不同，经过前两步运算，也可能得到相同散列值。所以我们put时，新的entry和旧的entry可能发生冲突，解决hash冲突的方法有很多，在hashmap中采用的是链地址法。即：
对新entry和旧entry进行判断：
1）散列值相同，key相同；
此时说明是相同的entry，用新的entry覆盖旧的entry。
2）散列值相同，key不同；
执行key.equals()方法；
如果这两个对象通过hashmap重写的equals()方法判断是一样的，说明是同一个entry对象，用新的entry覆盖旧的entry；
如果不同，就把新加入的entry对象放在对应数组下标位置的表头，早进来的entry向后移动一个位置，形成链表；
特别注意：我们存放在数组中的并不只有value，是一个entry（hash,key,value,bucketIndex）对象。
3、链表长度太长，影响查询效率怎么办？
JDK1.8多了一个新特性，当链表的长度>=8时，链表转换为红黑树，提高查询效率：
1.8 链表转红黑树的源码 static final int TREEIFY_THRESHOLD = 8; if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break;
4、不断增加对象，是否需要扩容resize？
了解一下API里hashmap的构造方法，里面有initialCapacity和loadFactor两个名词；
initialCapacity是哈希表的数组的初识大小，始终保持 2^n，可以扩容，扩容后数组大小为当前的 2 倍；loadFactor是加载因子；HashMap的默认大小是16，那么他的数组长度是0-15；默认加载因子是0.75；threshold：扩容的阈值，等于 capacity * loadFactor
所以，当容量达到threshold时，数组会自动扩容到原来大小的两倍；比如，当前我们的数组的大小是16，当存储到12个元素时，数组会自动扩容到32.
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[] 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)(newCapacity * loadFactor); }
5、key为null时
public V put(K key, V value) { 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; } 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; }
当key为null时，如果数组中有key为null的，遍历table[0]链表（key为null的元素放在了数组的第0位），如果找到，将传入的value重新赋值给这个元素的value，并返回原来的value。如果没有找到，就将元素添加到table[0]链表的表头。所以，key为null时，在hashmap的链表中只有一个值。
二、get
1、与put相同，先根据key，算出hash，算出数组下标，定位到数组元素。
2、遍历该元素处的链表
取出传进来的key与链表中entry对象的key值相等的value或传进来的key和entry对象的key连重写后的equals后都一样的value；
public V get(Object key) { if (key == null) return getForNullKey(); int hash = hash(key.hashCode()); //先定位到数组元素，再遍历该元素处的链表 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.equals(k))) return e.value; } return null; } private V getForNullKey() { for (Entry<K,V> e = table[0]; e != null; e = e.next) { if (e.key == null) return e.value; } return null; }
3、当key为null时？
由put的过程可知，hashmap将key为null的元素放到了数组第0个元素的链表中。根据getForNullKey（）的实现代码可知。
