本文基于jdk1.8.
HashMap即哈希表，是一种能以常数平均时间完成插入，删除和查找操作的数据结构；
哈希表有两种实现方式：开放地址方式和冲突链表方式；开放地址方式不需要使用链表，但是要频繁的再散列操作，常用的再散列方法有线性探测法，平方探测法，双散列法。冲突链表方式将所有哈希值相同的键用链表串起来，理想情况下的哈希表每个哈希值对应一个键，此时查找操作为常数时间；
有两个参数与哈希表的性能有关：容量Capacity和装载因子load_factor，Threshold=Capacity * load_factor；
哈希表默认的容量是2^4；最大容量是2^30；装载因子默认为0.75；
当装入哈希表的元素大于threshold时，哈希表自动扩容，容量变为原来2倍，扩容后元素顺序会被打散，在不同时间遍历哈希表得到的结果可能不同；
在jdk1.8中，链表过长的话（长度>8），HashMap会将冲突链表转化为红黑树；
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable其底层实现是由数组和链表构造而成，如图：
1. get（Object key）
public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; }通过传入key得到value；
2. getNode(int hash, Object key)
final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; if ((e = first.next) != null) { if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }tab[n-1]&hash是确定key在哈希表中的位置；
然后在链表中寻找(k==key || key.equals(k)),找k是否==key或equals key；返回Node；
若需要将自定义的对象放入HashMap中，需要override equals方法和hashCode方法； 3. containsKey(Object key)
public boolean containsKey(Object key) { return getNode(hash(key), key) != null; }判断哈希表中是否存在这个key；
4. put
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }将一个键值对插入哈希表；5.remove
public V remove(Object key) { Node<K,V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; }将key对应的Node从哈希表中删除；
和其他集合类的比较：HashSet采用了适配器模式（HashSet里有一个HashMap）；HashMap没有实现同步，HashTable实现了同步，其余类似；HashMap元素无序，TreeMap元素有序；
参考文章：https://zhuanlan.zhihu.com/p/24828513
