大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
哈希表定义
- 散列表(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
- 线性探测再散列
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/179087.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...