转载

扰动函数和拉链法模拟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在计算后生成了相同的索引号，这时需要走拉链法，将他们分组到一个链表里，就这样，我们看到

了一个被分组之后的数据。

原文 http://www.cnblogs.com/lori/p/10913672.html

正文到此结束

所属分类：编程技术 Java

本文标签： map http 安全快的线程 key HTML 测试时间索引目录代码 ConcurrentHashMap 多线程 HashMap 数据 id
版权声明： 本文为互联网转载文章，出处已在文章中说明(部分除外)。如果侵权，请联系本站长删除，谢谢。
本文海报： 生成海报一生成海报二

其他链接

关于本站

本站定位：个人技术类博客

本站作用：写博客、记日志、闲聊扯淡鼓捣技术。

问题交流

扰动函数和拉链法模拟HashMap的存储结构

就是JDK1.8之前

模拟你的Map的查找过程

热门推荐

相关文章

说给你听

本文目录

随机标签

书籍教程

近期评论

网站信息

其他链接

关于本站

问题交流