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

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

[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 的话，哈希结果均匀要依赖输入均匀。现在对输入的依靠更弱

[zzkde]

@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，不会扩容。