HashMap简述
在JDK中，HashMap是存储键值对用的比较多的一个类。
其基于哈希散列表计算位置来达到键不重复存储。
其内部数据结构是数组（散列桶）+链表+红黑树，
数组是基础存储，存储位置为计算出来的hash值和数组长度减一相与，而数组长度一直都为2的整数幂。
链表是遇到哈希碰撞时，即数组同一下标要存放第二个值的时候，会在原值后面链接上下一个键值对。
红黑树是在链表过长（默认大于8）时进行的结构重组，将链表转换为红黑树，加快搜索效率。
HashMap的声明
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
扩展Map接口代表这个类是存储键值对的数据结构。
HashMap的域
在以往的版本中，是用Entry<K,V>来表示一个键值对结点的，而后来引入了红黑树表示的节点（TreeNode），就产生了新的表示方法（Node）。
1 transient Node<K,V>[] table; //这是HashMap的域 2 3 //内部类 4 static class Node<K,V> implements Map.Entry<K,V> { 5 final int hash; 6 final K key; 7 V value; 8 Node<K,V> next; 9 10 //下面还有一些方法，如geKeyt、setValue、toString 11 } 12 13 static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> 14 15 //下面这个是LinkedHashMap.Entry<K,V> 的声明 16 //TreeNode是Node的子类 17 //具体的实现不在这里描述，可以参考红黑树或者TreeMap<K,V> 18 static class Entry<K,V> extends HashMap.Node<K,V>
1 //用作缓存entrySet()函数的结果 2 transient Set<Map.Entry<K,V>> entrySet; 3 4 //当前存放键值对的个数 5 transient int size; 6 7 //加载因子 8 final float loadFactor; 9 10 //capacity（键值对数组table的大小）*loadFactor 11 //当size>threshold会进行一次扩容（resize） 12 int threshold; 13 14 //若初始化没指定时各个域的默认值 15 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 16 17 static final float DEFAULT_LOAD_FACTOR = 0.75f; 18 19 //一个HashMap capacity的最大容量 20 static final int MAXIMUM_CAPACITY = 1 << 30; 21 22 23 //链表和红黑树互相转换时参照的值 24 static final int TREEIFY_THRESHOLD = 8; 25 26 static final int UNTREEIFY_THRESHOLD = 6; 27 28 //使用红黑树时最小的capacity值 29 static final int MIN_TREEIFY_CAPACITY = 64;
HashMap的构造方法
1 public HashMap(int initialCapacity, float loadFactor) { 2 if (initialCapacity < 0) 3 throw new IllegalArgumentException("Illegal initial capacity: " + 4 initialCapacity); 5 if (initialCapacity > MAXIMUM_CAPACITY) 6 initialCapacity = MAXIMUM_CAPACITY; 7 if (loadFactor <= 0 || Float.isNaN(loadFactor)) 8 throw new IllegalArgumentException("Illegal load factor: " + 9 loadFactor); 10 this.loadFactor = loadFactor; 11 this.threshold = tableSizeFor(initialCapacity); 12 } 13 14 public HashMap(int initialCapacity) { 15 this(initialCapacity, DEFAULT_LOAD_FACTOR); 16 } 17 18 public HashMap() { 19 this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted 20 } 21 22 public HashMap(Map<? extends K, ? extends V> m) { 23 this.loadFactor = DEFAULT_LOAD_FACTOR; 24 putMapEntries(m, false); 25 }
除了参数为Map的构造方法，其余的都是参数检测和默认赋值，
另外值得一提的是，传入initCapacity的构造方法都会先将其放入threshold中，
可以发现构造方法中并没有构建任何数据结构，这些会在第一次put中才会生成。
参数为Map的构造方法调用了另外的核心方法，后面再详细叙述。
HashMap的关键方法
介绍增删改查之前，先介绍有关size的方法，也就是table大小的设定。
resize方法除了初始化会使用，在扩容的时候也会使用，但也同样保证了是2次幂。
1 final Node<K,V>[] resize() { 2 Node<K,V>[] oldTab = table; 3 //如果table为空，oldCap设为0，否则设为table的长度 4 int oldCap = (oldTab == null) ? 0 : oldTab.length; 5 int oldThr = threshold; 6 int newCap, newThr = 0; 7 //1:table不为空（扩容） 8 if (oldCap > 0) { 9 //1.1:table超过最大值，设 treshold为int最大值 10 if (oldCap >= MAXIMUM_CAPACITY) { 11 threshold = Integer.MAX_VALUE; 12 return oldTab; 13 } 14 //设newCap为oldCap的两倍 15 //1.2:如果newCap小于最大长度且oldCap大于初始长度 16 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && 17 oldCap >= DEFAULT_INITIAL_CAPACITY) 18 newThr = oldThr << 1; // double threshold 19 } 20 //2:table为空而threshold不为空，那初始的capacity就为threshold 21 else if (oldThr > 0) // initial capacity was placed in threshold 22 newCap = oldThr; 23 else {//3:没有设置初始容量，就设为默认容量和默认threshold 24 newCap = DEFAULT_INITIAL_CAPACITY; 25 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); 26 } 27 //如果是上述1.1或者2情况时，尚未指定newThr，则计算 28 if (newThr == 0) { 29 float ft = (float)newCap * loadFactor; 30 //计算是否超过最大值，超过就赋予int最大值 31 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? 32 (int)ft : Integer.MAX_VALUE); 33 } 34 threshold = newThr; 35 //生成初始化后或扩容后的table 36 @SuppressWarnings({"rawtypes","unchecked"}) 37 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; 38 table = newTab; 39 40 if (oldTab != null) { 41 //遍历旧值传入新table 42 for (int j = 0; j < oldCap; ++j) { 43 Node<K,V> e;//e保存旧结点，旧结点设为null等待回收 44 if ((e = oldTab[j]) != null) { 45 oldTab[j] = null; 46 //某结点下一个值为空（单一结点），直接赋值 47 if (e.next == null) 48 newTab[e.hash & (newCap - 1)] = e; 49 //某结点为TreeNode，用TreeNode方法赋值 50 else if (e instanceof TreeNode) 51 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); 52 //某结点是一个链表 53 //发现扩容后同一hash值的节点要么会在原数组索引位置 54 //要么会在原数组索引+原数组长度位置 55 //因为扩容总是扩展2的倍数 56 else { // preserve order 57 Node<K,V> loHead = null, loTail = null;//原位置 58 Node<K,V> hiHead = null, hiTail = null;//扩展位置（高位置） 59 Node<K,V> next; 60 do { 61 next = e.next; 62 //相与判断是否hash值仍在原索引位置 63 if ((e.hash & oldCap) == 0) { 64 if (loTail == null) 65 loHead = e; 66 else 67 loTail.next = e; 68 loTail = e; 69 } 70 else { 71 if (hiTail == null) 72 hiHead = e; 73 else 74 hiTail.next = e; 75 hiTail = e; 76 } 77 } while ((e = next) != null); 78 //原位置连接 79 if (loTail != null) { 80 loTail.next = null; 81 newTab[j] = loHead; 82 } 83 //高位置连接 84 if (hiTail != null) { 85 hiTail.next = null; 86 newTab[j + oldCap] = hiHead; 87 } 88 } 89 } 90 } 91 } 92 return newTab; 93 } 94 95 96 //使cap设为大于传入cap最小的2次幂 97 static final int tableSizeFor(int cap) { 98 //cap - 1为了防止传入cap为2的整数幂，经过计算后会变为原来的2倍 99 int n = cap - 1; 100 n |= n >>> 1; 101 n |= n >>> 2; 102 n |= n >>> 4; 103 n |= n >>> 8; 104 n |= n >>> 16; 105 //上面操作使得n最高位开始后面全部位都为1 106 //计算后n小于0（传入参数为0或者为负数）返回1 107 //否则如果计算后大于最大cap返回最大 108 //否则返回n+1，即n最高位前一位为1后面全部为0 109 //即是大于原参最小的2次幂 110 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; 111 }
1 public V put(K key, V value) { 2 return putVal(hash(key), key, value, false, true); 3 } 4 5 //onIfAbsent为true时表示只有在该Key值在Map中不存在时才插入 6 //evict表示Map为初始化阶段，仅与afterNodeInsertion方法相关联， 7 //在HashMap中，afterNodeInsertion方法体为空，可以无视 8 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, 9 boolean evict) { 10 Node<K,V>[] tab; Node<K,V> p; int n, i; 11 //当table为空（第一次插入）时，调用resize方法。 12 if ((tab = table) == null || (n = tab.length) == 0) 13 n = (tab = resize()).length; 14 //如果插入的节点hash值所占table的位置没有元素，则新建一个节点插入 15 if ((p = tab[i = (n - 1) & hash]) == null) 16 tab[i] = newNode(hash, key, value, null); 17 //插入点有元素（哈希碰撞） 18 else { 19 Node<K,V> e; K k; 20 //想插入的和原位置的hash值和key都相等时，将原节点替换为新节点 21 if (p.hash == hash && 22 ((k = p.key) == key || (key != null && key.equals(k)))) 23 e = p; 24 //原节点是一个红黑树节点，用红黑树的插入方法 25 else if (p instanceof TreeNode) 26 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); 27 //否则（有链表存在） 28 else { 29 //遍历链表，用binCount记录遍历链表长度 30 for (int binCount = 0; ; ++binCount) { 31 //原节点下一个节点为空，直接插入（将原节点next设为该节点） 32 if ((e = p.next) == null) { 33 p.next = newNode(hash, key, value, null); 34 //插入后发现链表长度大于要转换为红黑树的临界值，就转换为红黑树 35 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 36 treeifyBin(tab, hash); 37 break; 38 } 39 //如果遍历到链表中一节点hash值和key都与要插入的节点相等，就替换该节点 40 if (e.hash == hash && 41 ((k = e.key) == key || (key != null && key.equals(k)))) 42 break; 43 p = e; 44 } 45 } 46 //如果插入的地方是有原值的，就返回原来的值 47 if (e != null) { // existing mapping for key 48 V oldValue = e.value; 49 if (!onlyIfAbsent || oldValue == null) 50 e.value = value; 51 afterNodeAccess(e); 52 return oldValue; 53 } 54 } 55 ++modCount; 56 //如果插入后size超过threshold，就进行扩容 57 if (++size > threshold) 58 resize(); 59 afterNodeInsertion(evict); 60 return null; 61 }
1 public void putAll(Map<? extends K, ? extends V> m) { 2 putMapEntries(m, true); 3 } 4 5 final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { 6 int s = m.size(); 7 if (s > 0) { 8 //被插入的为null 9 if (table == null) { // pre-size 10 //根据size设置threshold 11 float ft = ((float)s / loadFactor) + 1.0F; 12 int t = ((ft < (float)MAXIMUM_CAPACITY) ? 13 (int)ft : MAXIMUM_CAPACITY); 14 if (t > threshold) 15 threshold = tableSizeFor(t); 16 } 17 //发现要扩容 18 else if (s > threshold) 19 resize(); 20 //设置好后遍历插入 21 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { 22 K key = e.getKey(); 23 V value = e.getValue(); 24 putVal(hash(key), key, value, false, evict); 25 } 26 } 27 }
1 public V get(Object key) { 2 Node<K,V> e; 3 return (e = getNode(hash(key), key)) == null ? null : e.value; 4 } 5 6 final Node<K,V> getNode(int hash, Object key) { 7 Node<K,V>[] tab; Node<K,V> first, e; int n; K k; 8 //判断table不为null且table有长度且hash值对应table中索引内有数据才进入 9 if ((tab = table) != null && (n = tab.length) > 0 && 10 (first = tab[(n - 1) & hash]) != null) { 11 //判断该节点是否为所求（没产生哈希碰撞） 12 if (first.hash == hash && // always check first node 13 ((k = first.key) == key || (key != null && key.equals(k)))) 14 return first; 15 //产生了哈希碰撞 16 if ((e = first.next) != null) { 17 //节点为TreeNode，用treeNode方法取出 18 if (first instanceof TreeNode) 19 return ((TreeNode<K,V>)first).getTreeNode(hash, key); 20 //节点为链表，循环遍历next 21 do { 22 if (e.hash == hash && 23 ((k = e.key) == key || (key != null && key.equals(k)))) 24 return e; 25 } while ((e = e.next) != null); 26 } 27 } 28 return null; 29 }
1 public V remove(Object key) { 2 Node<K,V> e; 3 return (e = removeNode(hash(key), key, null, false, true)) == null ? 4 null : e.value; 5 } 6 7 //matchValue为true时表示只有key和value都对应的情况下才remove 8 //movable为true时表示在TreeNode中移除该节点同时移动其他节点 9 //removeNode的条件判断和getNode的几乎相同，在此不再赘述 10 final Node<K,V> removeNode(int hash, Object key, Object value, 11 boolean matchValue, boolean movable) { 12 Node<K,V>[] tab; Node<K,V> p; int n, index; 13 if ((tab = table) != null && (n = tab.length) > 0 && 14 (p = tab[index = (n - 1) & hash]) != null) { 15 Node<K,V> node = null, e; K k; V v;//node存储要删除的节点 16 if (p.hash == hash && 17 ((k = p.key) == key || (key != null && key.equals(k)))) 18 node = p; 19 else if ((e = p.next) != null) { 20 if (p instanceof TreeNode) 21 node = ((TreeNode<K,V>)p).getTreeNode(hash, key); 22 else { 23 do { 24 if (e.hash == hash && 25 ((k = e.key) == key || 26 (key != null && key.equals(k)))) { 27 node = e; 28 break; 29 } 30 p = e;//p记录上一个节点 31 } while ((e = e.next) != null); 32 } 33 } 34 //找到删除节点并判断matchValue 35 if (node != null && (!matchValue || (v = node.value) == value || 36 (value != null && value.equals(v)))) { 37 //删除节点为TreeNode 38 if (node instanceof TreeNode) 39 ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable); 40 //删除节点为单一节点 41 else if (node == p) 42 tab[index] = node.next; 43 //删除节点为链表 44 else 45 p.next = node.next; 46 ++modCount; 47 --size; 48 afterNodeRemoval(node);//LinkedHashMap中实现，在此为空 49 return node; 50 } 51 } 52 return null; 53 }
1 //直接将table内所有元素置为null 2 //剩下的就交给GC完成 3 public void clear() { 4 Node<K,V>[] tab; 5 modCount++; 6 if ((tab = table) != null && size > 0) { 7 size = 0; 8 for (int i = 0; i < tab.length; ++i) 9 tab[i] = null; 10 } 11 }
在JDK1.8中还增加了一些关于“默认值“和”指定值”增删改查的功能，在这里不再详细分析，
只给出方法签名和用处，代码本身也比较简单，感兴趣的可以自己去了解一下。
1 //获取指定key对应的value，获取失败则返回defaultValue 2 public V getOrDefault(Object key, V defaultValue) 3 4 //只有key在原表中不存在时才插入 5 public V putIfAbsent(K key, V value) 6 7 //移除指定key-value的节点，有一个不对应都不移除 8 public boolean remove(Object key, Object value) 9 10 //替换指定key中的值，若原值不为oldValue不替换 11 public boolean replace(K key, V oldValue, V newValue)
HashMap的遍历
Map和LIst不同，因为Map有两个泛型参数，所以进行遍历的时候一个迭代器不能满足所有迭代需求，
熟悉HashMap的同学应该知道，JDK提供了3个便于我们访问的方法，而其返回的对应是3个集合。
这3个方法是values()，keySet()，EntrySet()。
从命名和Map我们都可以知道，后两个是不能重复的Set，而第一个只是Collection，
更值得一提的是，他们都是HashMap的内部类，在这里只用EntrySet()来举例，其他两个都差不多甚至更简单。
1 public Set<Map.Entry<K,V>> entrySet() { 2 Set<Map.Entry<K,V>> es; 3 return (es = entrySet) == null ? (entrySet = new EntrySet()) : es; 4 } 5 6 final class EntrySet extends AbstractSet<Map.Entry<K,V>> { 7 //返回set的长度，也就是HashMap的元素多少 8 public final int size() { return size; } 9 //直接调用HashMap的clear 10 public final void clear() { HashMap.this.clear(); } 11 //返回这个Set的迭代器 12 public final Iterator<Map.Entry<K,V>> iterator() { 13 return new EntryIterator(); 14 } 15 //判断Set是否包含某个Map.Entry，核心是调用getNode 16 public final boolean contains(Object o) { 17 if (!(o instanceof Map.Entry)) 18 return false; 19 Map.Entry<?,?> e = (Map.Entry<?,?>) o; 20 Object key = e.getKey(); 21 Node<K,V> candidate = getNode(hash(key), key); 22 return candidate != null && candidate.equals(e); 23 } 24 //删除某个节点，核心是调用removeNode 25 public final boolean remove(Object o) { 26 if (o instanceof Map.Entry) { 27 Map.Entry<?,?> e = (Map.Entry<?,?>) o; 28 Object key = e.getKey(); 29 Object value = e.getValue(); 30 return removeNode(hash(key), key, value, true, true) != null; 31 } 32 return false; 33 } 34 35 //返回并行用的迭代器，在这不详细说明 36 public final Spliterator<Map.Entry<K,V>> spliterator() 37 public final void forEach(Consumer<? super Map.Entry<K,V>> action) 38 }
可能有的同学会问了，为什么不用Node<K,V>而要用Entry<K,V>呢，搞的还要转换。
因为之前版本都是用的Entry，突然改成Node会使很多代码要重写，不太合适，而且Entry在遍历的时候已经足够使用。
遍历的时候仍是采取了迭代器的方式。
1 final class EntryIterator extends HashIterator 2 implements Iterator<Map.Entry<K,V>> { 3 public final Map.Entry<K,V> next() { return nextNode(); } 4 } 5 6 abstract class HashIterator { 7 Node<K,V> next; // 下一个要返回的Node 8 Node<K,V> current; // 现在光标所指Node 9 int expectedModCount; // 快速失败用 10 int index; // 现在光标索引 11 12 HashIterator() { 13 expectedModCount = modCount; 14 Node<K,V>[] t = table; 15 current = next = null; 16 index = 0; 17 if (t != null && size > 0) {//找到第一个不为空的节点 18 do {} while (index < t.length && (next = t[index++]) == null); 19 } 20 } 21 22 public final boolean hasNext() { 23 return next != null; 24 } 25 26 final Node<K,V> nextNode() { 27 Node<K,V>[] t; 28 Node<K,V> e = next; 29 if (modCount != expectedModCount) 30 throw new ConcurrentModificationException(); 31 if (e == null) 32 throw new NoSuchElementException(); 33 //找到下一个节点 34 if ((next = (current = e).next) == null && (t = table) != null) { 35 do {} while (index < t.length && (next = t[index++]) == null); 36 } 37 return e; 38 } 39 40 //移除当前元素，核心是removeNode 41 public final void remove() { 42 Node<K,V> p = current; 43 if (p == null) 44 throw new IllegalStateException(); 45 if (modCount != expectedModCount) 46 throw new ConcurrentModificationException(); 47 current = null; 48 K key = p.key; 49 removeNode(hash(key), key, null, false, false); 50 expectedModCount = modCount; 51 } 52 }
可以发现，EntrySet的迭代器和HashMap中数据内容是息息相关的，
也就是说是互相影响的，这也是HashMap不能在多线程使用的原因之一。