散列表采用线性探测法会出现_平方探测法解决冲突

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

第一、前言
ThreadLocal使用的是自定义的ThreadLocalMap，接下来我们来探究一下ThreadLocalMap的hash冲突解决方式。
第二、ThreadLocal的set()方法

public void set(T value) { 
   
    Thread t = Thread.currentThread();
    ThreadLocal.ThreadLocalMap map = getMap(t);
    if (map != null)
        map.set(this, value);
    else
        createMap(t, value);
}
ThreadLocal.ThreadLocalMap getMap(Thread t) { 
   
	return t.threadLocals;
}
void createMap(Thread t, T firstValue) { 
   
	t.threadLocals = new ThreadLocal.ThreadLocalMap(this, firstValue);
}

1.代码很简单,获取当前线程,并获取当前线程的ThreadLocalMap实例（从getMap(Thread t)中很容易看出来）。
2.如果获取到的map实例不为空,调用map.set()方法,否则调用构造函数ThreadLocal.ThreadLocalMap(this, firstValue)实例化map。可以看出来线程中的ThreadLocalMap使用的是延迟初始化,在第一次调用get()或者set()方法的时候才会进行初始化。
第三、构造函数ThreadLocalMap(ThreadLocal<?> firstKey, Object firstValue)

ThreadLocalMap(ThreadLocal<?> firstKey, Object firstValue) { 
   
    //初始化table
    table = new ThreadLocal.ThreadLocalMap.Entry[INITIAL_CAPACITY];
    //计算索引
    int i = firstKey.threadLocalHashCode & (INITIAL_CAPACITY - 1);
    //设置值
    table[i] = new ThreadLocal.ThreadLocalMap.Entry(firstKey, firstValue);
    size = 1;
    //设置阈值
    setThreshold(INITIAL_CAPACITY);
}

主要说一下计算索引，firstKey.threadLocalHashCode & (INITIAL_CAPACITY – 1)。
关于& (INITIAL_CAPACITY – 1),这是取模的一种方式，对于2的幂作为模数取模，用此代替%(2^n)，这也就是为啥容量必须为2的冥，在这个地方也得到了解答。
关于firstKey.threadLocalHashCode：

private final int threadLocalHashCode = nextHashCode();
private static int nextHashCode() { 
   
    return nextHashCode.getAndAdd(HASH_INCREMENT);
}
private static AtomicInteger nextHashCode =  new AtomicInteger();
private static final int HASH_INCREMENT = 0x61c88647;

这里定义了一个AtomicInteger类型，每次获取当前值并加上HASH_INCREMENT，HASH_INCREMENT = 0x61c88647,这个值和斐波那契散列有关（这是一种乘数散列法，只不过这个乘数比较特殊，是32位整型上限2^32-1乘以黄金分割比例0.618…的值2654435769，用有符号整型表示就是-1640531527，去掉符号后16进制表示为0x61c88647），其主要目的就是为了让哈希码能均匀的分布在2的n次方的数组里, 也就是Entry[] table中，这样做可以尽量避免hash冲突。
第四、ThreadLocalMap中的set()
ThreadLocalMap使用闭散列:(开放地址法或者也叫线性探测法)解决哈希冲突，线性探测法的地址增量di = 1, 2, … 其中，i为探测次数。该方法一次探测下一个地址，直到有空的地址后插入，若整个空间都找不到空余的地址，则产生溢出。假设当前table长度为16，也就是说如果计算出来key的hash值为14，如果table[14]上已经有值，并且其key与当前key不一致，那么就发生了hash冲突，这个时候将14加1得到15，取table[15]进行判断，这个时候如果还是冲突会回到0，取table[0],以此类推，直到可以插入。
按照上面的描述，可以把table看成一个环形数组。
先看一下线性探测相关的代码，从中也可以看出来table实际是一个环：

private static int nextIndex(int i, int len) { 
   
    return ((i + 1 < len) ? i + 1 : 0);
}
private static int prevIndex(int i, int len) { 
   
    return ((i - 1 >= 0) ? i - 1 : len - 1);
}
private void set(ThreadLocal<?> key, Object value) { 
   
    ThreadLocal.ThreadLocalMap.Entry[] tab = table;
    int len = tab.length;
    //计算索引，上面已经有说过。
    int i = key.threadLocalHashCode & (len-1);
    /**根据获取到的索引进行循环，如果当前索引上的table[i]不为空，在没有return的情况下， * 就使用nextIndex()获取下一个（上面提到到线性探测法）。*/
    for (ThreadLocal.ThreadLocalMap.Entry e = tab[i]; e != null;
        e = tab[i = nextIndex(i, len)]) { 
   
        ThreadLocal<?> k = e.get();
        //table[i]上key不为空，并且和当前key相同，更新value
        if (k == key) { 
   
            e.value = value;
            return;
        }
        /**table[i]上的key为空，说明被回收了 * 说明改table[i]可以重新使用，用新的key-value将其替换,并删除其他无效的entry*/
        if (k == null) { 
   
            replaceStaleEntry(key, value, i);
            return;
        }
    }
    //不存在也没有旧元素就创建一个
    tab[i] = new Entry(key, value);
    int sz = ++size;
    if (!cleanSomeSlots(i, sz) && sz >= threshold)
        rehash();//扩容
}

第五、闭散列
当我们要往哈希表中插入一个数据时，通过哈希函数计算该值的哈希地址，当我们找到哈希地址时却发现该位置已经被别的数据插入了，那么此时我们就找紧跟着这一位置的下一个位置，看是否能够插入，如果能则插入，不能则继续探测紧跟着当前位置的下一个位置。

假设要将key=y的元素存入哈希表，通过哈希函数求出哈希地址为7，比较哈希地址7的元素的key是否等于y，不相等，继续比对哈希地址为8的元素…直到找到哈希地址为2的位置，可以存储。

要进一步了解相关内容可以阅读:探究ThreadLocal内存泄漏及弱引用

欢迎大家积极留言交流学习心得，点赞的人最美丽。谢谢！