数据结构与算法_06_散列表

本文介绍散列表数据结构，散列表也被称为哈希表（Hashtable）。

1. 散列表理论基础

哈希表可以是单纯的数组，也可以是数组和单向链表的结合体。如果是数组的话，和普通数组的区别在于元素存储位置不是任意的，而是根据哈希算法得出。如果是数组和哈希表的结合体，则是当出现哈希冲突的时候一种解决办法。

前面提到过，数组的优点是查找效率高，链表的优点是随机增删效率高。哈希表则是将二者结合起来，充分发挥了各自的优点。

哈希表首先是一个数组，关键是这个数组中每个元素存储的是一个单向链表头结点的引用。换句话说：哈希表是一维数组，数组中的每个元素是一个单向链表。即哈希表是数组和链表的结合体。

1.1 哈希表介绍

首先哈希表是一个数组，但是和普通的数据有区别，一方面，元素并不是在任意下标存储，而是通过哈希算法得出该元素应该存储的下标位置，当多个元素通过哈希算法得出的元素存储下标的位置相同时，此时称为哈希碰撞。

针对哈希碰撞，该如何解决呢？有拉链法和线性探测法（开放地址法）。拉链法就是将下标位置相同的元素形成链表，链表头结点存储在数组中（这种方法适用于数组空间小于数据规模的时候）。如果数组空间大于数据规模，可以采用线性再探测，将发生冲突的元素存储在数组其他空余空间中。

哈希表可以用来快速判断一个元素是否出现在集合里，根据哈希函数直接获取到下标索引，然后根据下标来取值判断。

1.2 哈希表主要方法

和其他数据结构一样，哈希表最重要的两个方法是存（put）和取（get），Java中的HashMap类中的方法大致的执行过程如下。

1.2.1 put()方法

map.put(k, v)方法原理：

第一步：先将 k,v 封装到Node对象当中。

第二步：底层会调用k的hashCode()方法得出hash值，然后通过哈希函数/哈希算法，将hash值转换成数组的下标，下标位置上如果没有任何元素，就把Node添加到这个位置上了。如果说下标对应的位置上有元素（链表），此时会将k和链表上每一个节点中的k进行equals，如果所有的equals方法返回都是false，表明该节点没有存储在链表中，那么这个新节点将会被添加到链表的末尾，如果其中有一个equals返回了true，此时会将旧节点的value替换为新节点的value（即更新节点值）。

1.2.2 get()方法

map.get(k)方法原理：

第一步：先调用k的hashCode()方法得出哈希值，通过哈希算法转换成数组下标，通过数组下标快速定位到某个位置上（某个链表上），如果这个位置上什么也没有，返回null。如果这个位置上有单向链表，那么会拿着参数k和单向链表上的每个节点中的k进行equals，如果所有equals方法返回false，那么get方法返回null；如果其中有一个节点的k和参数k equals的时候返回true，那么此时这个节点的value就是我们要找的value，get方法最终返回这个要找的value。

通过这两个方法可以看出：

从链表的角度来看，结合数组和哈希算法，一定程度上减少了扫描范围，使得检索效率有了一定的提升，即根据哈希算法可以直接定位到某一条子链表中。

从数组的角度来看，结合链表和哈希算法，一定程度上减少了元素的移动，使得随机增删效率有了一定的提升，即根据哈希值计算出节点所在的链表后，在链表上进行元素的增删。

所以哈希表的随机增删和查询效率都很高。因为增删是在链表上完成，查询由数组缩小了扫描范围。相当于是数组和链表的折中，在增删和查询之间做了均衡。

1.3 哈希表实现

1.3.1 哈希表简单实现

不知道具体的哈希算法都有哪些，所以参考了网上的例子，参考链接。直接以拉链法形式实现哈希表，对于线性再探测就不考虑了，采用的哈希算法具体思路如下：

将字符串中每个字符对应的ASCII值相加，并对数组长度取余。

本实例规定了哈希表中存储的元素类型为自定义元素类型，自定义元素类型代码如下所示：

// 创建要存储的数据类型
class Person{
    private String key;
    private String value;
    private Person next;

    public Person(){}

    public Person(String key, String value){
        this.key = key;
        this.value = value;
        this.next = null;
    }

    public void setKey(String key){
        this.key = key;
    }

    public void setValue(String value){
        this.value = value;
    }

    public void setNext(Person p){
        this.next = p;
    }

    public String getKey(){
        return this.key;
    }

    public String getValue(){
        return this.value;
    }

    public Person getNext(){
        return this.next;
    }

    public String toString(){
        return this.key + "-->" + this.value;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return Objects.equals(key, person.key) &&
                Objects.equals(value, person.value);
    }

    @Override
    public int hashCode() {
        return Objects.hash(key, value);
    }
}

为了测试哈希函数，暂时先不考虑哈希碰撞之后的拉链行为。哈希表实现代码如下所示：

class HashTable{

    private Person[] arrays;

    public HashTable(){
        this(10);
    }

    public HashTable(int size){
        this.arrays = new Person[size];
    }

    public void insert(Person p){
        // 先不考虑拉链，只是基本情况，看是否覆盖。
        this.arrays[this.hashCodeBySelf(p.getKey())] = p;
    }

    public Person find(String key){
        // 先不考虑拉链
        return this.arrays[hashCodeBySelf(key)];
    }

    private int hashCodeBySelf(String key){
        char[] keys = key.toCharArray();
        int asciiSum = 0;
        for (char c : keys) {
            asciiSum += c - 97;
        }

        return asciiSum % this.arrays.length;
    }

    public void print(){
        // 不考虑拉链情况
        for (Person p: arrays) {
            System.out.println(p);
        }
    }
}

测试代码和结果如下所示，可以看到确实发生了覆盖：

public class CustomizeHashTable {

    public static void main(String[] args) {

        HashTable ht = new HashTable(5);

        ht.insert(new Person("a", "zhangSan"));
        ht.insert(new Person("g", "liSan"));
        ht.insert(new Person("l", "wangSan"));
        ht.insert(new Person("h", "zhaoSan"));
        ht.insert(new Person("c", "liuSan"));

        System.out.println(ht.find("g"));

        ht.print();
    }
}

// 结果如下所示：
l-->wangSan
a-->zhangSan
l-->wangSan
c-->liuSan
null
null

此时开始考虑拉链，当数组下标位置已经存储元素的时候，就遍历该链表，直到更新值或者新增节点。哈希表实现代码（只有inset、find、print三个方法改变了）如下所示：

public void insert(Person p){
    // 先不考虑拉链，只是基本情况，看是否覆盖。
    // this.arrays[this.hashCodeBySelf(p.getKey())] = p;
    int index = this.hashCodeBySelf(p.getKey());
    if(null != this.arrays[index]){
        // 说明该位置上已经存储了，此时需要遍历链
        Person temp = this.arrays[index];
        while(temp.getNext() != null){
            if(!temp.getKey().equals(p.getKey())){
                temp = temp.getNext();
            }else{
                temp.setValue(p.getValue());
                return;
            }
        }

        // 此时只剩最后一个节点未判断
        if(!temp.getKey().equals(p.getKey())){
            temp.setNext(p);
        }else{
            temp.setValue(p.getValue());
            return;
        }

        return;
    }

    this.arrays[this.hashCodeBySelf(p.getKey())] = p;
}

public Person find(String key){
    int index = this.hashCodeBySelf(key);

    if(this.arrays[index] == null){
        return null;
    }

    Person temp = this.arrays[index];

    while(temp.getNext() != null){
        if(temp.getKey().equals(key)){
            return temp;
        }
        temp = temp.getNext();
    }

    if(temp.getKey().equals(key)){
        return temp;
    }

    return null;
}

public void print(){

    Person p = null;

    for (Person array : arrays) {
        p = array;

        if (p == null) {
            System.out.println(p);
            continue;
        }

        if (p.getNext() == null) {
            System.out.println(p);
            continue;
        }

        while (p.getNext() != null) {
            System.out.print(p + " ~~~ ");
            p = p.getNext();
        }
        System.out.println(p);
    }
}

测试代码如下所示：

public class CustomizeHashTable {

    public static void main(String[] args) {

        HashTable ht = new HashTable(5);

        ht.insert(new Person("a", "zhangSan"));
        ht.insert(new Person("g", "liSan"));
        ht.insert(new Person("l", "wangSan"));
        ht.insert(new Person("h", "zhaoSan"));
        ht.insert(new Person("c", "liuSan"));

        System.out.println(ht.find("g"));

        ht.print();

        System.out.println("--------------");

        // 测试覆盖值
        ht.insert(new Person("c", "zhaoLiu"));

        ht.print();

        System.out.println("--------------");

        // 测试一下取值
        System.out.println(ht.find("b"));
        System.out.println(ht.find("a"));
    }
}

1.3.2 Java提供的哈希表

Java中的java.util.HashMap和java.util.HashSet提供了两种底层是哈希表的实现类。

2. 散列表经典题目

2.1 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1: 输入: s = “anagram”, t = “nagaram” 输出: true

示例 2: 输入: s = “rat”, t = “car” 输出: false

说明: 你可以假设字符串只包含小写字母。

字母异位词指的是，两个字符串的长度相等，且各字母的个数相等，只是顺序不同。可以遍历第一个字符串，统计其字符出现的个数；然后再遍历另一个字符串，统计其字符出现的个数。对比二者的个数是否一样即可。

那么字符的个数怎么存储呢？应该开辟多大的空间呢？ 因为是字母，并且只包含小写字母，所以可以开辟26个长度的数组。在遍历第一个单词的时候，用数组计数，在遍历第二个单词的时候，用数组减数。最后判断数组中是否存在不为0的元素，如果存在则说明两个单词的字符个数不等，不存在则说明二者是字母异位词。

实现代码如下：

public static boolean wordDifferentSame(String word1, String word2){

    if(word1.length() != word2.length()) return false;

    int[] words = new int[26];

    char[] word1s = word1.toCharArray();
    char[] word2s = word2.toCharArray();

    for (char c : word1s) {
        words[c - 97]++;
    }

    for (char c: word2s) {
        words[c - 97]--;
    }

    for (int i: words) {
        if(i != 0) return false;
    }

    return true;
}

2.2 两个数组的交集

给定两个数组，编写一个函数来计算它们的交集。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]

说明：

输出结果中的每个元素一定是唯一的。
我们可以不考虑输出结果的顺序。

这道题很容易想到用Set相关数据类型存储数据。先遍历其中一个数组，将其存储到Set中。再遍历另一个数组，判断第一个Set中是否包含该数组中的元素，如果包含则将其添加到另一个Set中。注意，Set集合contains方法的复杂度远小于O(n)，所以当数据量大的时候，该方法的时间复杂度是小于暴力破解O(n^2)的。

实现代码如下所示：

public static int[] mixByTwo(int[] array1, int[] array2){

    if (array1 == null || array1.length == 0 || array2 == null || array2.length == 0) {
        return new int[0];
    }
    HashSet<Integer> hs1 = new HashSet<>();
    HashSet<Integer> hs2 = new HashSet<>();

    for (int i: array1) {
        hs1.add(i);
    }

    for (int i: array2) {
        if(hs1.contains(i)){
            hs2.add(i);
        }
    }

    int[] result = new int[hs2.size()];
    int index = 0;
    for (Integer i: hs2) {
        result[index] = i;
        index++;
    }

    return result;

}

2.3 快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。

如果 n 是快乐数就返回 True ；不是，则返回 False 。

示例：

输入：19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

这道题的题目和示例其实就给出了解决方法，关键是如何返回false，即如何判断是否是无限循环。可以保存中间结果，如果之后的中间结果和保存的中间结果一样，那么就说明是无限循环。所以可以用Set集合来保存中间结果。

public static boolean happyNumber(int num){

    String numS = String.valueOf(num);
    char[] numC = numS.toCharArray();
    int result = num;
    HashSet<Integer> hs = new HashSet<>();

    while(result != 1){

        hs.add(result);

        result = 0;

        for (char c: numC) {
            result += Math.pow(Integer.parseInt(c + ""), 2);
        }

        if(hs.contains(result)) {
            return false;
        }

        numS = String.valueOf(result);
        numC = numS.toCharArray();
    }

    return true;

}

上述方法中，采用了一种比较笨的方法来取数字的各位位数。其实可以直接求余来做，如下所示：

public static boolean happyNumber2(int num){

    int temp;
    int result = num;
    HashSet<Integer> hs = new HashSet<>();

    while(result != 1){

        hs.add(result);

        result = 0;

        while (num != 0) {
            temp = num % 10;
            num = num / 10;
            result += Math.pow(temp, 2);
        }

        if(hs.contains(result)) return false;

        num = result;

    }

    return true;

}

2.4 两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

>给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

这道题可以先用暴力破解法做一遍，代码如下所示：

public static int[] twoSum(int[] array, int target){

    int[] result = new int[2];
    for (int i = 0; i < array.length; i++) {
        for (int i1 = 0; i1 < array.length; i1++) {
            if(array[i] + array[i1] == target && i != i1){
                result[0] = i;
                result[1] = i1;
                return result;
            }
        }
    }
    return result;
}

那么怎么改进呢？一种方法是可以用Set存储数，然后遍历数组的时候用target减去元素值，并判断结果是否在Set中。这种做法不足是需要找下标，本质上还是O(n^2)。如下所示：

public static int[] twoSum2(int[] array, int target){

    HashSet<Integer> hs = new HashSet<>();
    int[] result = new int[2];

    for (int i = 0; i < array.length; i++) {
        if(hs.contains(array[i]) && target / array[i] == 2){
            // 说明数组中有两个同样的数，并且该两数就是要找的。并且前面出现的数一定是最先出现的。
            result[0] = findIndex(array, array[i]);
            result[1] = i;
            return result;
        }

        hs.add(array[i]);
    }

    // 普通情况，不是相同数字
    for (int i = 0; i < array.length; i++) {
        if(hs.contains(target - array[i])){
            result[0] = i;
            result[1] = findIndex(array, target - array[i]);
            return result;
        }
    }

    return result;
    }

private static int findIndex(int[] array, int key){
    for (int i = 0; i < array.length; i++) {
        if(array[i] == key)
            return i;
    }

    return -1;
}

那么是否可以存储下标呢？可以用HashMap来做。实现代码如下所示：

public static int[] twoSum3(int[] array, int target){

    HashMap<Integer, Integer> hm = new HashMap<>();
    int[] result = new int[2];

    for (int i = 0; i < array.length; i++) {
        if(target / array[i] == 2 && hm.get(array[i]) != null){
            result[0] = hm.get(array[i]);
            result[1] = i;
            return result;
        }

        hm.put(array[i], i);
    }

    // 普通情况，不是相同数字
    for (int i = 0; i < array.length; i++) {
        if(hm.get(target - array[i]) != null){
            result[0] = hm.get(target - array[i]);
            result[1] = i;
            return result;
        }
    }

    return result;
}

能不能再次优化一点呢？实际上没必要全部将数字放入Map中，首先判断差值是否在Map中，如果有则说明该两数就是结果；如果没有，则放入（说明当前数字是第一个因子），后续遍历其他元素的时候一定会找到（当前数字树第二个因子）。实现代码如下所示：

public static int[] twoSum4(int[] array, int target){

    HashMap<Integer, Integer> hm = new HashMap<>();
    int[] result = new int[2];

    // 普通情况，不是相同数字
    for (int i = 0; i < array.length; i++) {
        if(hm.get(target - array[i]) != null){
            result[0] = hm.get(target - array[i]);
            result[1] = i;
            return result;
        }

        hm.put(array[i], i);
    }

    return result;
}

2.5 三数之和

上面的题目是两数之和，那么三数之和该怎么做呢？

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意： 答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]

2.6 四数之和

2.7 四数相加II

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。

为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间，最终结果不会超过 2^31 - 1 。

示例 1：

输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2

解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

示例 2：

输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1

首先题目限制了数字相加不会有溢出的问题。具体有点复杂，没有思路，先用暴力破解法，实现代码如下：

public static int fourSum(int[] array1, int[] array2, int[] array3, int[] array4){

    int resultNum = 0;

    for (int n1 : array1) {
        for (int n2 : array2) {
            for (int n3 : array3) {
                for (int n4 : array4) {
                    if(n1+n2+n3+n4 == 0)
                        resultNum++;
                }
            }
        }
    }

    return resultNum;
}

四个数组具有相同的长度，并且总和为0（必定有正负），能不能从这两点入手呢？

可不可以分组呢，即两个数组分别相加，形成新的两个数组，这两个数组再相加。但是这样做的话，空间开辟似乎有点大，至少要O(n^2)的空间复杂度。

2.8 赎金信

3. 备注

部分参考代码随想录 (programmercarl.com)。