扰动函数和拉链法模拟HashMap的存储结构
HashMap是Map接口下面的子孙，它对外是K,V结构存储的，而内部也着自己的存储结构，它的get操作是O(1)的时间复杂度，可以说是非常快的找到目录，而添加时，也是O(1)，所以在键值存储里，它成为了我们的首选，在多线程情况下，要注意，它不是线程安全的。如果是多线程情况下，请使用 ConcurrentHashMap
.
就是JDK1.8之前
JDK1.8 之前 HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列。HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash
判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过 拉链法
解决冲突。
我们简单起见，我们使用Map来模块Map的查找方式，真正的Map是使用数组+链表实现的。
模拟你的Map的查找过程
/**
* 扰动法+拉链法.
*/
void moniMap(Map<Integer, Map<String, String>> moni, String val, int length) {
int index = (length - 1) & val.hashCode();
if (moni.containsKey(index)) {
Map<String, String> map = moni.get(index);
map.put(val, val);
} else {
moni.put(index, new HashMap<String, String>() {{
put(val, val);
}});
}
}
添加一个测试代码
@Test
public void moniTest() {
int len = 4;
Map<Integer, Map<String, String>> moni = new HashMap<>();
moniMap(moni, "a", len);
moniMap(moni, "b", len);
moniMap(moni, "c", len);
moniMap(moni, "b", len);
moniMap(moni, "e", len);
moniMap(moni, "zzl", len);
moniMap(moni, "zhl", len);
moniMap(moni, "zhz", len);
System.out.println(moni);
}
结果
{
0={zzl=zzl, zhz=zhz},
1={a=a, e=e},
2={b=b, zhl=zhl},
3={c=c}
}
从结果中我们可以看到，首先根据扰动法找到一个索引号，然后当不同hash在计算后生成了相同的索引号，这时需要走拉链法，将他们分组到一个链表里，就这样，我们看到
了一个被分组之后的数据。
正文到此结束
热门推荐
相关文章
Loading...
![[HBLOG]公众号](http://www.liuhaihua.cn/img/qrcode_gzh.jpg)
