1.结构

Map<K,V>是一个接口，这个接口内部还有一个接口，叫Entry<K,V>。HashMap中Entry接口的实现类是内部静态类：HashMap.Node，结构见下：

static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; /**/ } HashMap类的结构见下：

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { transient Node<K,V>[] table; transient Set<Map.Entry<K,V>> entrySet; transient int size; transient int modCount; int threshold; static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 final float loadFactor; static final int TREEIFY_THRESHOLD = 8; /**/ }

size：map中元素的个数。

modCount：表示读以外的操作次数。用来检查并抛出ConcurrentModificationException。这是fast-fail思想。

TREEIFY_THRESHOLD： 若某个链表的长度大于此阀值，则将node转为TreeNode，即将链表转为红黑树。注意其他链表不受影响。

loadFactor：装填因子，与capacity搭配使用。

DEFAULT_INITIAL_CAPACITY：初始容量。capacity为数组（桶）的长度。capacity与loadfactor决定了扩容的threshold。

threshold: 初始=capacity*loadFactor。当size>threshold后，扩容，capacity与threshold都翻一倍。

2.写操作

V java.util.HashMap.put(K key, V value) 向map中添加元素，它会调用下面putVal(...)方法。 V java.util.HashMap.putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) 参数onlyIfAbsent：在为true的情况下，如果map中已经有这个key了，那么此次添加操作无效。 此函数的具体操作为：首先找到key所在的链表，table[i],这个下标i=(tab.length-1) & hash。如果table[i]=null，则新建node；否则遍历链表。若在遍历过程中遇到相等的key，按照onlyIfAbsent参数行事；若遇不到，在尾部新建node。

3.读操作

V java.util.HashMap.get(Object key) 根据key拿到value。它会调用getNode()方法，然后返回node的value。见下。 Node<K, V> java.util.HashMap.getNode(int hash, Object key) 先根据hashcode找到所在的链表。Node<K,V> first=table[(table.length-1) & hash]。然后遍历。

4.resize()扩容

Node<K, V>[] java.util.HashMap.resize() 扩容一倍。

首先申请新的数组，Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]。然后遍历旧数组的链表，分拆到新数组中。

5.treeify

JDK 1.8之前，HashMap是数组（桶）+链表实现，而1.8中作了大的变动，改为数组（桶）+链表+红黑树实现。 当链表长度超过阈值8时，将链表转换为红黑树，这样大大减少了查找时间。