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
- /**
- * 原版 - 扰动法 + 拉链法
- *
- * @param list
- * @param val
- */
- void moniLinkList(LinkedList[] list, String val) {
- int length = list.length;
- int index = (length - 1) & val.hashCode();
- LinkedList linkedList = list[index];
- if (linkedList != null) {
- linkedList.add(val);
- } else {
- linkedList = new LinkedList();
- linkedList.add(val);
- }
- list[index] = linkedList;
- }
测试一下
- @Test
- public void moniLinkListTest() {
- LinkedList[] list = new LinkedList[8];
- moniLinkList(list, "a");
- moniLinkList(list, "b");
- moniLinkList(list, "c");
- moniLinkList(list, "d");
- moniLinkList(list, "e");
- moniLinkList(list, "f");
- moniLinkList(list, "zzl");
- for (int i = 0; i <list.length; i++) {
- System.out.print(list[i] + " ");
- }
- }
结到我们希望的结果
null [a] [b] [c] [d, zzl] [e] [f] null
模拟你的 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 在计算后生成了相同的索引号, 这时需要走拉链法, 将他们分组到一个链表里, 就这样, 我们看到
了一个被分组之后的数据.
来源: https://www.cnblogs.com/lori/p/10913672.html