ThreadLocalMap 的源码看起来会考虑一种哈希冲突的情况,但不是 ThreadLocal 本身实现了完美散列吗? - V2EX
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
amiwrong123
V2EX    Java

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

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

    看 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(tring[] 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     Solana     1177 人在线   最高记录 6679       Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 30ms UTC 23:39 PVG 07:39 LAX 16:39 JFK 19:39
    Do have faith in what you're doing.
    ubao snddm index pchome yahoo rakuten mypaper meadowduck bidyahoo youbao zxmzxm asda bnvcg cvbfg dfscv mmhjk xxddc yybgb zznbn ccubao uaitu acv GXCV ET GDG YH FG BCVB FJFH CBRE CBC GDG ET54 WRWR RWER WREW WRWER RWER SDG EW SF DSFSF fbbs ubao fhd dfg ewr dg df ewwr ewwr et ruyut utut dfg fgd gdfgt etg dfgt dfgd ert4 gd fgg wr 235 wer3 we vsdf sdf gdf ert xcv sdf rwer hfd dfg cvb rwf afb dfh jgh bmn lgh rty gfds cxv xcv xcs vdas fdf fgd cv sdf tert sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf shasha9178 shasha9178 shasha9178 shasha9178 shasha9178 liflif2 liflif2 liflif2 liflif2 liflif2 liblib3 liblib3 liblib3 liblib3 liblib3 zhazha444 zhazha444 zhazha444 zhazha444 zhazha444 dende5 dende denden denden2 denden21 fenfen9 fenf619 fen619 fenfe9 fe619 sdf sdf sdf sdf sdf zhazh90 zhazh0 zhaa50 zha90 zh590 zho zhoz zhozh zhozho zhozho2 lislis lls95 lili95 lils5 liss9 sdf0ty987 sdft876 sdft9876 sdf09876 sd0t9876 sdf0ty98 sdf0976 sdf0ty986 sdf0ty96 sdf0t76 sdf0876 df0ty98 sf0t876 sd0ty76 sdy76 sdf76 sdf0t76 sdf0ty9 sdf0ty98 sdf0ty987 sdf0ty98 sdf6676 sdf876 sd876 sd876 sdf6 sdf6 sdf9876 sdf0t sdf06 sdf0ty9776 sdf0ty9776 sdf0ty76 sdf8876 sdf0t sd6 sdf06 s688876 sd688 sdf86