【并发】ThreadLocalMap 解决 Hash 冲突的实现方式

ThreadLocalMap 解决哈希冲突的主要方式是使用线性探测法（linear probing）。这种方法通过线性探测来寻找空槽位，以应对哈希冲突。以下是详细的解决方案：

1. 线性探测法

线性探测法在发生哈希冲突时，通过检查数组中的下一个位置来找到空的槽位。如果当前槽位已被占用，它将继续检查下一个槽位，直到找到空槽位或合适的槽位为止。

2. ThreadLocalMap 实现中的哈希冲突解决

ThreadLocalMap 通过以下方法来处理哈希冲突：

1. 计算索引：

   • 使用 ThreadLocal 的哈希码来计算在 Entry 数组中的索引。
   • 该索引由 ThreadLocal 实例的 threadLocalHashCode 和数组长度（减去 1）按位与运算得到。

2. 线性探测：

   • 如果计算出的索引位置已经被占用（即已有 Entry 对象），ThreadLocalMap 会通过线性探测法检查数组中的下一个位置，直到找到一个空槽位或适合的槽位。
   • 使用 nextIndex 方法来实现线性探测，它将当前位置增加 1，循环回到数组的开头。

3. 处理过时条目：

   • 如果在探测过程中遇到 Entry 的键为 null（即过时的条目），ThreadLocalMap 会调用 expungeStaleEntry 方法来清理这些过时条目，并将当前条目插入到合适的位置。

关键代码解析

以下是 ThreadLocalMap 中处理哈希冲突的相关代码：

static class ThreadLocalMap {// 存储条目的数组private Entry[] table;// 存储条目的数量private int size = 0;// 定义初始容量private static final int INITIAL_CAPACITY = 16;// 构造函数ThreadLocalMap(ThreadLocal<?> firstKey, Object firstValue) {table = new Entry[INITIAL_CAPACITY];int i = firstKey.threadLocalHashCode & (INITIAL_CAPACITY - 1);table[i] = new Entry(firstKey, firstValue);size = 1;}// 线性探测法获取 Entryprivate Entry getEntry(ThreadLocal<?> key) {int i = key.threadLocalHashCode & (table.length - 1);Entry e = table[i];if (e != null && e.get() == key)return e;elsereturn getEntryAfterMiss(key, i, e);}// 线性探测法后处理private Entry getEntryAfterMiss(ThreadLocal<?> key, int i, Entry e) {Entry[] tab = table;int len = tab.length;while (e != null) {ThreadLocal<?> k = e.get();if (k == key)return e;if (k == null)expungeStaleEntry(i);elsei = nextIndex(i, len);e = tab[i];}return null;}// 设置值private void set(ThreadLocal<?> key, Object value) {Entry[] tab = table;int len = tab.length;int i = key.threadLocalHashCode & (len - 1);for (Entry e = tab[i]; e != null; e = tab[i = nextIndex(i, len)]) {ThreadLocal<?> k = e.get();if (k == key) {e.value = value;return;}if (k == null) {replaceStaleEntry(key, value, i);return;}}tab[i] = new Entry(key, value);int sz = ++size;if (!cleanSomeSlots(i, sz) && sz >= threshold)rehash();}// 获取下一个索引private int nextIndex(int i, int len) {return ((i + 1 < len) ? i + 1 : 0);}// 替换过时条目private void replaceStaleEntry(ThreadLocal<?> key, Object value, int staleSlot) {Entry[] tab = table;int len = tab.length;Entry e;int slotToExpunge = staleSlot;for (int i = prevIndex(staleSlot, len);(e = tab[i]) != null;i = prevIndex(i, len)) {if (e.get() == null)slotToExpunge = i;}for (int i = nextIndex(staleSlot, len);(e = tab[i]) != null;i = nextIndex(i, len)) {ThreadLocal<?> k = e.get();if (k == key) {e.value = value;tab[i] = tab[staleSlot];tab[staleSlot] = e;if (slotToExpunge == staleSlot)slotToExpunge = i;cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);return;}if (k == null && slotToExpunge == staleSlot)slotToExpunge = i;}tab[staleSlot].value = null;tab[staleSlot] = new Entry(key, value);if (slotToExpunge != staleSlot)cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);}// 处理过时条目private int expungeStaleEntry(int staleSlot) {Entry[] tab = table;int len = tab.length;tab[staleSlot].value = null;tab[staleSlot] = null;size--;Entry e;int i;for (i = nextIndex(staleSlot, len);(e = tab[i]) != null;i = nextIndex(i, len)) {if (e.get() == null) {e.value = null;tab[i] = null;size--;} else {int h = e.get().threadLocalHashCode & (len - 1);if (h != i) {tab[i] = null;while (tab[h] != null)h = nextIndex(h, len);tab[h] = e;}}}return i;}// 清理某些槽位private boolean cleanSomeSlots(int i, int n) {boolean removed = false;Entry[] tab = table;int len = tab.length;do {i = nextIndex(i, len);Entry e = tab[i];if (e != null && e.get() == null) {n = len;removed = true;i = expungeStaleEntry(i);}} while ((n >>>= 1) != 0);return removed;}// 重新哈希private void rehash() {expungeStaleEntries();if (size >= threshold - threshold / 4)resize();}private void expungeStaleEntries() {Entry[] tab = table;int len = tab.length;for (int j = 0; j < len; j++) {Entry e = tab[j];if (e != null && e.get() == null)expungeStaleEntry(j);}}private void resize() {Entry[] oldTab = table;int oldLen = oldTab.length;int newLen = oldLen * 2;Entry[] newTab = new Entry[newLen];int count = 0;for (int j = 0; j < oldLen; ++j) {Entry e = oldTab[j];if (e != null) {ThreadLocal<?> k = e.get();if (k == null) {e.value = null;} else {int h = k.threadLocalHashCode & (newLen - 1);while (newTab[h] != null)h = nextIndex(h, newLen);newTab[h] = e;count++;}}}setThreshold(newLen);size = count;table = newTab;}
}

重要细节

1. 计算索引：

   • i = key.threadLocalHashCode & (len - 1); 使用 ThreadLocal 的哈希码和表长度减去 1 的按位与运算来计算索引。

2. 线性探测：

   • nextIndex(i, len) 方法计算下一个索引位置，用于探测冲突。
   • 如果发生冲突，会在 table 数组中继续查找，直到找到空槽位。

3. 清理和重哈希：

   • 使用 expungeStaleEntry 方法清理过时的条目。
   • resize() 方法扩展数组并重新分配条目，以减少冲突并提高性能。

总结

ThreadLocalMap 使用线性探测法解决hash冲突