关于数据结构和算法:自己动手实现-HashMapPython字典彻底系统的学习哈希表上篇不看血亏

HashMap（Python字典）设计原理与实现（上篇）——哈希表的原理

在此前的四篇长文当中咱们曾经实现了咱们本人的ArrayList和LinkedList，并且剖析了ArrayList和LinkedList的JDK源代码。 本篇文章次要跟大家介绍咱们十分罕用的一种数据结构HashMap，在本篇文章当中次要介绍他的实现原理，下篇咱们本人入手实现咱们本人的HashMap，让他能够像JDK的HashMap一样工作。

如果有公式渲染不了，可查看这篇内容雷同且可渲染公式的文章

HashMap初识

如果你应用过HashMap的话，那你必定很相熟HashMap给咱们提供了一个十分不便的性能就是键值(key, value)查找。比方咱们通过学生的姓名查找分数。

  public static void main(String[] args) {    HashMap<String, Integer> map = new HashMap<>();    map.put("学生A", 60);    map.put("学生B", 70);    map.put("学生C", 20);    map.put("学生D", 85);    map.put("学生E", 99);    System.out.println("学生B的分数是：" + map.get("学生B"));  }

咱们晓得HashMap给咱们提供查问get函数性能的工夫复杂度为O(1)，他在常数级别的工夫复杂度就能够查问到后果。那它是如何做到的呢？

咱们晓得在计算机当中一个最根本也是惟一的，可能实现常数级别的查问的类型就是数组，数组的查问工夫复杂度为O(1)，咱们只须要通过下标就能拜访对应的数据。比方咱们想拜访下标为6的数据，就能够这样：

String[] strs = new String[10];strs[6] = "一无是处的钻研僧";System.out.println(strs[6]);

因而咱们要想实现HashMap给咱们提供的O(1)级别查问的工夫复杂度的话，就必须应用到数组，而在具体的HashMap实现当中，比如说JDK底层也是采纳数组实现的。

HashMap整体设计

咱们实现的HashMap须要满足的最重要的性能是依据键(key)查问到对应的值(value)，比方下面提到的依据学生姓名查问问题。

因而咱们能够有一个这样的设计，咱们能够依据数据的键值计算出一个数字（像这种能够将一个数据转化成一个数字的叫做哈希函数，计算出来的值叫做哈希值咱们后续将会认真阐明），将这个哈希值作为数组的下标，这样的话键值和下标就有了对应关系了，咱们能够在数组对应的哈希值为下标的地位存储具体的数据，比方下面谈到的问题，整个流程如下图所示：

然而像这种哈希函数计算出来的数值个别是没有范畴的，因而咱们通常通过哈希函数计算出来的数值通常会通过一个求余数操作(%)，对数组的长度进行求余数，否则求进去的数值将超过数组的长度。比方数组的长度是16，计算出来的哈希值为186，那么求余数之后的后果为186%16=10，那么咱们能够将数据存储在数组当中下标为10的地位，下次咱们来取的时候就取出下标为10地位的数据即可。

如何设计一个哈希函数？

首先咱们须要理解一个常识，那就是在计算机世界当中咱们所含有的两种最根本的数据类型就是，整型(short, int, long)和字符串(String)，其余的数据类型能够由这些数据类型组合起来，上面咱们来剖析一下常见的数据类型的哈希函数设计。

整型的哈希函数

对于整型数据，他原本就是一个数值，因而咱们能够间接将这个值返回作为他的哈希值，而JDK中也是这么实现的！JDK中实现整型的哈希函数的办法：

    /**     * Returns a hash code for a {@code int} value; compatible with     * {@code Integer.hashCode()}.     *     * @param value the value to hash     * @since 1.8     *     * @return a hash code value for a {@code int} value.     */    public static int hashCode(int value) {        return value;    }

字符串的哈希函数

咱们晓得字符串底层存储的还是用整型数据存储的，比说说字符串hello world，就能够应用字符数组['h', 'e', 'l', 'l', 'o' , 'w', 'o', 'r', 'l', 'd']进行存储，因为咱们计算出来的这个哈希值须要尽量不和别的数据计算出来的哈希值抵触（这种景象叫做哈希抵触，咱们前面会认真探讨这个问题），因而咱们要尽可能的充分利用字符串外面的每个字符信息。咱们来看一下JDK当中是怎么实现字符串的哈希函数的

public int hashCode() {    // hash 是 String 类当中一个公有的 int 变量，次要作用即存储计算出来的哈希值    // 防止哈希值反复计算 节约工夫    int h = hash; // 如果是第一次调用 hashCode 这个函数 hash 的值为0，也就是说 h 值为 0    // value 就是存储字符的字符数组    if (h == 0 && value.length > 0) {        char val[] = value;        for (int i = 0; i < value.length; i++) {            h = 31 * h + val[i];        }        // 更新 hash 的值        hash = h;    }    return h;}

下面的计算hashCode的代码，能够用上面这个公式示意：

• 其中s，示意存储字符串的字符数组
• n示意字符数组当中字符的个数

$$s[0]*31^{(n-1)} + s[1]*31^{(n-2)} + ... + s[n-1]$$

自定义类型的哈希函数

比方咱们本人定义了一个学生类，咱们改设计他的哈希函数，并且计算他的哈希值呢？

class Student {  String name;  int grade;}

咱们能够依据下面提到的两种哈希函数，仿照他们的设计，设计咱们本人的哈希函数，比方像上面这样。

class Student {  String name;  int grade;      // 咱们本人要实现的哈希函数  @Override  public int hashCode() {    return name.hashCode() * 31 + grade;  }      @Override  public boolean equals(Object o) {    if (this == o) return true;    if (o == null || getClass() != o.getClass()) return false;    Student student = (Student) o;    return grade == student.grade &&        Objects.equals(name, student.name);  }}

事实上JDK也贴心的为咱们实现了一个类，去计算咱们自定义类的哈希函数。

// 上面这个函数是咱们本人设计的类 Student 的哈希函数@Overridepublic int hashCode() {    return Objects.hash(name, grade);}// 上面这个函数为  Objects.hash 函数public static int hash(Object... values) {    return Arrays.hashCode(values);}// 上面这个函数为  Arrays.hashCode 函数public static int hashCode(Object a[]) {    if (a == null)        return 0;    int result = 1;    for (Object element : a)        result = 31 * result + (element == null ? 0 : element.hashCode());    return result;}

JDK帮忙咱们实现的哈希函数，实质上就是将类当中所有的字段封装成一个数组，而后像计算字符串的哈希值那样去计算咱们自定义类的哈希值。

汇合类型的哈希函数

其实汇合类型的哈希函数也能够像字符串那样设计哈希函数，咱们来看一下JDK外部是如何实现汇合类的哈希函数的。

public int hashCode() {    int hashCode = 1;    // 遍历汇合当中的对象，进行哈希值的计算    for (E e : this)        hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());    return hashCode;}

上述代码也能够用之前的公式来示意，其中s[i]示意汇合当中第i个数据对象：

$$s[0]*31^{(n-1)} + s[1]*31^{(n-2)} + ... + s[n-1]$$

哈希抵触

因为咱们用的最终的数组的下标是通过哈希值取余数失去的，那么就有可能产生抵触。比如说咱们的数组长度为10，有两个数据他们的哈希值别离为8和28，他们对10取余之后失去的后果都为8那么改如何解决这个问题呢？

凋谢地址法（再散列法）

线性探测再散列

假如咱们的哈希函数为H，咱们的数组长度为m，咱们的键为key，那么我计算出来的下标为：

$$h_i = H(key) \% m$$

当咱们有哈希抵触的时候，咱们计算下标的办法变为：

$$h_i = (H(key) + d_i) \% m, d_i = i$$

当咱们第一次抵触的时候$d_1 = 1$，如果从新进行计算依然抵触那么$d_2 = 2$ ......

比方在上图当中咱们首次计算的哈希值$H(key) = 5$的后果等于5，如果有哈希抵触，那么下次计算出来的哈希值为$(H(key) + 1) \% 12 = 6$，如果还是抵触那么计算出来的哈希值为$(H(key) + 2) \% 12 = 7$ ......，直到找到一个空地位。谈到这里你可能会问，万一都满了呢？咱们在下一大节再谈这个问题。

二次探测再散列

$$h_i = (H(key) + d_i) \% m, d_i = (-1)^{i - 1} i^2$$

这个散列办法和线性探测散列差不多，只不过$d_i$的值变动状况不一样而已，大家能够参考线性探测进行剖析，这个办法能够往数组的两个办法走，因为后面有一个而线性探测只能往数组的一个方向走。此外这个办法走的间隔比线性探测更大，因而可能能够在更小的抵触次数当中找到一个空地位。

伪随机数再散列

$$h_i = (H(key) + d_i) \% m, d_i = 一个随机数$$

这个形式的大抵策略和后面差不多，只不过$d_i$上略微有所差别。

再哈希法

咱们能够筹备多个哈希函数，当应用一个哈希函数产生抵触的时候，咱们能够换一个哈希函数，心愿通过不同的哈希函数失去不同的哈希值，以解决哈希抵触的问题。

链地址法

这个办法是目前应用比拟多的办法，当产生哈希抵触的时候，数据用一个链表将抵触的数据链接起来，比方像上面这样：

以上就是一些常见的解决哈希抵触的办法，因为都是文字说明没有代码，你可能略微有些难以了解，比如说我通过下面的办法存储数据，那么我之后怎么拿到我存进去的数据呢？如同放进去就拿不进去了呀！没事儿，这些疑难咱们在下篇本人实现哈希表的时候会一一解开，到时候你就发现原来这些算法的设计如此奇妙。

扩容

在下面的文章当中咱们并没有谈到当数组满了之后怎么办。很简略嘛，我能够应用一个变量记录数组当中曾经应用了的空间，如果全副应用过了，咱们就进行扩容，扩充咱们的数组就能够了嘛！而后将原数组当中的数据从新进行哈希寄存到新数组当中即可！因为咱们在计算存储下标的时候须要对数组长度进行取余，而当咱们申请新数组的时候数组长度曾经发生变化了，因而须要从新对数据进行哈希操作。这外面依然有很多须要思考的细节问题，这些问题咱们在下篇当中进行代码实现的时候会认真探讨。

总结

在本篇文章当中，咱们次要谈到了如何去设计一个能够应用的哈希表，同时介绍了咱们改如何设计一个哈希函数，最终谈到了解决哈希抵触和数组满了的问题！！！

• HashMap整体的设计构造。

• 设计一个好的哈希函数。

  • 整型数据的哈希函数。
  • 字符串的哈希函数。
  • 自定义类型的哈希函数。
  • 汇合的哈希函数。

• 解决哈希抵触的方法。

  • 凋谢地址法

    • 线性探测
    • 二次探测
    • 随机数探测
  • 再哈希法
  • 链地址地址法
• 扩容办法

以上就是本篇文章的所有内容了，咱们将在下篇当中本人入手实现一个本人的哈希表MyHashMap，这其中还有很多十分细节的设计，其中波及到很多位运算操作和很多其余十分奇妙的操作。我是LeHung咱们下期再见！！！

更多精彩内容合集，可拜访：https://github.com/Chang-LeHu...

关注公众号：一无是处的钻研僧，理解更多计算机常识！！！