导读：数据结构哈希表也称散列表，是一种键(key) 值(value)映射关系的数据结构。这种结构在java中是通过HashMap类实现的。接下来我们一起来学习这个类。
1.类核心成员
HashMap类底层原理是维护数组、单向链表、红黑树实现哈希表，该中核心成员分别是：
1.table是Node类型的数组
2.Node是单向链表
3.TreeNode是红黑树
package java.util;
public class HashMap extends AbstractMap
implements Map, Cloneable, Serializable {
transient Node[] table;//table是Node类型的数据
static class Node implements Map.Entry{} //单向链表
static final class TreeNode extends LinkedHashMap.Entry{} //红黑树
}
2.哈希表本质
在java8中,哈希表是HashMap类型的实例，这个实例本质是一个数组，数组元素是Node类型，或者是红黑树TreeNode。其中TreeNode是Node的派生类。在向这个数组添加数据的时候，Node与TreeNode会相互转换，从而降低时间复杂度。
//TreeNode继承LinkedHashMap类中内部类Entry
static final class TreeNode extends LinkedHashMap.Entry{}
//Entry继承HashMap类中内部类Node
static class Entry extends HashMap.Node{}
3.哈希表的键(key)-值(value)映射关系的实现
数组数据结构是下标是int类型，从下标0开始。那么键(key)是如何实现映射关系的呢？
在putVal()方法中有这么一句代码 tab[i = (n - 1) & hash]。i是数组tab的下标，tab下标值范围0~(n-1)。hash是key通过哈希函数生成的值，同一个key生成的hash值是一样的，(n-1)&hash运算的结果在 0~(n-1)范围，也就是数组tab下标范围，从而实现了key值对数组下标的对应。同学们一定发现了不同的key值hash后有可能结果相同，比如“Aa”和“BB”的hash值相同，会导致数组下标碰撞，那么这个类是如何处理，保存数据呢?
static class Node implements Map.Entry{
final int hash;//保存key的hash值
final K key;//保存key值
V value;//保存value值
Node next; //保存下一个Node元素的值
}
4.哈希表保存值的流程
1.判断数组下标是否有值，这个下标为空则写入这个Node
2.如果数组下标有值，则处理下标碰撞
2.1 如果坑位元素p的哈希值与新元素的哈希值相同,并且元素p的key值与新元素key相同 或者 key不为null并且key.equals(k)，则为视为同一个key值，不做处理;
2.2 如果坑位元素p是TreeNode，则写入TreeNode;
2.3 不是TreeNode就是Node类型，则加入链表Node尾部。
以上就是HashMap保存元素以及处理下标碰撞的流程。
//返回V值
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
//如果tab为null或者长度为0
if ((tab = table) == null || (n = tab.length) == 0)
//n的值是数组的长度
n = (tab = resize()).length;
//key值hash后与数组长度减1位，位运算后获取数组下标，并判断改下标数组元素是否为空
if ((p = tab[i = (n - 1) & hash]) == null)
//这个下标元素为空则赋值
tab[i] = newNode(hash, key, value, null);
else {//发生处理下标碰撞
//声明一个Node类型局部变量e,K类型(与实参类型一致的类型)的k
Node e; K k;
//p为已经存在的旧元素
//如果坑位元素p的哈希值与新元素的哈希值相同,
if (p.hash == hash &&
//并且坑位元素p的key值与新元素key相同 或者 key不为null并且key.equals(k)
//则为视为一个元素,不做任何处理(即去重)
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果坑位元素p是红黑树TreeNode类型，则写入这个红黑树
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
//不是红黑树TreeNode，只能是Node单向链表
else {
//无限循环
for (int binCount = 0; ; ++binCount) {
//e值为链表的下一个
if ((e = p.next) == null) {
//链表尾处追加
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
//退出循环
break;
}
//并且坑位元素p的key值与新元素key相同 或者 key不为null并且key.equals(k)
//则为视为一个元素,不做任何处理(即去重)
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//p的值也为链表的最后一个
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;
}
文章来源: blog.csdn.net，作者：码者，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/win_von/article/details/112162164