V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
amiwrong123
V2EX  ›  Java

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

  •  
  •   amiwrong123 · 2020-04-18 11:03:32 +08:00 · 3504 次点击
    这是一个创建于 1690 天前的主题,其中的信息可能已经有所发展或是发生改变。

    看 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 对象的哈希值一样了,产生了哈希冲突。

    27 条回复    2020-04-30 10:27:59 +08:00
    lyjr
        1
    lyjr  
       2020-04-18 11:12:55 +08:00
    哈希值不同,但是运算得到的地址是可能相同的,就是这句喽,int i = key.threadLocalHashCode & (table.length - 1);
    i 肯定可能冲突嘛。
    高层面上想一想也不可能嘛,世界上哪有不冲突的哈希表,一个无限的集合映射到一个有限的集合,能不冲突吗
    amiwrong123
        2
    amiwrong123  
    OP
       2020-04-18 11:16:14 +08:00
    @lyjr
    但是见此博客 https://www.cnblogs.com/dennyzhangdd/p/7978455.html 中的 MagicHashCode 测试类,利用魔数后,就算是取模后的 i,在有限的 2 的幂的哈希表,也没有一个 i 冲突啊。
    wysnylc
        3
    wysnylc  
       2020-04-18 11:17:25 +08:00
    有答案了 @我下蟹蟹
    lyjr
        4
    lyjr  
       2020-04-18 11:24:04 +08:00
    @amiwrong123 举个最简单的例子,长度为 2^3=8 的哈希表,插入 9 个元素,如果不冲突的话,最后一个元素放在哪里?
    根本不用想太多,跟任何数据结构和算法都无关,本质上是一个集合映射的数学问题,9 个元素的集合不肯能无冲突的映射到大小为 8 的集合。
    coer
        5
    coer  
       2020-04-18 11:24:04 +08:00 via iPad
    这个魔数可以完美散列,学到了
    amiwrong123
        6
    amiwrong123  
    OP
       2020-04-18 11:27:12 +08:00
    @lyjr
    但是,ThreadLocalMap 里面的 key,如果个数大于了阈值,就会在 rehash 啊,然后容量变成下一个 2 的幂。也就不会出现你说的这种情况了啊
    coer
        7
    coer  
       2020-04-18 11:34:07 +08:00 via iPad
    cheng6563
        8
    cheng6563  
       2020-04-18 11:39:46 +08:00 via Android
    散列都是有可能冲突的,不管多少位。
    wysnylc
        9
    wysnylc  
       2020-04-18 11:41:17 +08:00
    斐波那契数列,0x61c88647 对应 10 进制是 1640531527
    CoderGeek
        10
    CoderGeek  
       2020-04-18 11:47:16 +08:00
    有限集映射无限 你告诉我没冲突 你的数据结构老师要打人了 离散的老师也要气疯了
    lance6716
        11
    lance6716  
       2020-04-18 11:57:30 +08:00
    @amiwrong123 啥玩意,0x61c88647 咋就成了完美散列了。csdn 现在越来越能扯了
    daozhihun
        12
    daozhihun  
       2020-04-18 12:02:18 +08:00
    魔数只是让哈希相对均匀的分布,怎么可能完全没有冲突。
    amiwrong123
        13
    amiwrong123  
    OP
       2020-04-18 12:05:38 +08:00
    好吧,我错了。我好像想通了。
    ```java
    import java.util.HashSet;
    import java.util.Set;

    public class MagicHashCode {
    private static final int HASH_INCREMENT = 0x61c88647;

    public static void main(String[] args) {
    hashCode1();
    }


    private static void hashCode1(){
    Integer length = 32;
    int hashCode = 0;
    for(int i=0;i<length;i++){
    hashCode = i*HASH_INCREMENT;//每次递增 HASH_INCREMENT
    System.out.print((hashCode & (16-1)) + " ");//求散列下标,算法公式
    }
    }

    }
    ```
    打印结果:0 7 14 5 12 3 10 1 8 15 6 13 4 11 2 9 0 7 14 5 12 3 10 1 8 15 6 13 4 11 2 9
    结论:先创建 32 个 ThreadLocal,然后给线程 A 先设置第 1 个 ThreadLocal,再设置第 17 个 ThreadLocal,然后就冲突了
    lance6716
        14
    lance6716  
       2020-04-18 12:06:15 +08:00   ❤️ 1
    @amiwrong123 0..15 放 16 个槽互不冲突很简单,key = i 就好了啊,都没那个魔数什么事。hash 是要解决不定范围的数放 16 个槽
    amiwrong123
        15
    amiwrong123  
    OP
       2020-04-18 12:11:44 +08:00
    @lance6716 #14
    你这么说,倒真是哈。。。比如让 ThreadLocal 的那个静态变量 HASH_INCREMENT 为 1 。一样实现,2 的幂里完美散列的效果。
    amiwrong123
        16
    amiwrong123  
    OP
       2020-04-18 12:24:32 +08:00
    @daozhihun
    嗯,我现在理解到了这点了。
    Aresxue
        17
    Aresxue  
       2020-04-18 12:58:50 +08:00
    完美散列是指 hashCode 不冲突,但是桶位的计算一般都是取后几位那么就很有可能冲突,说到底你混淆了桶位和 hashCode
    daozhihun
        18
    daozhihun  
       2020-04-18 13:14:24 +08:00 via Android
    @Aresxue hash code 也不可能不冲突,32 位的 hash code 不可能可以表示理论上无穷多的对象
    jorneyr
        19
    jorneyr  
       2020-04-18 13:37:16 +08:00
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.List;

    public class Test {
    public static void main(String[] args) {
    final int MAGIC_NUMBER = 0x61c88647;
    final int N = 16;

    List<Integer> list = new ArrayList<>(N);

    for (int i = 0; i < N; ++i) {
    int index = (MAGIC_NUMBER * i) & (N - 1);
    list.add(index);
    }

    System.out.println(list);
    Collections.sort(list);
    System.out.println(list);

    // 如果非递增序列,则输出 Error
    for (int i = 1; i < list.size(); ++i) {
    if (list.get(i) <= list.get(i-1)) {
    System.out.println("Error");
    break;
    }
    }
    }
    }


    输出
    [0, 7, 14, 5, 12, 3, 10, 1, 8, 15, 6, 13, 4, 11, 2, 9]
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

    是不会冲突的,当使用到 80% 的时候就扩大数组了,根本不给使用完的机会。
    Aresxue
        20
    Aresxue  
       2020-04-18 13:41:25 +08:00
    @daozhihun 这只是个近似说法,因为正常情况下使用不到上限而已。而上面的完美散列也只是利用黄金分割率来达到一种勉强的不冲突而已(也没有真实达到),这个方法的好处只在于计算 hash 的方法极其简单所以性能也非常的好
    brucefu
        21
    brucefu  
       2020-04-18 13:51:10 +08:00
    看来还是懒了,debug 就能解决了,哈
    daozhihun
        22
    daozhihun  
       2020-04-18 13:56:37 +08:00 via Android
    @Aresxue 是的,你这个说法没错,只是经过很多实验得到的一个相对均匀的分布方法
    brucefu
        23
    brucefu  
       2020-04-18 14:14:09 +08:00
    感觉在问 XX 不是永动机吗?
    amiwrong123
        24
    amiwrong123  
    OP
       2020-04-19 11:27:42 +08:00
    @Aresxue
    @daozhihun
    @lance6716
    各位大佬,可否再帮忙解答一个问题。
    就是使用这个魔数只是为了哈希相对均匀的分布,那么如果不使用这个魔数,直接让静态变量 HASH_INCREMENT 为 1,会有什么坏处吗?(是不是因为 ThreadLocalMap 用的开发寻址,所以如果哈希均匀分布,那么冲突的时候,就能大概率更快的找到冲突后的新位置吗)
    lance6716
        26
    lance6716  
       2020-04-19 13:07:03 +08:00 via Android
    @amiwrong123 等于 1 的话,哈希结果均匀要依赖输入均匀。现在对输入的依靠更弱
    zzkde
        27
    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,不会扩容。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5200 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 32ms · UTC 03:52 · PVG 11:52 · LAX 19:52 · JFK 22:52
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.