跳至主要內容
  • Hostloc 空間訪問刷分
  • 售賣場
  • 廣告位
  • 賣站?

4563博客

全新的繁體中文 WordPress 網站
  • 首頁
  • ThreadLocalMap 的源码看起来会考虑一种哈希冲突的情况,但不是 ThreadLocal 本身实现了完美散列吗?
未分類
2 5 月 2020

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

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

資深大佬 : amiwrong123 13

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

大佬有話說 (26)

  • 資深大佬 : lyjr

    哈希值不同,但是运算得到的地址是可能相同的,就是这句喽,int i = key.threadLocalHashCode & (table.length – 1);
    i 肯定可能冲突嘛。
    高层面上想一想也不可能嘛,世界上哪有不冲突的哈希表,一个无限的集合映射到一个有限的集合,能不冲突吗

  • 主 資深大佬 : amiwrong123

    @lyjr
    但是见此博客 https://www.cnblogs.com/dennyzhangdd/p/7978455.html 中的 MagicHashCode 测试类,利用魔数后,就算是取模后的 i,在有限的 2 的幂的哈希表,也没有一个 i 冲突啊。

  • 資深大佬 : wysnylc

    有答案了 @我下蟹蟹

  • 資深大佬 : lyjr

    @amiwrong123 举个最简单的例子,长度为 2^3=8 的哈希表,插入 9 个元素,如果不冲突的话,最后一个元素放在哪里?
    根本不用想太多,跟任何数据结构和算法都无关,本质上是一个集合映射的数学问题,9 个元素的集合不肯能无冲突的映射到大小为 8 的集合。

  • 資深大佬 : coer

    这个魔数可以完美散列,学到了

  • 主 資深大佬 : amiwrong123

    @lyjr
    但是,ThreadLocalMap 里面的 key,如果个数大于了阈值,就会在 rehash 啊,然后容量变成下一个 2 的幂。也就不会出现你说的这种情况了啊

  • 資深大佬 : coer

    https://blog.csdn.net/outsanding/article/details/104688125

  • 資深大佬 : cheng6563

    散列都是有可能冲突的,不管多少位。

  • 資深大佬 : wysnylc

    斐波那契数列,0x61c88647 对应 10 进制是 1640531527

  • 資深大佬 : CoderGeek

    有限集映射无限 你告诉我没冲突 你的数据结构老师要打人了 离散的老师也要气疯了

  • 資深大佬 : lance6716

    @amiwrong123 啥玩意,0x61c88647 咋就成了完美散列了。csdn 现在越来越能扯了

  • 資深大佬 : daozhihun

    魔数只是让哈希相对均匀的分布,怎么可能完全没有冲突。

  • 主 資深大佬 : amiwrong123

    好吧,我错了。我好像想通了。
    “`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

    @amiwrong123 0..15 放 16 个槽互不冲突很简单,key = i 就好了啊,都没那个魔数什么事。hash 是要解决不定范围的数放 16 个槽

  • 主 資深大佬 : amiwrong123

    @lance6716 #14
    你这么说,倒真是哈。。。比如让 ThreadLocal 的那个静态变量 HASH_INCREMENT 为 1 。一样实现,2 的幂里完美散列的效果。

  • 主 資深大佬 : amiwrong123

    @daozhihun
    嗯,我现在理解到了这点了。

  • 資深大佬 : Aresxue

    完美散列是指 hashCode 不冲突,但是桶位的计算一般都是取后几位那么就很有可能冲突,说到底你混淆了桶位和 hashCode

  • 資深大佬 : daozhihun

    @Aresxue hash code 也不可能不冲突,32 位的 hash code 不可能可以表示理论上无穷多的对象

  • 資深大佬 : jorneyr

    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

    @daozhihun 这只是个近似说法,因为正常情况下使用不到上限而已。而上面的完美散列也只是利用黄金分割率来达到一种勉强的不冲突而已(也没有真实达到),这个方法的好处只在于计算 hash 的方法极其简单所以性能也非常的好

  • 資深大佬 : brucefu

    看来还是懒了,debug 就能解决了,哈

  • 資深大佬 : daozhihun

    @Aresxue 是的,你这个说法没错,只是经过很多实验得到的一个相对均匀的分布方法

  • 資深大佬 : brucefu

    感觉在问 XX 不是永动机吗?

  • 主 資深大佬 : amiwrong123

    @Aresxue
    @daozhihun
    @lance6716
    各位大佬,可否再帮忙解答一个问题。
    就是使用这个魔数只是为了哈希相对均匀的分布,那么如果不使用这个魔数,直接让静态变量 HASH_INCREMENT 为 1,会有什么坏处吗?(是不是因为 ThreadLocalMap 用的开发寻址,所以如果哈希均匀分布,那么冲突的时候,就能大概率更快的找到冲突后的新位置吗)

  • 資深大佬 : daozhihun

    @amiwrong123 https://stackoverflow.com/questions/38994306/what-is-the-meaning-of-0x61c88647-constant-in-threadlocal-java

  • 資深大佬 : lance6716

    @amiwrong123 等于 1 的话,哈希结果均匀要依赖输入均匀。现在对输入的依靠更弱

文章導覽

上一篇文章
下一篇文章

AD

其他操作

  • 登入
  • 訂閱網站內容的資訊提供
  • 訂閱留言的資訊提供
  • WordPress.org 台灣繁體中文

51la

4563博客

全新的繁體中文 WordPress 網站
返回頂端
本站採用 WordPress 建置 | 佈景主題採用 GretaThemes 所設計的 Memory
4563博客
  • Hostloc 空間訪問刷分
  • 售賣場
  • 廣告位
  • 賣站?
在這裡新增小工具