文章目录
目录
文章目录
前言
1 . 成员变量
灵魂五问
第一问: 默认初始化容量为啥是16?
第二问: 最大容量为什么必须是2的幂?
第三问: 链表转红黑树的阈值为什么是8?
第四问: 红黑树转链表的阈值为什么是6?
第五问: 默认加载因子为什么是0.75?
2. 成员方法
equals && hash
构造方法
get
put
resize
总结
前言
并不是阅读全部源码哈, 了解关键的源码就可以了, 读多了头疼
1 . 成员变量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 默认初始化容量16
static final int MAXIMUM_CAPACITY = 1 << 30; 最大容量。必须是2的幂<= 1<<30
static final float DEFAULT_LOAD_FACTOR = 0.75f; 在构造函数中未指定时使用的负载因子。
static final int TREEIFY_THRESHOLD = 8; 链表转红黑树的阈值
static final int UNTREEIFY_THRESHOLD = 6; 红黑树转链表的阈值
static final int MIN_TREEIFY_CAPACITY = 64; 可以对哈希桶进行树化的最小表容量
int threshold; 扩容阈值 threshold = capacity*loadfactor
transient Node<K,V>[] table; 哈希表
final float loadFactor; 哈希表的负载因子这里直接就上强度了, 来个灵魂五问,哈哈
灵魂五问
第一问: 默认初始化容量为啥是16?
谈到这个那就得引出HashMap的索引计算公式了 index = (length-1) & hash (插入元素key对应的hash值)
举个例子
假设有一个 Key 的 HashCode 值为 12345。我们需要计算它在数组中的 index。 首先，计算 length-1 的结果：10-1=9。 然后，将 12345 与 9 进行按位与运算：12345 & 9。 将 12345 转换为二进制，为 11000000111001。将 9 转换为二进制，为 0000000000001001。 按位与运算的结果为：0000000000000001。 最后，将二进制数转换为十进制，结果为 1。 所以，该 Key 在数组中的 index 为 1 将length改为16我们来再算一遍 假设数组的 length 为 16。 首先，计算 length-1 的结果：16-1=15。 然后，将 12345 与 15 进行按位与运算：12345 & 15。 将 12345 转换为二进制，为 11000000111001。将 15 转换为二进制，为 0000000000001111。 按位与运算的结果为：0000000000000001。 最后，将二进制数转换为十进制，结果为 1。 所以，该 Key 在数组中的 index 为 1。
说明了什么呢? Hash 算法最终得到的 index 结果，完全取决于 Key 的 HashCode 值的最后几位。既然和数组容量无关,那当然是大一点好了, 可以减少哈希碰撞的几率!
第二问: 最大容量为什么必须是2的幂?
因为 n 永远是2的次幂，所以 n-1 通过 二进制表示，永远都是尾端以连续1的形式表式，当(n - 1) 和 hash 做与运算时，会保留hash中 后 x 位的 1，这样碰撞的几率小。
另外，使用2的幂作为数组长度还有一个好处是，可以通过位运算来对索引进行优化，提高访问速度。例如，当数组长度为16时，可以通过hashCode的高4位来计算索引，即 hashCode >>> 28。这样可以保证不同的哈希值分布到数组的不同位置，减少了哈希冲突的概率。
第三问: 链表转红黑树的阈值为什么是8?
链表转红黑树的阈值为8是为了在保持树的平衡和性能之间取得一个合适的平衡。
当链表长度小于等于8时，红黑树的插入和删除操作相对链表操作来说，并没有明显的优势，反而可能会增加额外的开销。此时，继续使用链表结构即可。
而当链表长度超过8时，红黑树的平衡性能就会比链表好很多。红黑树的平均时间复杂度为O(log n)，而链表的平均时间复杂度为O(n)。因此，将链表转换为红黑树可以提高搜索、插入和删除等操作的效率。
因此，8被选择作为链表转红黑树的阈值，是为了平衡树的性能和开销之间的权衡。当链表长度超过8时，转换为红黑树可以提高性能；而当链表长度小于等于8时，继续使用链表可以减少额外的开销。
第四问: 红黑树转链表的阈值为什么是6?
经过实验和研究，发现当红黑树中节点数小于等于6时，进行红黑树转链表操作的开销较小,同时也避免了红黑树和链表发生频繁转换而造成的开销。
第五问: 默认加载因子为什么是0.75?
当加载因子为0.75时，哈希表的填充比例达到75%时就会触发扩容操作，即将哈希表的容量扩大一倍。这样可以减少碰撞的可能性，同时保持较小的空间开销和较高的查询效率。
如果加载因子过低，例如0.5，虽然可以减少碰撞的概率，但会造成较大的空间浪费；如果加载因子过高，例如1.0，虽然可以节省空间，但会导致碰撞概率大大增加，从而影响查询性能。
因此，经过实践和测试，0.75被认为是一个较为合适的默认加载因子。
总结: 太小导致空间浪费,太大导致碰撞的概率增加,权衡之下,0.75最合适
2. 成员方法
equals && hash
equals方法
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; 节点的哈希值，用于快速定位节点在哈希表中的位置。
final K key; 节点的键值。
V value; 节点的值。
Node<K,V> next; 指向下一个节点的引用。
重写的equals方法
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}重写的hashcode方法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}重写equals方法是为了比较插入元素的key是否相等,但是为什么hashcode方法也被重写了?
当我们重写
equals方法时，意味着我们定义了对象相等的逻辑，即当两个对象根据我们定义的相等逻辑判断为相等时，equals方法应该返回true。而在HashMap等数据结构中，如果两个对象根据equals方法判断为相等，那么它们的hashCode值应该相等，以保证它们能够被放入相同的哈希桶中。因此，为了保证对象相等的逻辑与哈希码的一致性，确实应该在重写
equals方法的同时，也要重写hashCode方法。通常来说，如果两个对象根据equals方法判断为相等，那么它们的hashCode方法应该返回相同的哈希码。这样可以确保相同的对象在哈希表中返回相同的哈希值，从而提高哈希表的性能和正确性。在默认情况下，
hashCode()方法会返回对象的内存地址经过哈希算法计算得出的哈希值。但是，通常情况下，我们会在自定义类中重写hashCode()方法，以便根据对象的属性来计算哈希值。
(h = key.hashCode()) ^ (h >>> 16)
为了减少哈希碰撞（不同对象具有相同哈希值）的概率，通常会对hashCode进行一些位操作，以增加哈希值的随机性。在这段代码中，通过将hashCode的高16位与低16位进行异或操作，可以更好地分散哈希值，减少碰撞的可能性。 java中的hashCode()方法返回的是一个32位的整数，通常会将对象的内部信息转换为一个整数作为哈希码。将hashCode的高16位和低16位进行异或操作，可以将对象的不同部分的信息混合在一起，增加哈希值的随机性。
构造方法
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0) 初始化容量为零 抛异常
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY) 如果大于最大容量大小 令其为最大容量
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor)) 如果负载因子小于零或者非数字 抛异常
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}get
在jdk1.8时候HashMap的底层结构由数组+链表 -> 数组加链表加红黑树
jdk1.8之后源码
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) { 1. 通过 (n-1)&hash 计算出索引位置
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k)))) 2. 先通过hash值比较该索引位置的元素是否是要找的元素,如果哈希值相同则通过equals方法看看key是否相同(相同直接返回结果,找到了),如果不相同那么就需要查找挂在这个节点下面的链表或者红黑树
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode) 3 . 判断是否为红黑树 如果是的话就按照红黑树的逻辑来搜索节点(不展开)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash && 4 . 反之则是链表 按照链表的方式递归遍历
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}put
在jdk1.7及之前链表采用头插的方式来插入节点,在jdk1.8及之后采用尾插的方式来插入节点
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; 1 . 如果哈希表为空 触发扩容
if ((p = tab[i = (n - 1) & hash]) == null) 2 . 如果数组位置为空,直接插入即可
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)))) 3. 如果要插入元素的hash值和当前数组位置的hash值相同,并且通过equals方法比较key也相同,默认新的value直接覆盖老的value
e = p;
else if (p instanceof TreeNode) 4 . 向下遍历, 如果是红黑树, 调用红黑树添加节点的方法(不展开)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) { 5. 反之则为链表,按照尾插的方式来添加节点
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) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold) 6 . 添加完元素之后 令有效元素个数加一 如果有效元素个数大于 threshold 进行扩容
resize();
afterNodeInsertion(evict);
return null;
}
为什么jdk1.7 -> jdk1.8 链表插入元素的方式由头插改为了尾插?
resize
HashMap的扩容机制是为了保持哈希表的负载因子在一个合适的范围内，从而保证查询、插入和删除操作的性能。当HashMap中的元素数量超过了阈值（负载因子 * 当前容量）时，就会触发扩容操作。具体的扩容机制如下：
- 创建一个新的哈希表数组，其大小是原数组的两倍。
- 将原哈希表数组中的所有元素重新计算哈希值，并放入新的哈希表数组中的对应位置。
- 扩容完成后，原哈希表数组会被丢弃，所有的引用会指向新的哈希表数组。
- 扩容过程中，所有的插入、删除、查找操作都可以正常进行，因为HashMap在扩容时会保证线程安全。
在扩容过程中，由于需要重新计算哈希值并重新插入元素，可能会导致性能损耗。因此，为了避免频繁扩容，可以通过调整初始容量和负载因子来优化HashMap的性能。
差不多了,后续如果还有注意点的话,再来补充。
总结
以上就是这篇博客的主要内容了,大家多多理解,下一篇博客见!
