参考文章 https://zhuanlan.zhihu.com/p/31805309
1, 在介绍 hashmap 之前首先简单来了解一下什么是二叉查找树和红黑树
1.1 二叉查找树
它具备两个特性:
1, 左子树上所有结点的值小于等于它的根结点的值
2, 右子树上所有结点的值大于等于它的根结点的值
如下图
二叉查找树的优势就是便于查找, 比如说找到 1 这个值, 查找次数最多等于这棵树的高度. 然而它的缺陷在于多次插入新结点会导致这棵树的不平衡, 比如下面这棵树
所以红黑树应运而生, 红黑树在二叉树的基础上又增加了如下的规则:
1, 节点是红色或黑色
2, 根节点是黑色
3, 每个叶子节点都是黑色的空节点 (NIL 节点)
4, 每个红色节点的两个子节点都是黑色, 而且每个叶子到根的所有路径上不能有连续的两个红色节点
5, 从任一节点到其每个叶子的所有路径都包含着相同数量的黑色节点
下面就是一颗典型的红黑树
当插入或删除节点的时候, 红黑树的规则有可能会被打破. 这时候就需要做出一些调整来继续维持我们的规则, 调整方法有两种: 变色和旋转, 而旋转又分为左旋转和右旋转, 具体看参考文章, 只要了解红黑树的自平衡思想就可以了.
好了接下来进入正题来看看我们的 hashmap 源码吧, 源码中介绍 hashmap 的 key 和 value 都允许为空, 但是他不能保证顺序随时间不变, hashmap 中有三个重要的参数
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认初始化容量为 16
static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默认负载因子 0.75
transient Node<K,V>[] table; // 声明一个 node 类型的数组, hashmap 中实际操作的数组
Node 为静态内部类
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next; // 用来标记下一个节点的对象
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
首先来看看 put 方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
hash(key) 方法将 key 进行 hashcode 运算返回一个 hash 值
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
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) n = (tab = resize()).length;
// 当第一次添加元素是满足 table 为 null, 此时触发 resize() 方法; 此时 resize() 方法返回默认容量 16
if ((p = tab[i = (n - 1) & hash]) == null)
//i=(n-1) & hash 计算出来的值 i 一定在 1-n 之间用, 这个值去做下标计算出来的值如果为 null, 则新建一个 node 赋值给这个位置, 那么如果 i 值重复, 即发生数组下标的元素重复怎么办呢? 代码在下面
tab[i] = newNode(hash, key, value, null);
else {
Node < K,
V > e;
K k;
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p;
else if (p instanceof TreeNode) e = ((TreeNode < K, V > ) p).putTreeVal(this, tab, hash, key, value);
else {
// 这里就是解决 hash 冲突的地方
for (int binCount = 0;; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null); // 新建一个 node 对象赋值给上一个对象的 next 引用, 即以单向链表的方式存储 Node.
if (binCount >= TREEIFY_THRESHOLD - 1)
// 当 bincount 大于等于 7 时链表转化为红黑树, jdk1.7 是没有红黑树的, jdk1.8 中加入红黑树是为了防止哈希表碰撞 (任何哈希表的长度都是有限的, 所以不同的数据项具有相同哈希值, 此时不同数据项被定为到同一个桶, 称为碰撞), 当链表长度为 8 时, 转化为红黑树能提高 map 的效率
break;
}
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break;
p = e;
}
}
if (e != null) { // existing mapping for key 当 Key 值重复时将新的 value 值替换
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 方法
1, 首先根据 key 的值算出 hash 值, 然后根据 hash 值得出这个 key 在 table 数组中的位置上的对象 p
2, 如果这个对象为 null, 则直接赋值
3, 如果不为 null 有三种情况,
3.1 这个对象 p 的 hash 和 key 是否与所给的相等如果相等赋值为一个 node 对象 e
3.2 如果这个对象 p 是 TreeNode 红黑树类型, 则循环树中的节点, 判断 p 的 key 是否 == 或 equals 节点的 key, 成立则替换树里的 value 并返回旧值, 不成立就添加到树中.
3.3 否则就遍历单向链表, 如果这个链表中的 key== 或 equals 对象 p 的 key 则替换, 否则添加到链表中
4, 判断是否需要替换 vlaue 值只需要判断 hash 值是否相等, Key 值是否 == 或者 equals
来源: http://blog.csdn.net/qq_33661044/article/details/79213620