HashMap和CocurrentHashMap源码介绍
先介绍HashMap
要了解hashmap首先需要了解哈希表。
关于哈希表，可以简单理解成是一个主干数组，每传入一个参数的时候，可以通过一个Key去获得想要的位置，从而获取对应的数组值。而通过key去获取数组的位置，就成了哈希表的关键。
一般我们都会通过hashCode方法将一个key转化成哈希值，再通过哈希值去获取数组下标。
我用一张图解释一下
1024555-20161113180447499-1953916974.png
介绍完哈希表，那么我们继续介绍一下hashmap的一些关键参数
/**
* 阈值，代表当前哈希表的主干数组最大有多少个，默认是16
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* The load factor used when none specified in constructor.
* 负载因子，代表当前最多可以存储多少个value值
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 哈希表的主干数组
*/
transient Entry<K,V>[] table;
再介绍一下HashMap的一个重要内部类
static class Entry<K,V> implements Map.Entry<K,V> { final K key;
V value;
Entry<K,V> next; //存储指向下一个Entry的引用，单链表结构 int hash;//对key的hashcode值进行hash运算后得到的值，存储在Entry，避免重复计算
/** * Creates new entry. */
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
}
可以看出，其实这是一个
除了自身带有key 和value的对象外，还有下一个节点值。是不是很像链表的一个节点？
接着直接看put方法
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;
}
简单总结一下就是
1.如果table为空，那么初始化table
2.将当前的key转化为hash值
3.通过哈希值获取在数组中的index
4.如果当前Key已存在，就进行覆盖。
再看一下get
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();
}
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;
}
1.通过key获取哈希值
2.通过哈希值获取当前数组下表index
3.获取数组下表以后就等于获取了当前链表的第一个节点
4.依次遍历链表找出最终对应Key的节点
哈希冲突
刚才我们看到，获取数组table的节点以后，会再获取当前节点的下一个节点，这是为什么呢？
因为这里就涉及到了一个节点冲突的问题。简单点将就是，不同的Key通过哈希转化以后，可能得到同一个index。如果出现了这种现象，当前的hash值通过拉链法去解决。
何为拉链法呢，就是其实table的每一个值都是一个节点，对应一条链表。当我们发现当前的Key所对应数组下标的value中，已经有值，我们就把新的节点挂在当前节点的后方，形成链表。
所以我们上面的get方法就可以看出，获取到tab的一个值之后，还需要循环当前链表。
用一张图来简单描述一下hashMap的数据结构
1024555-20161113235348670-746615111.png
从这里开始我们可以发现，hashMap的操作请求都没有做同步处理，所以HashMap也就不是线程安全。基于这种情况，jdk又推出了ConcurrentHashMap。也就是在HashMap的基础上增加了线程安全的逻辑。
ConcurrentHashMap
相比HashMap，ConcurrentHashMap是由Segment 的数组组成，这个数组的个数一共是16个，每一个Segment则是继承了RenteenLock。这样等于每一个Segment都是一个分段锁，可以实现同时16个线程的操作。而Segment里面的每一个值，就可以理解成是一个HashMap，只是增加了线程同步的HashMap。
先用一张图介绍一下：
3.png
然后我们再来看一下Segment的源码
接着就来分析一下put的操作
public V put(K key, V value) {
Segment<K,V> s;
if (value == null)
throw new NullPointerException();
// 1. 计算 key 的 hash 值
int hash = hash(key);
// 2. 根据 hash 值找到 Segment 数组中的位置 j
// hash 是 32 位，无符号右移 segmentShift(28) 位，剩下低 4 位，
// 然后和 segmentMask(15) 做一次与操作，也就是说 j 是 hash 值的最后 4 位，也就是槽的数组下标
int j = (hash >>> segmentShift) & segmentMask;
// 刚刚说了，初始化的时候初始化了 segment[0]，但是其他位置还是 null，
// ensureSegment(j) 对 segment[j] 进行初始化
if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; recheck
(segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment
s = ensureSegment(j);
// 3. 插入新值到 槽 s 中
return s.put(key, hash, value, false);
}
1.首先根据Key获取哈希值
2.获取哈希值之后通过特定的算法获取Segments数组对应的下标
3.通过下标获取当前key的节点所在的Segment
4.获取到Segment之后，其实就是Segment内部的操作了
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
// 在往该 segment 写入前，需要先获取该 segment 的独占锁
// 先看主流程，后面还会具体介绍这部分内容
HashEntry<K,V> node = tryLock() ? null :
scanAndLockForPut(key, hash, value);
V oldValue;
try {
// 这个是 segment 内部的数组
HashEntry<K,V>[] tab = table;
// 再利用 hash 值，求应该放置的数组下标
int index = (tab.length - 1) & hash;
// first 是数组该位置处的链表的表头
HashEntry<K,V> first = entryAt(tab, index);
// 下面这串 for 循环虽然很长，不过也很好理解，想想该位置没有任何元素和已经存在一个链表这两种情况
for (HashEntry<K,V> e = first;;) {
if (e != null) {
K k;
if ((k = e.key) == key ||
(e.hash == hash && key.equals(k))) {
oldValue = e.value;
if (!onlyIfAbsent) {
// 覆盖旧值
e.value = value;
++modCount;
}
break;
}
// 继续顺着链表走
e = e.next;
}
else {
// node 到底是不是 null，这个要看获取锁的过程，不过和这里都没有关系。
// 如果不为 null，那就直接将它设置为链表表头；如果是null，初始化并设置为链表表头。
if (node != null)
node.setNext(first);
else
node = new HashEntry<K,V>(hash, key, value, first);
int c = count + 1;
// 如果超过了该 segment 的阈值，这个 segment 需要扩容
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node); // 扩容后面也会具体分析
else
// 没有达到阈值，将 node 放到数组 tab 的 index 位置，
// 其实就是将新的节点设置成原链表的表头
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;
break;
}
}
} finally {
// 解锁
unlock();
}
return oldValue;
}
1.获取同步锁加锁
2.逻辑基本和HashMap的一致就不再详细说明了，上面注释已经很详细了
3.要注意在finally中会释放锁。
java 1.7和1.8的区别
由于会出现链表冲突导致一个数组的链表特别长的情况，1.8将通过链表去解决节点冲突的方式改成了红黑树。
