喜欢该类型文章可以给博主点个关注，博主会持续输出此类型的文章，知识点很全面，再加上LeetCode的真题练习，每一个LeetCode题解我都写了详细注释，比较适合新手入门数据结构与算法，后续也会更新进阶的文章。
课件参考—开课吧《门徒计划》

4-2 哈希表与布隆过滤器

哈希表基础知识

$func(key)=value$

下标为 $0-8$，假设要存的值 $val=16$，那么怎么能将它不越界的存到这几个下标中呢？我们可以进行取余操作，$16\%9=7$：

可以把哈希表理解为升级版的数组，哈希表不单单可以存储数字，它的下标可以是任意类型，最终对应的值也可以是任意类型。

Map<String, Integer> map = new HashMap<>(); // key => value

哈希函数

哈希函数是一个很随意化的东西，你只要能把传入的任意字符换换成对应的数字 它就可以作为哈希函数。

• 计算出来的值一定是正数（作为下标）
• $key1=key2$ => $hash1=hash2$
• $key1\ne key2$ => $hash1\ne hash2$（目前所有的哈希函数都无法实现，因为会存在哈希冲突，而我们需要学习怎么解决哈希冲突）

查找效率为 $O(1)$。

哈希冲突

此时还要存一个值 $7$，那么 $7\%9=7$，此时会跟 $16$ 存到同样的位置，造成了哈希冲突：

哈希冲突处理方法

1. 开放定址法（线性探测法）

最粗暴最简单的方法，假设当前下标已经有了元素，那么直接将它存入该下标的下一个位置，假如下一个位置也有元素，那么再继续往下，直到找到某个下标位置为空：

但是如果这个哈希表中的元素已经很多了，那么每次查找就不可能是 $O(1)$ 了，最坏情况下会退化成 $O(N)$。

我们可以试着增加步长，以指数的方式增加下标：

开放定址法也存在着缺点，假设通过开放定址法存入三个 $7$，那么下标位置肯定会依次存放在 $7、8、9$，但如果我们把下标为 $8$ 对应的元素删除，那么此时会找不到下标为 $9$ 的元素，因为当 $8$ 这个位置没有元素，会误认为这个哈希表中并未出现过哈希冲突，所以就不会再往下遍历，遍历不到下标为 $9$ 的位置。

如何解决？可以在已删除元素的下标添加一个 $deleted$ 标记，表明这个下标位置的元素被删除过。

开放定址法局限性比较大。

但如果数据量小，存储元素的字节较小，开放定址法是一个不错的选择。

开放定址法代码实现

/*
  开放定址法
 */
public class Hash1 {
    public static void main(String[] args) {
        int op;
        String s; // 数字跟字符串做映射
        HashTable h = new HashTable(100);
        Scanner sc = new Scanner(System.in);
        while (true) {
            op = sc.nextInt();
            s = sc.next();
            switch (op) {
                case 1: 
                    h.insert(s); break;
                case 2:
                    System.out.println("find " + s + " : " + h.find(s));
            }
        }
    }
}

class HashTable {

    int cnt;
    String[] data;
    boolean[] flags;

    public HashTable(int n) {
        data = new String[n];
        flags = new boolean[n];
        cnt = 0;
    }

    public void insert(String s) {
        int ind = hash_func(s) % data.length; // get hash code
        recalc_ind(ind, s); // 如果出现冲突 重新计算下标 使用线性探测法
        if (!flags[ind]) {
            data[ind] = s;
            flags[ind] = true;
            cnt++;
            if (cnt * 100 > data.length * 75) { // 如果存的值大于75% 则进行扩容
                expand(); // 扩容函数
            }
        }
    }

    private void expand() {
        // 如何处理哈希搬运(从旧数组搬运到扩容的新数组中) 同样也是redis主键实现的方式
        /*
          当整个哈希函数需要扩容时 我们先把扩容的新数组创建出来
          当有insert操作时 直接插入到新数组中 当有find操作时 先从小(旧)数组中找
          如果找到 则将小数组的值拷贝到新数组中 再把小数组找到的值删掉 以此类推 小数组中的元素会越来越少 最后小数组会逐渐消失
          相当于延迟操作的效果 对于整个程序 把集中式的密集计算 变为了时间长度跨越较大的 离散式的计算 减少负载
         */
        int n = data.length * 2; // 扩容2倍
        HashTable h = new HashTable(n);
        for (int i = 0; i < data.length; i++) {
            if (!flags[i]) continue;
            h.insert(data[i]);
        }
    }

    public boolean find(String s) {
        int ind = hash_func(s) % data.length; // get hash code
        recalc_ind(ind, s); // 如果出现冲突 重新计算下标 使用线性探测法
        return flags[ind];
    }

    // 把传入的字符串转换成数字
    private int hash_func(String s) {
        int seed = 131, hash = 0;
        for (int i = 0; i < s.length(); i++) {
             /*
               比较常见的字符串哈希
               我们乘的这个seed:131可以不是一个固定值 只要是一个素数就可以
               使用哈希函数 每次迭代都乘上一个素数 那么最终算出来的值 很大的概率是平均的（数学公式推导证明出来的）
             */
            hash = hash * seed + s.charAt(i);
        }
        return hash & 0x7fffffff; // 保证哈希值一定是正数
    }

    // 重新计算 处理冲突 线性探测法
    private void recalc_ind(int ind, String s) {
        int t = 1;
        while (flags[ind] && !data[ind].equals(s)) {
            ind += t * t; // 指数倍递增
            t++;
            ind %= data.length;
        }
    }
}

2. 再哈希法

顾名思义，一个哈希函数可能会造成哈希冲突，那么我们用一组哈希函数 来避免冲突：

但其实再哈希法局限性更大，可能一组哈希函数还是会造成冲突。

再哈希法单独拿出来没什么用，需要跟布隆过滤器结合一起使用。

3. 建立公共溢出区

之前我们的 $16$ 和 $7$ 出现了冲突，这时我们可以开辟一个溢出缓冲区，把冲突的数字丢进去，再查找 先在哈希数组中找，找不到再从缓冲区中找：

这个缓冲区可以是任意一种合适的数据结构：堆、红黑树、B树、链表（就是下面的拉链法）等。

建立公共溢出区代码实现

/*
  建立公共溢出区
 */
public class Hash2 {
    public static void main(String[] args) {
        int op;
        String s; // 数字跟字符串做映射
        HashTable h = new HashTable(100);
        Scanner sc = new Scanner(System.in);
        while (true) {
            op = sc.nextInt();
            s = sc.next();
            switch (op) {
                case 1:
                    h.insert(s); break;
                case 2:
                    System.out.println("find " + s + " : " + h.find(s));
            }
        }
    }
}

class HashTable {

    int cnt;
    String[] data;
    boolean[] flags;
    Set<String> buff; // 使用set集合作为缓冲区

    public HashTable(int n) {
        data = new String[n];
        flags = new boolean[n];
        cnt = 0;
    }

    public void insert(String s) {
        int ind = hash_func(s) % data.length; // get hash code
        if (!flags[ind]) {
            data[ind] = s;
            flags[ind] = true;
            cnt++;
            if (cnt * 100 > data.length * 75) { // 如果存的值大于75% 则进行扩容
                expand(); // 扩容函数
            }
        } else if (!data[ind].equals(s)) {
            buff.add(s); // 只要找不到 就放在缓冲区中
        }
    }

    private void expand() {
        // 如何处理哈希搬运(从旧数组搬运到扩容的新数组中) 同样也是redis主键实现的方式
        /*
          当整个哈希函数需要扩容时 我们先把扩容的新数组创建出来
          当有insert操作时 直接插入到新数组中 当有find操作时 先从小(旧)数组中找
          如果找到 则将小数组的值拷贝到新数组中 再把小数组找到的值删掉 以此类推 小数组中的元素会越来越少 最后小数组会逐渐消失
          相当于延迟操作的效果 对于整个程序 把集中式的密集计算 变为了时间长度跨越较大的 离散式的计算 减少负载
         */
        int n = data.length * 2; // 扩容2倍
        HashTable h = new HashTable(n);
        for (int i = 0; i < data.length; i++) {
            if (!flags[i]) continue;
            h.insert(data[i]);
        }
        for (String s : buff) {
            h.insert(s); // 把buff中的所有元素存入新数组中
        }
    }

    public boolean find(String s) {
        int ind = hash_func(s) % data.length; // get hash code
        if (!flags[ind]) return false;
        if (data[ind].equals(s)) return true;
        return buff.contains(s); // 当到了这一行 说明元素肯定存入了缓冲区中
    }

    // 把传入的字符串转换成数字
    private int hash_func(String s) {
        int seed = 131, hash = 0;
        for (int i = 0; i < s.length(); i++) {
             /*
               比较常见的字符串哈希
               我们乘的这个seed:131可以不是一个固定值 只要是一个素数就可以
               使用哈希函数 每次迭代都乘上一个素数 那么最终算出来的值 很大的概率是平均的（数学公式推导证明出来的）
             */
            hash = hash * seed + s.charAt(i);
        }
        return hash & 0x7fffffff; // 保证哈希值一定是正数
    }
}

4. 链式地址法（拉链法）

拉链法是最常见的处理哈希冲突方式。

每一个数组下标存的不是具体的结点值，而是一个链表，哈希值相同的元素统统放到对应数组下标的链表中：

链表有什么缺点，链式地址法就有什么缺点。

HashMap解决哈希冲突使用的就是拉链法

拉链法代码实现

/*
  拉链法
 */
public class Hash3 {
    public static void main(String[] args) {
        int op;
        String s; // 数字跟字符串做映射
        HashTable h = new HashTable(100);
        Scanner sc = new Scanner(System.in);
        while (true) {
            op = sc.nextInt();
            s = sc.next();
            switch (op) {
                case 1:
                    h.insert(s); break;
                case 2:
                    System.out.println("find " + s + " : " + h.find(s));
            }
        }
    }
}

class HashTable {

    int cnt;
    Node[] data;

    public HashTable(int n) {
        data = new Node[n];
        Arrays.fill(data, new Node()); // 初始化
        cnt = 0;
    }

    public void insert(String s) {
        int ind = hash_func(s) % data.length; // get hash code
        Node p = data[ind];
        // 不为空 且每一个节点都不等于s
        while (p.next != null && !p.next.data.equals(s)) p = p.next;
        if (p.next == null) {
            p.insert(new Node(s));
            cnt++;
            if (cnt * 3 > data.length)
                expand();
        }
    }

    private void expand() {
        int n = data.length * 2;
        HashTable h = new HashTable(n);
        for (int i = 0; i < data.length; i++) {
            Node p = data[i].next;
            while (p != null) {
                h.insert(p.data);
                p = p.next;
            }
        }
    }

    public boolean find(String s) {
        int ind = hash_func(s) % data.length; // get hash code
        Node p = data[ind];
        while (p.next != null && !p.next.data.equals(s)) p = p.next;
        return p.next != null; // 找到了则不为空
    }

    // 把传入的字符串转换成数字
    private int hash_func(String s) {
        int seed = 131, hash = 0;
        for (int i = 0; i < s.length(); i++) {
            hash = hash * seed + s.charAt(i);
        }
        return hash & 0x7fffffff;
    }
}

// 链表
class Node {

    String data;
    Node next;

    public Node() {
    }

    public Node(String data) {
        this.data = data;
    }

    public void insert(Node node) {
        node.next = this.next;
        this.next = node;
    }
}

布隆过滤器

只是简单的进行讲解，并无法讲的很彻底，我自认为理解的也不是很好。

布隆过滤器启动后，元素数量是多少就是多少，几乎不会对存储空间进行扩容或缩容。

布隆过滤器是一个跟数学强相关的东西，在设计布隆过滤器时会通过一系列复杂的数学公式，来把传入的数据规模的数量、变化程度通过公式计算后，算出布隆过滤器最终的值，这个值也就是布隆过滤器启动时初始化的值。

假设有一个 $key1$，把这个 $key1$ 同时传入这三个哈希函数中，这三个哈希函数的实现都各有不同，最终算出的值也不同，三个函数映射出三个位置来，把这三个位置都置为 $1$：

采用了布隆冲突器之后，产生冲突的概率就小了很多。

假设此时又传入了一个 $key2$，通过三个哈希函数计算后，结果这三个值跟计算后 $key1$ 的三个值一样，发生了冲突，那怎么办呢？

布隆过滤器没有办法解决冲突。

问题没法解决，那我们就不让这个问题发生，想象一个场景：“过滤器”，布隆过滤器只起到一个作用：过滤。

我只需要知道它对应的值是 $1$ 还是 $0$，从而将它过滤。

布隆过滤器的底层就是二进制的 $bitmap$ 位图，全部由二进制位组成的数组。

当某个 $key$ 通过三个哈希函数计算后的位置，有一个位置是 $0$，则一定不会被过滤，三个位置如果全是 $1$，则有可能被过滤，为了确认这个可能性，我们可以用其他的方式确认一下（在线查询、查询数据库），即使慢一点也没什么关系，毕竟过滤的一定是少数，这些时间损耗都是可以接受得了的。

$布隆过滤器=bitmap+hash\_func()+等一系列策略$

布隆过滤器的应用非常广泛，比如微信小游戏的封禁功能就是使用的布隆过滤器。

LeetCode真题

经典面试题—哈希结构封装

LeetCode705. 设计哈希集合

LeetCode706. 设计哈希映射

经典面试题—哈希结构使用

LeetCode535. TinyURL 的加密与解密

LeetCode187. 重复的DNA序列

LeetCode318. 最大单词长度乘积

LeetCode面试题 16.25. LRU 缓存

NodeList
   ↑
HashList
   ↑
  LRU

总结

其实哈希表这个结构，就是一个升级版的数组，存储的是键值对 $key=>value$，给定一个 $key$，通过哈希函数计算 将 $value$ 放到指定位置，一般哈希表都是用来快速判断一个元素是否出现集合里，实现 $O(1)$ 的查找效率。

了解过java的HashMap就应该知道 HashMap解决哈希冲突就是使用的拉链法，在jdk1.8之后 链表长度超过8会转换为红黑树。

LRU缓存使用的哈希表+链表，在java中也有对应的实现类：LinkedHashMap，我之后也会阅读这个类的源码。