欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

字典哈希表的实现原理

程序员文章站 2022-06-28 21:29:23
两个数组 bucket数组:存储key的hash桶,桶指的是把hashcode分配到一定的范围内 entry数组:用来存储实现的值,它是一个单向链表,bucket总是存储链表的最后一个元素 实现方式 通过哈希桶来实现的k/v存储,通过key的hash码,再进行桶计算,生成一个在某个范围内的值,这就是 ......

两个数组

  • bucket数组:存储key的hash桶,桶指的是把hashcode分配到一定的范围内
  • entry数组:用来存储实现的值,它是一个单向链表,bucket总是存储链表的最后一个元素

实现方式

通过哈希桶来实现的k/v存储,通过key的hash码,再进行桶计算,生成一个在某个范围内的值,这就是桶的索引号,再把值存储到桶对应的entry里,桶bucket存储了entry的索引号,通过一个bucket可以直接或者间接找到一个entry.

  1. 直接找到:当hash没有冲突时,它存储的就是真实的entry索引
  2. 间接找到:当hash出现冲突(碰撞)时,它就会把当前最后的索引赋值这个新entry.next,而新的entry的索引就是现在的bucket的值。

实现流程图

graph lr key-->hashcode hashcode-->bucket桶运算 bucket桶运算-->得到bucket索引 得到bucket索引-->bucket值就是entry的索引 bucket值就是entry的索引-->x("↓")
graph lr bucket值就是entry的索引-->冲突解决 冲突解决-->单向链表next指向上一个值 单向链表next指向上一个值-->单身链表查找 单身链表查找-->返回结果

数组长度为素数

hash桶数全部使用的是质数,因为我们在hash的定义中,hash函数使用的是标准的求模函数,因此这样定义桶数有利于元素各个桶之间的均匀分布减少hash相同值的碰撞概率。 例如:

举一个有点极端的例子,假设我们的元素全是偶数1,4,6,8,10,12,14,1,6,18,20,22

如果我们使用4个桶:

0: 4,8,12,16.20

1:

2:6,10,14,18,22

3:

很明显看出有的桶有很多元素,但是有的桶是空桶,如果我们改为使用3个桶:

0:  6,12,18

1:4,10,16,22

2:2,8,14,20

模拟一个字典的实现

@getter
@setter
class kvpair<k, t> {
  private k key;
  private t value;
  private int hashcode;
  private int next; //下一个元素的下标索引,如果没有下一个就为-1
}

/**
 * 模拟实现一个字典kv结构.
 *
 * @param <t>
 */
class mokihashmap<k, t> {
  static int[] primes = {
      3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 761, 919,
      1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591,
      17519, 21023, 25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523, 108631, 130363, 156437,
      187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263,
      1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471, 7199369};
  // 桶数组
  private int[] buckets;// 最新的entry的索引号,
  // 真实的数据
  private kvpair<k, t>[] entry; // entry根据next形成一个单链表
  private int count = 0;          // 当前entries的数量

  public mokihashmap() {
    buckets = new int[3];
    entry = new kvpair[3];
    for (int i = 0; i < buckets.length; i++) {
      buckets[i] = -1;
    }
  }

  private void resize() {
    int newlength = getprime(count);
    int[] newbuckets = new int[newlength];
    for (int i = 0; i < newbuckets.length; i++) {
      newbuckets[i] = -1;
    }
    kvpair<k, t>[] newentries = new kvpair[newlength];
    system.arraycopy(entry, 0, newentries, 0, count);
    system.arraycopy(buckets, 0, newbuckets, 0, count);
    entry = newentries;
    buckets = newbuckets;
  }

  /**
   * 得到某个key所在的hash桶
   *
   * @param key .
   * @return
   */
  private int gethashbucketindex(k key) {
    int len = buckets.length;
    int hashcode = key.hashcode();
    int index = hashcode & (len - 1);//len升级的hash桶
    return index;
  }

  /**
   * 得到较大的素数.
   *
   * @param min .
   * @return
   */
  private int getprime(int min) {
    if (min < 0) {
      throw new illegalargumentexception("最小为3");
    }
    for (int i = 0; i < primes.length; i++) {
      int prime = primes[i];
      if (prime > min) return prime;
    }

    return min;
  }

  public void add(k key, t value) {
    if (count == entry.length) {
      resize();
    }
    int index = gethashbucketindex(key);
    int entryindex = buckets[index];
    entry[count] = new kvpair();
    if (entryindex < 0) {
      entry[count].setnext(-1);
    } else {
      entry[count].setnext(buckets[index]);
    }
    entry[count].sethashcode(index);
    entry[count].setkey(key);
    entry[count].setvalue(value);
    buckets[index] = count;
    count = count + 1;
  }

  public t find(k key) {
    int entryindex = buckets[gethashbucketindex(key)];
    while (entry[entryindex].getnext() > -1) {
      if (entry[entryindex].getkey().equals(key)
          && entry[entryindex].gethashcode() == gethashbucketindex(key)) {
        return entry[entryindex].getvalue();
      }
      entryindex = entry[entryindex].getnext();
    }
    return null;
  }
}

public class kvtest {
  @test
  public void testdic() {
    mokihashmap<string, string> dic = new mokihashmap<>();
    dic.add("ok", "1");
    dic.add("zzl", "2");
    dic.add("lr", "3");
    dic.add("dd", "1");
    dic.add("a", "b");
    dic.add("b", "c");
    dic.add("d", "e");
    dic.add("e", "f");

    system.out.println("dic find:" + dic.find("a"));
  }
}