最近面试屡屡碰壁，。孔子他老人家曾经说过：“吾日三省吾身”，所以自己对面试过程进行了一个详细的回忆和反省。换位思考，如果我是面试官我会不会聘用我自己，我惊奇的发现答案是”不会“。反省过后才认识到了自己的很多不足，有种自己是一个自以为是的井底之蛙的感觉。了解到很多知识点，但是都没有很深入。所以面试官往深处一问，基本都是懵逼的状态。这时候才认识到自己需要一个长足的提高以及深入的学习过程。并把自己的学习历程已经经验记录下来。不管是为自己以后回忆还是分享给更多的后来者，同时也帮助更多的人避坑。必须要记录下来。
第一篇当然是深入研究下面试题必问之HashMap原理剖析，本文基于jdk1.8HasMap源码
1、什么是哈希表
在研究HashMap之前还需要把数据结构书中的知识捡回来，哈希表和链表、二叉树、线性表一样是一种数据结构。相比较其他数据结构哈希表对应插入、查找、删除的效率十分之高，时间复杂度是O(1)。下面来研究下是怎么实现达到惊艳的O(1)的时间复杂度。
使用过HashMap的人都知道，HasMap可以给我们存储key-value。我们从这个角度去分析HashMap实现O(1)时间复杂度的基本逻辑。我们知道数组元素可根据下标一次定位即可查到。同样哈希表的主干就是数组。
比如说我们要把<"kobe",1>,<"james",2>两个键值对插入到哈希表，首先会把key通过某个函数（我们叫哈希函数f）映射到数组的某个位置。即存储在数组的index等于
index=f(key)
图一 哈希表基本原理
查找同理，先通过哈希函数算出实际存储地址，然后从数组中去除即可。
哈希冲突
当我们对某个元素进行哈希运算，算出的存储地址发现被其他元素占用了，这就是所谓的哈希冲突。解决哈希冲突的方法有：开放定址（发生冲突继续寻找下一块未被占用的的存储地址），再散列行数法、链地址法。而HashMap即是采用了链地址法，也就是数组+链表的方式
二、HashMap的类图
直接上类图描述下HashMap的类结构关系
图一 HashMap的类图
三、HashMap的实现原理
HasMap的主干是一个Node数组，Node是实现了Map.Entry接口。其中Node是HashMap的基本组成单元，每个Node包含了一个key-value键值对。
Node是HashMap的静态内部类：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
....
}
下面来看看Node数组table的定义和初始化位置：
transient Node<K,V>[] table;
在初始化位置并没有table的一个初始化操作，贴出我们常用的new HashMap（）构造函数
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
扶了一把眼镜，你没有看错就是一行代码！！，设置负载因子为默认负载因子。那初始化在哪里呢(摸了摸仅剩了几根头发)？
顿时脑海中想起了一个词，懒加载！！用的时候再加载初始化。顺着这个方向我们继续分析下HashMap的put方法，不多说，贴代码
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
....
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)
//如果table为空，调用resize方法，第一次put都为空。resize是HashMap的扩容方法
n = (tab = resize()).length;
//如果主干数组对应的索引值==null,也就是对应主干数组没有元素，则new一个Node插入到主干数组中.
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//否则
else {
Node<K,V> e; K k;
//如果hash值和key都相同，也就是put相同的key，替换Node
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果元素属于TreeNode的对象，What?这是什么鬼。查看资料后是红黑树的结点
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
//链表中数目大于8转化为红黑树
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
put方法中信息量还是比较足的。前面我们提到HashMap中处理哈希冲突的方法是数组+链表，但是在jdk1.8以后做了如下处理如果链表中长度大于等于8，链表将转化为红黑树，转化为数组+链表+红黑树。我们还了解到如果put相同的key值会覆盖掉原来的结点。具体原理图如下：
图三 HashMap数据结构原理图
分析到这里我们大概了解了HashMap的基本原理，当时我们还是没有追踪到Node table的new过程。我们继续分析resize()方法,首先我们来看下源码中的注释：
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
大概意思就是初始化和扩容table为原来的两倍。如果为空，分配位于初始化值和阈值之间的容量。另外使用了2次幂扩展，每个元素在新表中的索引要么保持原来的索引要么是2次幂的偏移量。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold; //老阈值
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) { //如果阈值大于最大容量，不再扩容直接返回
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold //左移一位也就是乘于2
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults //就是这里了，当老阈值为0，也就是未初始化的时候，使用默认容量初始化table
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
根据以上分析，我们可以获取到的信息是HashMap的默认初始化容量为16，最大初始化容量1<<30。每次扩容原来的两倍。
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 //默认容量
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30; //最大容量
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f; //默认负载因子
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8; //链表转红黑树的阈值
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6; //红黑树转链表的阈值
/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
*/
static final int MIN_TREEIFY_CAPACITY = 64; //转红黑树，table的最小长度
还有get，entrySet等方法暂时不作解析。我们阅读源码看到HashMap的没有做任何同步操作，所以HashMap不是线程安全的。
其中线程安全可以考虑使用HashTable和ConcurrentHashMap:
这里我们在简要谈一下HashTable和ConcurrentHashMap
1、Hashtable
Hashtable使用的是数组+链表的形式处理哈希冲突
Hashtable使用了synchronized同步，线程安全。不过会拿Hashtable对象的锁，会锁住整个哈希表（全局加锁）
Hashtable默认容量为11、负载因子为0.75、最大容量是Integer.MAX_VALUE-8
Hashtable不允许key和value为null，会throw空指针异常
2、ConcurrentHashMap
线程安全，避免了对全局加锁改成了局部Segment加锁操作
ConcurrentHashMap定位一个元素的过程需要进行两次Hash操作
jdk1.8使用的是synchronized+CAS+HashEntry+红黑树
ConcurrentHashMap原理图
后续有时间会详细分析ConcurrentHashMap的实现原理，这里不再多说。
由于笔者水平有限，如有错误还请指正！！
网友评论