本文一是总结后面两种汇合，补充一些脱漏，再者对HashMap进行简略介绍。
回顾
因为前两篇ArrayList和LinkedList都是针对独自的汇合类剖析的，只见树木未见森林，明天剖析HashMap，能够联合起来看一下java中的汇合框架。下图只是一小部分，而且为了不便了解去除了抽象类。
Java中的汇合（有时也称为容器）是为了存储对象，而且少数时候存储的不止一个对象。
能够简略的将Java汇合分为两类：
- 一类是Collection，存储的是独立的元素，也就是单个对象。细分之下，常见的有List，Set，Queue。其中List保障依照插入的顺序存储元素。Set不能有反复元素。Queue依照队列的规定来存取元素，个别状况下是“先进先出”。
- 一类是Map，存储的是“键值对”，通过键来查找值。比方事实中通过姓名查找电话号码，通过身份证号查找集体详细信息等。
实践上说咱们齐全能够只用Collection体系，比方将键值对封装成对象存入Collection的实现类，之所以提出Map，最次要的起因是效率。
HashMap简介
HashMap用来存储键值对，也就是一次存储两个元素。在jdk1.8中，其实现是基于数组+链表+红黑树，简略说就是一般状况间接用数组，产生哈希抵触时在抵触地位改为链表，当链表超过肯定长度时，改为红黑树。
能够简略了解为：在数组中寄存链表或者红黑树。
- 齐全没有哈希抵触时，数组每个元素是一个容量为1的链表。如索引0和1上的元素。
- 产生较小哈希抵触时，数组每个元素是一个蕴含多个元素的链表。如索引2上的元素。
- 当抵触数量超过8时，数组每个元素是一棵红黑树。如索引6上的元素。
下图为示意图，相干构造没有严格遵循标准。
类签名
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable如下图
]
实现Cloneable和Serializable接口，领有克隆和序列化的能力。
HashMap继承抽象类AbstractMap的同时又实现Map接口的起因同样见上一篇LinkedList。
常量
//序列化版本号private static final long serialVersionUID = 362498820763181265L;//默认初始化容量为16static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //最大容量，2的30次方static final int MAXIMUM_CAPACITY = 1 << 30;//默认负载因子，值为0.75static final float DEFAULT_LOAD_FACTOR = 0.75f;//以下三个常量应联合看//链表转为树的阈值static final int TREEIFY_THRESHOLD = 8;//树转为链表的阈值，小于6时树转链表static final int UNTREEIFY_THRESHOLD = 6;//链表转树时的汇合最小容量。只有总容量大于64，且发生冲突的链表大于8才转换为树。static final int MIN_TREEIFY_CAPACITY = 64;上述变量的关键在于链表转树和树转链表的机会，综合看：
- 当数组的容量小于64是，此时不论抵触数量多少，都不树化，而是抉择扩容。
当数组的容量大于等于64时，
- 抵触数量大于8，则进行树化。
- 当红黑树中元素数量小于6时，将树转为链表。
变量
//存储节点的数组，始终为2的幂transient Node<K,V>[] table;//批量存入时应用，详见对应构造函数transient Set<Map.Entry<K,V>> entrySet;//理论寄存键值对的个数transient int size;//批改map的次数，便于疾速失败transient int modCount;//扩容时的临界值，实质是capacity * load factorint threshold;//负载因子final float loadFactor;数组中存储的节点类型，能够看出，除了K和Value外，还蕴含了指向下一个节点的援用，正如一开始说的，节点理论是一个单向链表。
static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; //...省略常见办法}构造方法
常见的无参结构和一个参数的结构很简略，间接传值，此处省略。看一下两个参数的构造方法。
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; //将给定容量转换为不小于其本身的2的幂 this.threshold = tableSizeFor(initialCapacity);}tableSizeFor办法
上述办法中有一个十分奇妙的办法tableSizeFor，它将给定的数值转换为不小于本身的最小的2的整数幂。
static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;}比方cap=10，转换为16；cap=32，则后果还是32。用了位运算，保障效率。
有一个问题，为啥非要把容量转换为2的幂？之前讲到的ArrayList为啥就不须要呢？其实关键在于hash，更精确的说是转换为2的幂，肯定水平上减小了哈希抵触。
对于这些运算，画个草图很好了解，关键在于可能想到这个办法很牛啊。解释的话配图太多，这里篇幅限度，将内容放在另一篇文章，HashMap之tableSizeFor办法图解。
增加元素
在下面构造方法中，咱们没有看到初始化数组也就是Node<K,V>[] table的状况，这一步骤放在了增加元素put时进行。
public V put(K key, V value) { return putVal(hash(key), key, value, false, true);}能够看出put调用的是putVal办法。
putVal办法
在此之前回顾一下HashMap的形成，数组+链表+红黑树。数组对应地位为空，存入数组，不为空，存入链表，链表超载，转换为红黑树。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; //数组为空，则扩容 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //依据key计算hash值得出数组中的地位i，地位i上为空，间接增加。 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); //数组对应地位不为空 else { Node<K,V> e; K k; //对应节点key上的key存在，间接笼罩value if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k)))) e = p; //为红黑树时 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); //为链表时 else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); //链表转换为红黑树 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; //下次增加前需不需要扩容，若容量已满则提前扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null;}resize()办法比较复杂，最好是配合IDE工具，debug一下，比拟容易弄清楚扩容的形式和机会，如果干讲的话反而容易混同。
获取元素
依据键获取对应的值，外部调用getNode办法
public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value;}getNode办法
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 && ((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;}总结
HashMap的内容太多，每个内容相干的知识点也很多，篇幅和集体能力限度，很难讲清所有内容，比方最根底的获取hash值的办法，其实也很考究的。有机会再针对具体的细节缓缓具体写吧。