一、什么是hash
哈希算法
接受任意长度的二进制输入值，对输入值做换算（hash），最终给出固定长度的二进制输出值；
Hash算法不是某个固定的算法，它代表的是一类算法，具体换算可能各不相同
哈希表
即散列表，一种数据结构，根据关键码值(Key value)而直接进行访问
给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数
哈希碰撞
根据上面对哈希表的定义，有一种情况是，对不同的关键字可能得到同一散列地址，即k1≠k2，但f(k1)=f(k2)，这种情况就是哈希碰撞。
解决哈希碰撞
拉链法（hashmap的解决方式）：
将键转换为数组的索引(0-M-1)，但是对于两个或者多个键具有相同索引值的情况，将大小为M 的数组的每一个元素指向一个条链表，链表中的每一个节点都存储散列值为该索引的键值对，这就是拉链法
二、HashMap的实现
基于哈希表的数据结构
线程不安全
下面从代码上来分析HashMap的实现原理
1. HashMap的结构
//实体数组
transient Node<K,V>[] table;
//实体构造函数
static class Node<K,V> implements Map.Entry<K,V> {
Node(int hash,K key,V value,Node<K,V> next){
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;//链表中下一个元素的引用
}
}
由上面的代码可以看出HashMap的基本结构就是:
- 储存的结构是实体Node<K,V>[]，即一个Map.Entry<K,V>。内部4个值，key-value键值对，hash值，以及指向下一个元素的引用next，构成链表。
- 实体Node再构成的一个数组 Node<K,V>[] table
- 而这个结构正是我们上面提到的hash表的结构，并很明显是用拉链法来解决hash冲突
2. put
//使用树而不是列表的bin计数阈值
static final int TREEIFY_THRESHOLD = 8;
public V put(K key, V value) {
// 对key的hashCode()做hash
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab;
Node<K,V> p;
int n, i;
//数组tab为空则创建
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果没有发生hash碰撞，则直接添加到数组tab中
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//发生了hash碰撞
else {
Node<K,V> e; K k;
//是否hash值相同，且key值也相同，即节点已存在
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//hash值相同，且key值也相同
e = p;
//该链是TreeNode
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) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 超过load factor*current capacity，resize
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
由上述代码可以看出put的逻辑
- 对key的hashCode()做hash计算得到hash值
- 根据hash值计算出对应在哈希表的数组中Node<K,V>[] table中的下标：index = (size - 1) & hash
- 如果该下标上没有存放Node<K,V>，即没有发生hash碰撞，则存放到table的该下标上
- 如果该下标上已经有存放Node<K,V>，即发生了hash碰撞，则存放到table的该下标的链表的尾部
- 如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD=8)则会把链表转换成红黑树
- 如果节点已经存在就替换节点的值oldValue为新值
- 如果table已经满了，则resize增加table的长度
3. get()
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
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) {
//直接找到了节点对应在table中的下标
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
//判断该下标下第一个节点的key也相同，则直接返回
return first;
if ((e = first.next) != null) {
//开始遍历链表
if (first instanceof TreeNode)
return
//TreeNode ((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;
}
由上述代码可以看出get的逻辑
- 对key的hashCode()做hash计算得到hash值
- 根据hash值计算出对应在哈希表的数组中Node<K,V>[] table中的下标
- 该下标上的第一个元素fristNode和要查找的key值做判断fristNode.key.equals(key),如果相同，返回
- 如果不相同，遍历链表直到Node.key.equals(key)，返回
4. 扩容resize()
//临界值（HashMap实际能存储的大小）,公式为(threshold = capacity * loadFactor),当hashmap中存储元素大于这个数时，就需要resize了
int threshold;
/** 负载因子,默认为0.75*/
final float loadFactor;
//默认负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//数组默认的大小，16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//数组最大的容量，2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
//旧表大小不为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)
//把新表的阀值设为旧表2倍
newThr = oldThr << 1; // double threshold
}
//如果旧表的长度的是0，则初始化表
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
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;//新表赋值给table
//如果旧表不为空，要把旧表的值转移到新表
if (oldTab != null) {
//遍历旧表
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//node没有链表则直接放在新表的e.hash & (newCap - 1)位置
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//e是treeNode，则拆树
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//e有链表，拆链表
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;
}
由上述代码可以看出reSize的逻辑
- 先判断旧表，如果没有旧表，则初始化一个默认大小的新表或者构造函数中传入过的initialCapacity大小的新表（默认大小16；阀值为12；16*0.75），
- 如果有旧表，则初始化一个新表，大小为旧表的两倍，阀值也是旧表的两倍
- 把旧表的值转移到新表
5. loadFactor和initialCapacity：
loadFactor负载因子，代表的是map的装填程度，构造函数中有
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +loadFactor);
表示loadFactor必须是大于0的数字。
由前面的知识我们知道HashMap是有数组table和链表的来实现的
initialCapacity表示HashMap的初始化数组table的大小
而HashMap的实际容量 = initailCapacity*loadFactor
当HashMap的实际容量满的时候，才会进行resize扩充容量
由此可知loadFactor越大，则HashMap中table会填的越满，链表会越长，越容易发生hash碰撞，造成索引效率低下；反之则会越稀疏，但会造成空间浪费。
loadFactor根据情况进行设置（时间空间选择）
注意：initailCapacity的值系统会根据传入的值换算成比传入值大的最接近的2的n次方这是因为
table下标计算：index = (size - 1) & hash
如当数组长度为15的时候，hashcode的值会与size - 1=14（1110）进行“与”，那么最后一位永远是0，而0001，0011，0101，1001，1011，0111，1101这几个位置永远都不能存放元素了，空间浪费相当大
6. 使用注意：
- reSize()比较耗性能的（主要是旧表的值转移到新表）,所以初始化的时候最好能初始化合适的大小
- HashMap hashMap = new HashMap(1000); 初始化后的表的大小为1024,即总是比传入值大的最小的2的n次方。这是因为数组长度为2的n次方的时候，不同的key算得得index相同的几率较小，可以减少hash碰撞，从而提高效率
- jdk8中，HashMap处理碰撞才增加了红黑树这种数据结构，当碰撞结点较少时，采用链表存储，当较大时（>TREEIFY_THRESHOLD=8个），采用红黑树存储这样碰撞后的查询由链表变为了红黑树，即时间复杂度有O(n)变为了O(logn)
