JDK中hash冲突解决的两种方法

哈希表定义

• 散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。 也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。 这个映射函数称做散列函数，存放记录的数组称做散列表。

实现关键点

• hash函数
• hash冲突解决

hash函数
首先来说hash函数，java中对象都已一个hashCode()
方法，那为什么还需要hash函数呢？hashCode是在jdk中是有符号int类型，这个一个很大的范围，如果散列表的数组能覆盖所有int值的话，就不需要hash函数了，当然内存不允许我们维护这么大的散列表。这时我们需要hash函数将原始hashCode映射到一个很小的数组上去。
常见的做法是取模法，也是jdk中的实现方式。

• HashMap实现

static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

 static int indexFor(int h, int length) {return h & (length-1);}

第一个hash函数有人称之为“扰动函数”，第二个indexFor函数在jdk8中去掉了，函数内的代码合并到了putVal中，个人认为这两个函数合并起来是一个完整的hash函数。
h & (length-1) 这段代码的作用其实就是取模，假设数组初始化长度为16，那么length-1的结果为15，对应二进制为00001111，如果我们有一个大小为20的key，对应二进制为00010100，与运算后结果为00000100，对应十进制为4.
这里数组的长度必须为2的次幂。

由于对key进行了取模运算，所以我们知道当length=16的时候，我们会舍弃调掉key高位的值，只保留了低4位。本来int是32位，只是用低4位冲突是不是太容易发生了？
所以第一个“扰动函数”的作用出现了，这个函数将key本身高16和低16位做了异或运算。

从网上找了这张图，可以解释下(h = key.hashCode()) ^ (h >>> 16) 的作用。

通过高位和低位异或之后，本来被丢弃的高位值在做取模运算的时候也能体现得到。

• ThreadLocal.ThreadLocalMap实现

 private void set(ThreadLocal key, Object value) {// We don't use a fast path as with get() because it is at// least as common to use set() to create new entries as// it is to replace existing ones, in which case, a fast// path would fail more often than not.Entry[] tab = table;int len = tab.length;int i = key.threadLocalHashCode & (len-1);for (Entry e = tab[i];e != null;e = tab[i = nextIndex(i, len)]) {ThreadLocal k = e.get();if (k == key) {e.value = value;return;}if (k == null) {replaceStaleEntry(key, value, i);return;}}tab[i] = new Entry(key, value);int sz = ++size;if (!cleanSomeSlots(i, sz) && sz >= threshold)rehash();}

其中int i = key.threadLocalHashCode & (len-1); 就是直接取模。

hash冲突避免

• HashMap
  
  • 拉链法
• ThreadLocal.ThreadLocalMap
  
  • 线性探测再散列

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！