算法与数据结构 - 散列表

点赞再看,养成习惯

---

引言

某日,韩梅梅和李雷来到一家新开的网红图书馆借阅书籍。
韩梅梅： 李雷，快来帮我找下《数据结构从入门到放弃》
李雷看了下周围书籍拜访，一脸苦恼的说： 这家图书馆的书籍摆放并不是很科学，可能我们要费一些时间~
韩梅梅：为什么不科学呢？
李雷：因为它摆放 书籍并没有按照某种规律进行拜访，我们查找书籍就只能够随机的去寻找，这样无疑是很浪费时间的。
韩梅梅：那你有办法优化下吗？
李雷：当然！

一、散列表概述

我们先不管什么是哈希表，先来看下如果物品没有规律随即摆放会怎么样。比如此时我们有Java，C,C++,C#,Python，JS，Mysql，Go，Rust几本书，如果我们随即摆放并查找Rust，可能出现的最坏情况如下：

由于没有规律，我们只能够进行按照已有顺序进行随机访问，经过9次才找到我们的目标书籍。但如果我们按照书籍的首字母进行归纳，然后再进行查找，最坏情况又会不同：

我们仅需6次就可以完成之前需要9次查找就可以完成的工作。当然这时候会有小伙伴有疑问，如果我所有书籍首字母都不同怎么办？我们显然不能够所有场景都按照字典目录的方式进行归纳，这种时候就需要我们提出一种新的方法来解决数据归纳的问题。

1.1 哈希函数

什么是哈希函数？ 我们可以简单的将它理解为是一种接口转换器。我们将已有的数据经过哈希函数加工后会得到一种固定长度的无规律数值，转换出来的数值就可以用在各种各样的场景中。

这里要简单的说一下，哈希函数有很多种算法实现，比如我们在密码安全加密方面常见的MD5,SHA-1,SHA-2等等，其中SHA-2是我们使用场景最广泛的一种。

哈希函数也是我们使用散列表的必须前提之一，我们需要通过哈希函数来计算元素将要进入我们已经划分好的具体哪个区域。既然如此，我们可以先简单的设计一个哈希算法。

1. 首先第一步，我们先确定我们会有n个空间用来存放相同函数值的元素
2. 第二步我们需要确认我们通过什么特征来进行哈希运算，这里我们决定选用字符串的字典序进行。
3. 最后我们只需要设定规则，我们哈希运算的规则就是字典序 % n 获取到的余数即为哈希结果。

让我们简单的写一段代码：

    public Integer getHashCode(String param, Integer count) {
        Integer lexicographicOrder = param.chars().sum();
        return lexicographicOrder & count;
    }
1
2
3
4

我们简单写一段测试代码测试下。

很好，我们已经可以通过字符串来进行哈希运算了。

1.2 散列表

我们回到正题，之所以要设计一个哈希函数本质上是为了我们可以将具有相同哈希值的元素划分到同一区域，那么有了依据我们就要深入的去想一下我们该如何分割区域。

1. 首先既然我们是以余数作为元素区分依据，那么我们就应该有对应多的区域（n），这个区域应该是固定且支持随机访问的。回顾我们之前学过的数据结构，数组无疑是最符合这个特性的，这样我们就完成了散列表设计的第一步。
2. 接下来我们需要选一个数据结构来存放划分到这个区域的元素，这个时候我们对于数据的访问应该是按照顺序依次进行，而且能够很好的支持数据增删的。基于这个需求，我们选用了链表作为元素存放的基础数据结构。

然后我们需要做的就是将数组和链表组装到一起，就像是这样：

这就是一个散列表的简单雏形，到这里我们已经做了三件事情:
3. 设计了一个可以精准计算元素分区的散列函数。
4. 使用支持随机访问的数组结构作为分区数据的目录
5. 使用链表结构用来存储已经分好区域的元素

接下来我们需要做的就是将这三个已经完成的事情组装到一起，用代码写一个简易的散列表：

public class MyHash {

    private LinkedList<String>[] linkedLists = new LinkedList[6];

    public MyHash() {
        for (int i = 0; i < linkedLists.length; i++) {
            if (linkedLists[i] == null) {
                linkedLists[i] = new LinkedList<>();
            }
        }
    }


    public Integer getHashCode(String param, Integer count) {
        Integer lexicographicOrder = param.chars().sum();
        return lexicographicOrder & count;
    }

    public Boolean put(String item) {
        Integer hashCode = getHashCode(item, linkedLists.length);
        linkedLists[hashCode].add(item);
        return Boolean.TRUE;
    }


    public String toString() {
        StringBuilder result = new StringBuilder();
        for (LinkedList<String> linkedList : linkedLists) {
            linkedList.forEach(item -> result.append(item + "\n"));
        }
        return result.toString();
    }


    public static void main(String[] args) {
        MyHash myHash = new MyHash();
        myHash.put("java");
        myHash.put("js");
        myHash.put("python");
        myHash.put("matlab");
        myHash.put("c++");
        myHash.put("c");
        System.out.println(myHash.toString());
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

运行一下：

不过我们这个散列表的能力还很弱，很多实用的功能诸如去重，解决hash碰撞，根据负载因子动态扩容等功能都还没有实现，如果感兴趣的小伙伴可以自己动手试一下。

二、算法实战

2.1 两数之和

题目

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。

示例1:

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

1
2
3
4

示例2:

输入： nums = [3,2,4], target = 6
输出： [1,2]
1
2

题解

1. 暴力破解

思路:
暴力枚举通常是我们解题时最常想到的方法,例如此题我们的目标是寻找相加等于target的两个数组元素。假设我们在遍历数组时的当前元素为currentValue，此时我们就需要再次去数组中遍历寻找一个值，此值等于target - currentValue ，若能找到则返回两个元素下标，若找不到则返回null。

代码：

/*枚举解法*/
private static int[] twoSumByExhaustion(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] == target - nums[i]) {
                return new int[]{i, j};
            }
        }
    }
    return null;
}
1
2
3
4
5
6
7
8
9
10
11

复杂度分析：

• 时间复杂度：O(N^2)，其中 N 是数组中的元素数量。
• 空间复杂度：O(1)。

运行结果：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-zmppqJYu-1668481560674)(https://p9-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/df0fd5e260ce4d3787809589a023ad65~tplv-k3u1fbpfcp-watermark.image?)]

2. hash表

思路：
由于本题并没有限制我们使用额外的内存空间，因此我们可以借助额外的内存空间存储数组中的元素以达到减少遍历次数的目的。

代码：

/*hash表解法*/
private static int[] twoSum(int[] nums, int target) {
    // 首先创建一个hash表
    Map intMap = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        // 判断hash表中是否已经存有目标元素
        Integer integer = intMap.get(target - nums[i]);
        if (integer != null) {
            // 若有则返回坐标
            return new int[]{integer, i};
        }
        // 如没有则存放元素,继续遍历
        intMap.put(nums[i], i);
    }
    return null;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

复杂度分析

• 时间复杂度：O(N)，其中 N 是数组中的元素数量。
• 空间复杂度：O(N)。

运行结果：

结语

今天的内容就到此结束了，有疑问的小伙伴欢迎评论区留言或者私信博主，博主会在第一时间为你解答。
Leetcode刷题攻略已上传到gitee仓库，需要的小伙伴们可以自取：
https://gitee.com/xiaolong-oba/algorithm-and-data-structure

码字不易，感到有收获的小伙伴记得要关注博主一键三连，不要当白嫖怪哦~
如果大家有什么意见和建议请评论区留言或私聊博主，博主会第一时间反馈的哦。