ThreadLocalMap 的源码看起来会考虑一种哈希冲突的情况,但不是 ThreadLocal 本身实现了完美散列吗?

2020-04-18 11:03:32 +08:00
 amiwrong123

看 ThreadLocal 的源码,它利用魔数0x61c88647在 2 的幂为容量的哈希表上,能够完美散列,没有一个元素会哈希冲突。

    private final int threadLocalHashCode = nextHashCode();

    private static AtomicInteger nextHashCode =
        new AtomicInteger();

    private static final int HASH_INCREMENT = 0x61c88647;

    private static int nextHashCode() {
        return nextHashCode.getAndAdd(HASH_INCREMENT);
    }

而且构造每个 ThreadLocal 时,使用了 AtomicInteger 来得到自己的哈希值,那么就算两个线程同时构造 ThreadLocal,两个 ThreadLocal 对象的哈希值也是不同的(这么理解,对吧?)。

综上,两个 ThreadLocal 对象在 ThreadLocalMap 不可能哈希冲突。

而你看下面这段源码,看起来会考虑一种哈希冲突的情况,但不是 ThreadLocal 本身实现了完美散列吗?:

        private Entry getEntry(ThreadLocal<?> key) {
            int i = key.threadLocalHashCode & (table.length - 1);
            Entry e = table[i];  //根据下标获得的 entry 可能为 null
            //只有当 entry 非 null,且 key 为同一个对象时,才直接返回 value
            if (e != null && e.get() == key)
                return e;
            //否则 getEntryAfterMiss
            else
                return getEntryAfterMiss(key, i, e);
        }

        /**
         * Version of getEntry method for use when key is not found in
         * its direct hash slot.
         *
         * @param  key the thread local object
         * @param  i the table index for key's hash code
         * @param  e the entry at table[i]
         * @return 
         */
        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)//寻址的过程中,不巧发现了包含 null key 的 entry
                    expungeStaleEntry(i);
                else//利用 nextIndex,寻址到冲突后的实际位置
                    i = nextIndex(i, len);
                e = tab[i];
            }
            return null;
        }

或者说,我认为 getEntryAfterMiss 里面的return e;不可能被调用到,因为这种情况发生,就说明两个 ThreadLocal 对象的哈希值一样了,产生了哈希冲突。

3292 次点击
所在节点    Java
27 条回复
brucefu
2020-04-18 13:51:10 +08:00
看来还是懒了,debug 就能解决了,哈
daozhihun
2020-04-18 13:56:37 +08:00
@Aresxue 是的,你这个说法没错,只是经过很多实验得到的一个相对均匀的分布方法
brucefu
2020-04-18 14:14:09 +08:00
感觉在问 XX 不是永动机吗?
amiwrong123
2020-04-19 11:27:42 +08:00
@Aresxue
@daozhihun
@lance6716
各位大佬,可否再帮忙解答一个问题。
就是使用这个魔数只是为了哈希相对均匀的分布,那么如果不使用这个魔数,直接让静态变量 HASH_INCREMENT 为 1,会有什么坏处吗?(是不是因为 ThreadLocalMap 用的开发寻址,所以如果哈希均匀分布,那么冲突的时候,就能大概率更快的找到冲突后的新位置吗)
daozhihun
2020-04-19 12:32:21 +08:00
lance6716
2020-04-19 13:07:03 +08:00
@amiwrong123 等于 1 的话,哈希结果均匀要依赖输入均匀。现在对输入的依靠更弱
zzkde
2020-04-30 10:27:59 +08:00
@amiwrong123 就算能扩容也要考虑删除情况啊,比如 len 为 16 时:
0 7 14 5 12 3 10 1 8 15 6 13 4 11 2 9 0,可以看到第 17 个 hash 值会冲突
如果单纯添加元素不删除的话到第 17 个元素也不会产生冲突,因为会扩容。
但如果考虑另外一种情况就是我先添加第一个,然后后面边添加边删除,到第 17 个就会产生冲突,但此时 size 为 2,不会扩容。

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/663692

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX