扰动函数和拉链法模拟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

/**
   * 原版-扰动法+拉链法
   *
   * @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在计算后生成了相同的索引号，这时需要走拉链法，将他们分组到一个链表里，就这样，我们看到
了一个被分组之后的数据。