HashMap是使用数组+链表+红黑树的方式构成的，它与ConcurrentHashMap的主要区别就是一个是线程不安全，一个是线程安全，在代码上可能会有些差别，但是在计算容量，定位 索引等原理上是基本差不多的，想要更多的了解ConcurrentHashMap，请转移到ConcurrentHashMap博文。
HashMap的计算某个key值的hash操作和ConcurrentHashMap是一样的，以下是HashMap计算hash值和进行索引定位的代码
//计算hash值 static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } //索引定位 tab[i = (n - 1) & hash]调用key自身的hashCode方法得到hash值，然后与hash值的高16进行异或。这么做是为了进行hash扰乱，将高16的变化能够得到体现。如果我们HashMap的数组的容量小于2的16次 方，而大部分的hash值都在高16位进行变化，那么他们进行 hash & (n - 1)得到的索引下标将不会变，导致严重的hash冲突，为了避免出现这样的情况，那么就需要将高16位发 生的变化也体现到低16位上。
Q: 为什么是异或而不是什么位或，位与呢？
A: 将一个hash值进行无符号右移之后，高16位为0，如果两个值进行相与，那么高16将全部变成零，丢失了高16，显然是不合适的，再者，如果低16位上某bit位上是零，那么 高16位上与之相对应的bit位即使发生了变化，它位与得到的值依然是0，无法体现出高16位的这种变化，如果是位或，高16位可以得到保留，但是低16位中只要有bit位为1的，那 么得到的bit位就是1，与之相对的高16对应位上的变化无法体现，举个例子
低16位 1001101101001111 1001101101001111 高16位 1001010010001000 --> 改变高位bit位 1001010010001101 --> 只改了第1位和第3位 位或 1001111111001111 1001111111001111 --> 没能体现出高16的第1位和第3位的变化 异或 0000111111000111 0000111111000010 --> 体现出了高16的第1位和第3位的变化再来个更加残酷的例子
低16位 1111111111111111 1111111111111111 高16位 1001010010001000 --> 改变高位bit位 1111111111111111 --> 把高16位的bit位全部设置为1 -------------------- -------------------- 位或 1111111111111111 1111111111111111 --> 不管高16位怎么变，这个值毫无改变，无法体现出高16的任何变化 异或 0000111111000111 0000000000000000 --> 体现出了高16的变化，如果此时高16任何一处的bit变成零，它都能捕捉到它的变化另外，与一个全零的数进行异或等于本身
1001010010001000 ^ 0000000000000000 -------------------- = 1001010010001000所以hash值与hash >>> 16进行异或不仅不会导致高16位丢失，还能把高16的变化体现出来。
Q: 为什么 hash % n = (n - 1) & hash？
A: 首先先声明，只有当n为2次幂的值的时候，hash % n = (n - 1) & hash，为什么呢？hash对一个2次幂的值进行求余的时候，我们知道 hash / 2 ^ n = hash >>> n 其实hash向右移出去的值就是余数，对于一个n为2次幂的整数值，它的所有bit位上只有一个1，比如 16 = 000…10000，它是2的4次方的值，hash / 2 ^ 4 = hash >>> 4, 如果此时我们要得到hash被移出去的4位bit位怎么办？ 那当然是 hash & 000…01111 = hash & (16 - 1) 把16替换成n就变成了hash & (n - 1)
首先检查是否已经初始化过，如果初始化过，那么扩容为原来的2倍，如果原来的容量大于默认的容量，那么相应的阈值也直接扩容为原来的2倍 要是还没有初始化，那么设置默认的容量
上面这段迁移代码除了没有锁，cas之外，原理和ConcurrentHashMap是一样的，感兴趣的可以移步到博文ConcurrentHashMap。HashMap在迁移链表和红黑树节点的时候，没有重 新计算节点的位置，而是通过 hash & oldCap 的方式去确定他们的位置，原理如下：
oldCap = 000...0010000 newCap = 000...0100000新容量与旧容量的二进制相比，就是左移了一位，当他们减去1的时候
oldCap - 1 = 000...0001111 newCap - 1 = 000...0011111当一个hash与上面两个值进行位与的时候，如果这个hash值的第5位的bit值为零，那么算出来的下标和原来是一样的，如果这个bit位为1，那么算出来的下标就是 oldIndex + oldCap
关于红黑树的部分可以移步到博文TreeMap
对于keySet我们主要研究下对应的迭代器KeyIterator
public final Iterator<K> iterator() { return new KeyIterator(); } | | V // KeyIterator 继承自 HashIterator HashIterator() { //modCount是记录HashMap的修改次数 expectedModCount = modCount; Node<K,V>[] t = table; current = next = null; index = 0; if (t != null && size > 0) { // advance to first entry do { //跳过null值，直到找到下一个节点 } while (index < t.length && (next = t[index++]) == null); } } final class KeyIterator extends HashIterator implements Iterator<K> { //next public final K next() { return nextNode().key; } }判断是否存在下一个节点
public final boolean hasNext() { return next != null; }获取下一个节点
final Node<K,V> nextNode() { Node<K,V>[] t; Node<K,V> e = next; //如果在循环的过程中，HashMap发生改变，那么抛出错误 if (modCount != expectedModCount) throw new ConcurrentModificationException(); if (e == null) throw new NoSuchElementException(); //获取当前链表或者红黑树的下一个节点 if ((next = (current = e).next) == null && (t = table) != null) { do { //跳过null值，直到找到下一个节点链表或者红黑树的头节点 } while (index < t.length && (next = t[index++]) == null); } return e; }下面是HashMap的entrySet方法
public Set<Map.Entry<K,V>> entrySet() { Set<Map.Entry<K,V>> es; return (es = entrySet) == null ? (entrySet = new EntrySet()) : es; }EntrySet使用的迭代器为EntryIterator，它是HashMap的内部类，其实和KeyIterator在原理上是一样的
public final Iterator<Map.Entry<K,V>> iterator() { return new EntryIterator(); }迭代操作
final Node<K,V> nextNode() { Node<K,V>[] t; Node<K,V> e = next; //如果在迭代的过程中发生修改，抛出错误 if (modCount != expectedModCount) throw new ConcurrentModificationException(); if (e == null) throw new NoSuchElementException(); //获取当前链表或者红黑树的下一个节点 if ((next = (current = e).next) == null && (t = table) != null) { do { //循环找到下一个链表或者红黑树的头节点 } while (index < t.length && (next = t[index++]) == null); } return e; }可以看出对视图的操作最终都会反映到HashMap上
除了线程安全，CAS操作，计数机制外，HashMap与ConcurrentHashMap的原理基本一样。除此之外，与之相似的一个集合类叫HashSet，这个HashSet 内部直接关联了一个HashMap，下面是它的构造器
public HashSet() { map = new HashMap<>(); }下面是它的add方法
public boolean add(E e) { return map.put(e, PRESENT)==null; }PRESENT是一个固定的Object对象。
还有一个维护了节点添加顺序的类LinkedHashMap，它继承自HashMap，它除了将值put到HashMap中，它还用两个成员变量，head和tail用于维护一个单独的链表保持添加顺序，其主要逻辑在创建新节点的时候
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) { LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e); //将新创建的节点添加到链表尾部 linkNodeLast(p); return p; } private void linkNodeLast(LinkedHashMap.Entry<K,V> p) { LinkedHashMap.Entry<K,V> last = tail; tail = p; if (last == null) head = p; else { p.before = last; last.after = p; } }当我们调用keySet和entrySet方法的时候，其内部使用的迭代器都是通过LinkedHashMap单独维护的链表进行遍历的。
