一 功能简介
hashMap与concurrentHashMap 都属于集合，用于存储键值对数据，它两最明显的区别是，hashMap是非线程安全的，concurrentHashMap是线程安全的，
concunrrentHashMap还有另外的称呼，如 并发容器
概述
HashMap
jdk 1.7
实现方式：底层 数组+链表
jdk 1.8
实现方式：底层 数组+链表+红黑树
初始大小：16
负载因子：0.75
扩容：newSize = oldSize*2; map中元素总数超过Entry数组的75%，触发扩容操作
存放键值对要求：key 和 value 都允许为null,这种key只能有1个
线程安全性：不安全
父类：AbstractMap
ConcurrentHashMap
jdk 1.7
实现方式：底层 segment数组 + hashEntry数组+链表
segment 数组初始化：在申明ConcurrentHashMap对象的时候
jdk 1.8
实现方式：底层 node数组+链表+红黑树
node数组初始化：put()第一个元素的时候
默认初始大小 16
负载因子：0.75
线程安全
父类 AbstractMap
二 实现逻辑
2.1 hashMap的内部实现逻辑
JDK1.7
hashmap 里面是一个数组，数组中每个元素是一个Entry类型的实例
每个Entry的实例包含4个属性，hash,key,value,next
当put进入某个（key,value）时，会对key取hashcode 后再hash，获取到散列地址，相同散列地址的键值对，存放到同一个链表上（默认放链表头）
扩容顺序：先扩容再插入新值
1） hashMap的实现原理
结构图如下
HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么查找，添加等操作很快，仅需一次寻址即可；
如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。
所以，性能考虑，HashMap中的链表出现越少，性能才会越好。
HashMap中 Entry节点怎么存储？
散列表table是1个Entry数组(上图0到6分别为table数组的下标 )保存Entry实例，
对于hash冲突：在开散列中，如果若干个entry计算得到相同的散列地址（不同的key也可能计算出相同的散列地址），这些entry 被组织成一个链表，以table[i]为头指针
hash方法() 代码
目的为了散列均匀，后续会有用到
// 计算指定key的hash值，原理是将key的hash code与hash code无符号向右移16位的值，执行异或运算。
// 在Java中整型为4个字节32位，无符号向右移16位，表示将高16位移到低16位上，然后再执行异或运行，也
// 就是将hash code的高16位与低16位进行异或运行。
// 小于等于65535的数，其高16位全部都为0，因而将小于等于65535的值向右无符号移16位，则该数就变成了
// 32位都是0，由于任何数与0进行异或都等于本身，因而hash code小于等于65535的key，其得到的hash值
// 就等于其本身的hash code。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
put(key,value)方法 源码
把元素加入HashMap中
public V put(K key, V value) { //如果table数组为空数组{}，进行数组填充（为table分配实际内存空间），入参为threshold， //此时threshold为initialCapacity 默认是1<<4(24=16) if (table == EMPTY_TABLE) { inflateTable(threshold); } //如果key为null，存储位置为table[0]或table[0]的冲突链上 if (key == null) return putForNullKey(value); int hash = hash(key);//对key的hashcode进一步计算，确保散列均匀 int i = indexFor(hash, table.length);//获取在table中的实际位置 for (Entry<K,V> e = table[i]; e != null; e = e.next) { //如果该对应数据已存在，执行覆盖操作。用新value替换旧value，并返回旧value Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++;//保证并发访问时，若HashMap内部结构发生变化，快速响应失败 addEntry(hash, key, value, i);//新增一个entry return null; }
上面代码中 addEntry()方法 源码
void addEntry(int hash, K key, V value, int bucketIndex) { if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length);//当size超过临界阈值threshold，并且即将发生哈希冲突时进行扩容 hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } createEntry(hash, key, value, bucketIndex); }
通过以上addEntry()代码能够得知，当发生哈希冲突并且size大于阈值（负载因子*初始大小）的时候，需要进行数组扩容，扩容时，需要新建一个长度为之前数组2倍的新的数组，
然后将当前的Entry数组中的元素全部传输过去（重新计算散列地址），扩容后的新数组长度为之前的2倍，所以扩容相对来说是个耗资源的操作。
transfer() 扩容方法
void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; //for循环中的代码，逐个遍历链表，重新计算索引位置，将老数组数据复制到新数组中去（数组不存储实际数据，所以仅仅是拷贝引用而已） for (Entry<K,V> e : table) { while(null != e) { Entry<K,V> next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); //将当前entry的next链指向新的索引位置,newTable[i]有可能为空，有可能也是个entry链，如果是entry链，直接在链表头部插入。 e.next = newTable[i]; newTable[i] = e; e = next; } } }
将老数组中的值，复制到新数组中（此过程中要重新计算元素的数组下标，部分元素会移动位置）
计算数组下标：
Hash值与该数组的长度减去1做与运算，如下所示：
int indexFor(int hash,int tableLength)
{
index = (tableLength - 1) & hash
}
获取到数组下标的流程图如下
先取key的hashcode()值，然后再重散列（hash）一次（为了散列的更加均匀） ，再用上面公式取下标。
get(key)方法 源码
public V get(Object key) { //如果key为null,则直接去table[0]处去检索即可。 if (key == null) return getForNullKey(); Entry<K,V> entry = getEntry(key); return null == entry ? null : entry.getValue(); }
get方法通过key值返回对应value，如果key为null，直接去table[0]处检索。我们再看一下getEntry这个方法
上面代码中 getEntry()源码
final Entry<K,V> getEntry(Object key) { if (size == 0) { return null; } //通过key的hashcode值计算hash值 int hash = (key == null) ? 0 : hash(key); //indexFor (hash&length-1) 获取最终数组索引，然后遍历链表，通过equals方法比对找出对应记录 for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } return null; }
get方法的实现相对简单，key(hashcode)–>hash–>indexFor–>最终索引位置，找到对应位置table[i]
再查看是否有链表，遍历链表，通过key的equals方法比对查找对应的记录
2） 重写equals方法需同时重写hashCode方法
老生常谈的问题，网上经常看到说 "重写equals时也要同时覆盖hashCode"
我们来看下，如果不重写会hashCode 会怎样 如何？
public class NotOverrideHashOrEquesTest { public static class Person { //任务id private int id; //名字 private String name; public Person(int id, String name) { this.id = id; this.name = name; } public int getId() { return id; } public void setId(int id) { this.id = id; } public String getName() { return name; } public void setName(String name) { this.name = name; } //重写equas方法 @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Person person = (Person) o; return id == person.id; } } @Test public void mainTest() { Map<Person, String> map = new HashMap<>(); Person person = new Person(11, "乔峰"); //往集合内添加元素 map.put(person, "降龙十八掌"); //取出元素 String getResult = map.get(new Person(11,"萧峰")); System.out.println("结果:"+getResult); }
实际输出结果：null
如果我们已经对HashMap的原理有了一定了解，这个结果就不难理解了。尽管我们在进行get和put操作的时候，使用的key从逻辑上讲是等值的（通过equals比较是相等的），
但由于没有重写hashCode方法，所以put操作时，key取hashCode1–>再hash–>indexFor–>最终索引位置 ，而通过key取出value的时候 key取hashCode2–>再hash–>indexFor–>最终索引位置，
由于hashcode1不等于hashcode2，导致没有定位到一个数组位置而返回逻辑上错误的值null（也有可能碰巧定位到一个数组位置，但是也会判断其entry的hash值是否相等，上面get方法中有提到。）
3） 为什么容量（即数组长度）要设计为2的N次幂？
- 在put方法中，计算数组下标，容量设计成2的n次幂能使下标相对均匀，减少哈希碰撞
- 在扩容相关的transfer方法中，也有调用indexFor重新计算下标。容量设计成2的n次幂能使扩容时重新计算的下标相对稳定，减少移动元素
JDK 1.8 HashMap
进行了优化，如果链表中元素( Node节点 Node implements Entry)超过8个链表才能转成红黑树（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树），就转换为红黑树（节点Node也转为treeNode），以减少查询的复杂度 O(logN)，如果红黑树中元素低于6个，则从红黑树转回链表。
Node 节点
static class Node<K,V> implements Map.Entry<K,V> { final int hash;//当前Node的Hash值 final K key;//当前Node的key V value;//当前Node的value Node<K,V> next;//表示指向下一个Node的指针，相同hash值的Node，通过next进行遍历查找 Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } ...... }
TreeNode节点
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // red-black tree links TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev; // needed to unlink next upon deletion boolean red; TreeNode(int hash, K key, V val, Node<K,V> next) { super(hash, key, val, next); } ...... }
可以看到TreeNode使用的是红黑树（Red Black Tree）的数据结构
put() 方法源码
2.2 ConcurrentHashMap 的实现逻辑
JDK 1.7
ConcurrentHashMap的思路和HashMap思路是差不多，但是因为它支持并发操作，所以要复杂一些，
整个ConcurrentHashMap由16个Segment组成，Segment代表“部分” 或 “一段”的意思，所以很多地方将其描述为分段锁，
ConcurrentHashMap是一个Segment数组， 其中 Segment 通过继承 ReentrantLock 来进行加锁，即每个锁锁住一个Segment，这样保证线程安全
ConcurrentHashMap初始化时，计算出Segment数组的大小ssize（默认16，也可自行指定）和每个Segment中HashEntry数组的大小cap，并初始化Segment数组的第一个元素；
其中ssize大小为2的幂次方，默认为16，cap大小也是2的幂次方，最小值为2，
ConcurrentHashMap的扩容，长度初始化后，无法对 Segment数组进行扩容的，扩容是对Segment里面 的数组（HashEntry数组）进行扩容，每个Segment 想当于一个线程安全的hashMap
扩容按2倍扩容，当元素个数>阈值（数组长度*负载值） 触发扩容
put()方法
当执行put方法插入数据的时候，根据key的hash值，在Segment数组中找到对应的位置
如果当前位置没有值，则通过CAS进行赋值，接着执行Segment的put方法通过加锁机制插入数据
假如有线程AB同时执行相同Segment的put方法
线程A 执行tryLock方法成功获取锁，然后把HashEntry对象插入到相应位置
线程B 尝试获取锁失败，则执行scanAndLockForPut()方法，通过重复执行tryLock()方法尝试获取锁
在多处理器环境重复64次，单处理器环境重复1次，当执行tryLock()方法的次数超过上限时，则执行lock()方法挂起线程B
当线程A执行完插入操作时，会通过unlock方法施放锁，接着唤醒线程B继续执行
size实现
统计每个segment对象中的元素个数，然后进行累加
但是这种方式计算出来的结果不一定准确
因为在计算后面的segment的元素个数时
前面计算过了的segment可能有数据的新增或删除
计算方式为：
先采用不加锁的方式，连续计算两次
如果两次结果相等，说明计算结果准确
如果两次结果不相等，说明计算过程中出现了并发新增或者删除操作
于是给每个segment加锁，然后再次计算
扩容机制
JDK 1.8
1.8中放弃了Segment分段锁的设计，使用的是Node+CAS+Synchronized来保证线程安全性
只有在第一次执行put方法是才会初始化Node数组
数据结构组成是： Node数组+链表+红黑树
put（）方法
当执行put方法插入数据的时候，根据key的hash值在Node数组中找到相应的位置
如果当前位置的Node还没有初始化，则通过CAS插入数据
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { //如果当前位置的`Node`还没有初始化，则通过CAS插入数据 if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))) break; // no lock when adding to empty bin }
如果当前位置的Node已经有值，则对该节点加synchronized锁，然后从该节点开始遍历，直到插入新的节点或者更新新的节点
if (fh >= 0) { binCount = 1; for (Node<K,V> e = f;; ++binCount) { K ek; if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { oldVal = e.val; if (!onlyIfAbsent) e.val = value; break; } Node<K,V> pred = e; if ((e = e.next) == null) { pred.next = new Node<K,V>(hash, key, value, null); break; } } }
如果当前节点是TreeBin类型，说明该节点下的链表已经进化成红黑树结构，则通过putTreeVal方法向红黑树中插入新的节点
else if (f instanceof TreeBin) { Node<K,V> p; binCount = 2; if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) { oldVal = p.val; if (!onlyIfAbsent) p.val = value; } }
如果binCount不为0，说明put操作对数据产生了影响，如果当前链表的节点个数达到了8个，则通过treeifyBin方法将链表转化为红黑树
size实现
使用一个volatile类型的变量baseCount记录元素的个数
当新增或者删除节点的时候会调用，addCount()更新baseCount
扩容机制
当往Map中插入结点时，如果链表的结点数目超过一定阈值（8），就会触发链表 -> 红黑树的转换：
if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i);
现在，我们来分析下treeifyBin这个红黑树化的操作：
/** * 尝试进行 链表 -> 红黑树 的转换. */ private final void treeifyBin(Node<K, V>[] tab, int index) { Node<K, V> b; int n, sc; if (tab != null) { // CASE 1: table的容量 < MIN_TREEIFY_CAPACITY(64)时，直接进行table扩容，不进行红黑树转换 if ((n = tab.length) < MIN_TREEIFY_CAPACITY) tryPresize(n << 1); // CASE 2: table的容量 ≥ MIN_TREEIFY_CAPACITY(64)时，进行链表 -> 红黑树的转换 else if ((b = tabAt(tab, index)) != null && b.hash >= 0) { synchronized (b) { if (tabAt(tab, index) == b) { TreeNode<K, V> hd = null, tl = null; // 遍历链表，建立红黑树 for (Node<K, V> e = b; e != null; e = e.next) { TreeNode<K, V> p = new TreeNode<K, V>(e.hash, e.key, e.val, null, null); if ((p.prev = tl) == null) hd = p; else tl.next = p; tl = p; } // 以TreeBin类型包装，并链接到table[index]中 setTabAt(tab, index, new TreeBin<K, V>(hd)); } } } } }
从代码我们可以看出，其实并不是直接就一股脑转红黑树
上述第一个分支中，还会再对table数组的长度进行一次判断：
如果table长度小于阈值MIN_TREEIFY_CAPACITY——默认64，则会调用tryPresize方法把数组长度扩大到原来的两倍。
从代码也可以看到，链表 -> 红黑树这一转换并不是一定会进行的，table长度较小时，CurrentHashMap会首先选择扩容，而非立即转换成红黑树
三 hashMap与hashTable 差异
| 属性 | hashMap（1.7及以前） | hashTable |
| 初始大小 | 16 | 11 |
| 负载因子 | 0.75 | 0.75 |
| 扩容机制 | 2N | 2N+1 |
| 数据结构 | 数组+entry链表 | 数组+entry链表 |
| 线程安全 | 不安全 | 安全（方法syncnozied） |
| 父类 | AbstractMap | Dictionary(已废弃) |
| key可否为null | 可以，默认hash值为0 放到了数组[0]处 | 抛异常 |
| hash值算法 | 用hashcode再计算hash值 | hashcode与数组长度取模 |
| 性能 | 高 | 相对较低（因为线程安全） |
| 使用场景 | 不需要线程安全时，用 | 需要线程安全时可用，不过已经不推荐使用，其父类已废弃 |