虽然在工作中经常用到HashMap,LinkedList之类的集合,但是对其真正的实现原理等都没有做过多的深入追究.所以趁这段时间有空就进行了深入的学习和记录.
- HashMap的特点是什么?
- HashMap的实现原理
- Equals()和hashCode()的都有什么作用？
- HashMap中的Hash如何设计
HashMap是什么？
HashMap是一个哈希的Map,有一个Entry数组,和若干链表(JDK 8后还包括红黑树)组成
HashMap的大概原理
HashMap中的Entry是一个桶,首先在我们进行Put操作的时候,根据对象的hashcode,计算出在桶中的位置，然后再判断此处是否已经存储了一个Node，没有就创建并且把键值对放进去，有就根据查找到对应的修改值。
HashMap的Put和Get原理
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;
//判断HashMap中的桶是否被初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//根据上面传来的Hash计算桶中的下标，为空就创建新的Node
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//判断对应的Node中的Hash与key是否跟出来的一致（此处等于用了HashCode和判断引用和equals）
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//判断为红黑树Node
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//链表Node
else {
for (int binCount = 0; ; ++binCount) {
//遍历到此Node的最后一个，插入
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//链表大于一定数量后转为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//遍历中找到对应的Node，
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;
//LinkedHashMap用的回调
afterNodeAccess(e);
return oldValue;
}
}
//Fail-Fast 机制
++modCount;
//扩容判断
if (++size > threshold)
resize();
//LinkedHashMap用的回调
afterNodeInsertion(evict);
return null;
}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) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((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的逻辑比较简单就是直接根据hash的下标，然后比对key的hash和key来获取值
Equals()和hashCode()
这中间还有几个概念为Hashcode，Equals，==。这都有些区别
==
==是二元操作符，其对比基于两个的对象的内存引用，如果一致就返回True
Equals()
equals()是object中的方法，在源码中表示类似这样
public boolean equals(Object obj) {
return (this == obj);
}大概的一看好像equals与==是一样的，只是equals对==操作符进行了一个包裹，但是equals是可以被重写的，所以equals的比对逻辑又是可以根据具体情况来的。
比如下面代码
public class Test {
public static class Test1{
@Override
public boolean equals(Object obj) {
return true;
}
}
public static void main(String[] args) {
Test1 t1 = new Test1();
Test1 t2 = new Test1();
System.out.println(String.format("t1==t2:%s", t1==t2));
System.out.println(String.format("t1.equals(t2):%s", t1.equals(t2)));
}
}
t1==t2:false
t1.equals(t2):trueHashcode
由本地方法返回一个散列值。
HashMap的Hash及冲突
在使用hashMap中不管是增加删除查询，最后都是要定位元素在桶中的位置。所以在桶中摆放元素的时候肯定是希望位置要分布的均匀，而不是挤在一块或者是重复再同个位置。 在HashMap中的实现是
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}如果key是null，那么就hash是0，这也就是为什么HashMap可以支持key为Null，而且只有一个可以key为null。如果不是那么先取key的hashcode然后和他自己的hashcode的无符号右移16位后结果，进行异或。
假设key的hashcode:
hashcode 1111 1111 1111 1111 0000 0101 0010 1110
h>>>16 0000 0000 0000 0000 1111 1111 1111 1111
hashcode^(h>>>16) 1111 1111 1111 1111 1111 1010 1101 0001
为什么要增加一个这样的操作呢?看一下下面的方法就知道了。
//JDK 1.8中没有了
static int indexFor(int h, int length) {
return h & (length-1);
}这段代码就是在计算元素对应在buket中的位置了。
那么我们希望分布的比较均匀的话，可以使用取模，但是取模又是比较消耗的行为，所以在这边又进行了优化。
因为bucket桶的长度一直是2的n次方，所以h&(length-1)就等价于h%length了，但是又减少了消耗。
但是这边还是没有看出来为什么上面要先对hashcode的进行计算再来取模。
事实上假设如果在bucket的桶的长度比较小的时候，直接对key的hashcode进行&运算时候事实上会只有低位的bit进行了参与运算，那么高位就空出来不进行运算了，增加了hash碰撞的机会，所以先位移16位，那么就是刚刚好32字节对半分开，然后异或后就高位低位一起参与了下标计算。
HashMap中Bucket的实现
HashMap中的Bucket被命名为table，桶中的元素就是一个Node实现了Map.Entry接口。在元素的hash计算出下标重复后用链表来连接，然后在链表过长后变成了红黑树。在添加数据过多后进行扩容。每次扩容也是2的n次方.
HashMap中Bucket的扩容思路
当在HashMap中不停的添加元素的时候，在HashMap的桶无法装载更多元素的时候，需要扩大数组的长度，以便能装入更多的元素。
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) {
//如果已经到了最大的就不resize了
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
}
//实例化使用传来的
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;
//遍历老的中的所有元素然后重新计算下标放到新的桶中
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;
}