CS 61B 哈希表

---

笔记的来源：CS 61B-2024 春季的课程 课程主要内容：数据结构与算法分析 课程运用语言：Java

你可以在我的笔记网站里获得更多有用的资源。

这个课有6 个 Homework，10 个 Lab，9 个 Project。其中第一个 project 是一个完整的 2024 游戏的实现，很有意思。此文章对应的是课程 19,20 节的内容。主要讲述 红黑旋转术的数据结构

此笔记对应资源：CS 61B 课本资源

1. 哈希算法简介：数据索引数组

1.1. DataIndexIntegerSet

这个想法是这样的，让一个很大的数组存储每一个位置上的 boolean 值：

public class DataIndexedIntegerSet {
    private boolean[] present;

    public DataIndexedIntegerSet() {
        present = new boolean[2000000000];
    }

    public void add(int x) {
        present[i] = true;
    }

    public boolean contains(int x) {
        return present[i];
    }
}

这样我们就能直接查询到一个位置上是否有值了。 接下我们慢慢改进这个方法，我们会处理字符串等数据形式。

1.2. DataIndexStringSet

大概意思就是，我们插入一个单词的时候，希望给每个字符串赋予一个数字。 那么这个数字怎么制定呢？我们可以用 26 进制类似的方式，比如： 我们想插入一个单词“cat”，我们可以插入的数字为：

$"cat"=3*26^2 + 1*26^1 + 20*26^0$

这个方法类似十进制可以给每一个单词赋予唯一对应的数字。 那么扩展到更多的字符串的话，我们可以用对应字符的 ASCII 码作为底数，但是这样会到值数字计算出来太大，带指数的肯定没啥好事。

2. HashCode

所以我们可以利用 hashcode 的方法。 Java 中的 String 类就有这样的方法：

public class String {
    public int hashCode(String s) {
        ...
    }
}

这个函数可以解决问题。

3.总结

我看到这里的时候大概有些概念了。我重新整理一下：

这个哈希表的数据结构就是预先准备好一张表，然后每一个位置都有一个索引，所有元素都可以找到对应的索引，哈希表主要解决的是防止表格的位置太多超出 java 的最大数字范围的问题。他的解决方法是利用余数，就是到头了就从来。

然后有一个负载因子用来评估这个表的性能，这节课里的因子算法就是用总元素数除以坑位。超过了 1.5 就不太好。但是就怕全站一个坑位，不知道会如何解决。只要比较均匀的分布的话，运行时间就差不多是 O(1) 。比红黑数啥的都好。