Java中ThreadLocalMap解決Hash沖突的實現(xiàn)方式

更新時間：2025年04月24日 09:48:41 作者：灰_灰丶灰

本文主要介紹了Java中ThreadLocalMap解決Hash沖突的實現(xiàn)方式,主要方式是使用線性探測法,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧

1. 線性探測法

線性探測法在發(fā)生哈希沖突時，通過檢查數(shù)組中的下一個位置來找到空的槽位。如果當前槽位已被占用，它將繼續(xù)檢查下一個槽位，直到找到空槽位或合適的槽位為止。

2. ThreadLocalMap 實現(xiàn)中的哈希沖突解決

ThreadLocalMap 通過以下方法來處理哈希沖突：

計算索引：
- 使用 ThreadLocal 的哈希碼來計算在 Entry 數(shù)組中的索引。
- 該索引由 ThreadLocal 實例的 threadLocalHashCode 和數(shù)組長度（減去 1）按位與運算得到。
線性探測：
- 如果計算出的索引位置已經(jīng)被占用（即已有 Entry 對象），ThreadLocalMap 會通過線性探測法檢查數(shù)組中的下一個位置，直到找到一個空槽位或適合的槽位。
- 使用 nextIndex 方法來實現(xiàn)線性探測，它將當前位置增加 1，循環(huán)回到數(shù)組的開頭。
處理過時條目：
- 如果在探測過程中遇到 Entry 的鍵為 null（即過時的條目），ThreadLocalMap 會調用 expungeStaleEntry 方法來清理這些過時條目，并將當前條目插入到合適的位置。

關鍵代碼解析

以下是 ThreadLocalMap 中處理哈希沖突的相關代碼：

static class ThreadLocalMap {

    // 存儲條目的數(shù)組
    private Entry[] table;
    
    // 存儲條目的數(shù)量
    private int size = 0;
    
    // 定義初始容量
    private static final int INITIAL_CAPACITY = 16;

    // 構造函數(shù)
    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;
    }

    // 線性探測法獲取 Entry
    private Entry getEntry(ThreadLocal<?> key) {
        int i = key.threadLocalHashCode & (table.length - 1);
        Entry e = table[i];
        if (e != null && e.get() == key)
            return e;
        else
            return 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);
            else
                i = 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;
    }
}

重要細節(jié)

計算索引：
- i = key.threadLocalHashCode & (len - 1); 使用 ThreadLocal 的哈希碼和表長度減去 1 的按位與運算來計算索引。
線性探測：
- nextIndex(i, len) 方法計算下一個索引位置，用于探測沖突。
- 如果發(fā)生沖突，會在 table 數(shù)組中繼續(xù)查找，直到找到空槽位。
清理和重哈希：
- 使用 expungeStaleEntry 方法清理過時的條目。
- resize() 方法擴展數(shù)組并重新分配條目，以減少沖突并提高性能。