CS61B 课程笔记（Examprep 09 Hashing Exam Prep)

1. 外部链表哈希表 (External Chaining Hash Set) 重新调整大小

在插入元素时，如果哈希表的负载因子（Load Factor）达到某个阈值（如1.5），就会触发扩容。在题目中，负载因子为1.5时触发重新扩展，即从4个桶扩展到8个桶。我们假设插入元素5时会发生重新扩容。

初始哈希表（4个桶）：

0 → 8  
1 → 25  
2 → 10 → 18  
3 →

插入5并触发扩容（扩展到8个桶）：

0 → 8  
1 → 25  
2 → 10 → 18  
3 →  
4 →  
5 → 5  
6 →  
7 → 15

使用默认的 hashCode 方法，整数本身作为哈希值。
插入5后，负载因子为6/8 = 0.75，小于1.5，因此不会再次触发扩容。

2. 哈希表操作的时间复杂度分析

问题描述：

给定一个使用外部链表实现的哈希表，并且记录了键的数量。哈希表的负载因子始终保持小于等于2。假设哈希函数和键的比较操作都是常数时间。求不同情况下添加元素的最坏时间复杂度（以N表示元素数量）。

（1）负载因子为1时的最坏情况时间复杂度

情况：所有元素都在同一个桶中，类似链表，插入时需要遍历整个链表。
时间复杂度：\(\Theta(N)\)

（2）负载因子为2时的最坏情况时间复杂度

情况：在插入元素时发生扩容，扩容需要重新分配并复制元素。
时间复杂度：
- 如果扩容时不检查重复元素，复杂度为 \(\Theta(N)\)（线性扩容）。
- 如果扩容时检查重复元素（如调用 put 方法），最坏情况下为 \(\Theta(N^2)\)。

（3）假设哈希函数非常好，总能均匀分布元素到各个桶中

负载因子为1时的最坏情况时间复杂度：\(\Theta(1)\)，插入操作仅需常数时间。
负载因子为2时的最坏情况时间复杂度：\(\Theta(N)\)，扩容依旧是线性时间。

（4）使用平衡二叉搜索树而不是链表作为桶

假设哈希函数不均匀，所有元素可能都落在同一个桶中，但由于使用了平衡二叉树，查找元素的时间复杂度为 \(\Theta(\log N)\)。

（5）使用好的哈希函数与平衡二叉树

最坏情况时间复杂度：\(\Theta(1)\)，因为元素均匀分布且查找操作为常数时间。

3. 哈希函数的设计问题

以下是几个类的 hashCode 方法的代码分析及其潜在问题：

（1）`DynamicString` 类

class DynamicString {
    ArrayList<Character> vals;
    public int hashCode() {
        int h = 0;
        for (int i = 0; i < vals.size(); i++) {
            h = 31 * h + vals.get(i);
        }
        return h;
    }
    public boolean equals(Object o) {
        DynamicString d = (DynamicString) o;
        return vals.equals(d.vals);
    }
}

问题：没有问题，使用了与 String::hashCode 类似的实现，分布性良好。

（2）`PokeTime` 类

class PokeTime {
    int startTime;
    int duration;
    public int getCurrentTime() {
        // 获取当前系统时间
    }
    public int hashCode() {
        return 1021 * (startTime + 1021 * duration + getCurrentTime());
    }
    public boolean equals(Object o) {
        PokeTime p = (PokeTime) o;
        return p.startTime == startTime && p.duration == duration;
    }
}

问题：无效的哈希函数，使用当前时间导致哈希码不确定性，不能确保相同对象生成相同的哈希码。

（3）`Phonebook` 类

class Phonebook {
    List<Human> humans;
    public int hashCode() {
        int h = 0;
        for (Human human : humans) {
            h = (h + human.hashCode()) % 509;
        }
        return h;
    }
    public boolean equals(Object o) {
        Phonebook p = (Phonebook) o;
        return p.humans.equals(humans);
    }
}

问题：虽然是有效的哈希函数，但由于使用了 mod 509，导致哈希码的取值范围受到限制，可能会影响分布的均匀性。

（4）`Person` 类

class Person {
    Long id;
    String name;
    Integer age;
    public int hashCode() {
        return id.hashCode() + name.hashCode() + age.hashCode();
    }
    public boolean equals(Object o) {
        Person p = (Person) o;
        return p.id == id;
    }
}

问题：无效。两个 Person 对象如果 id 相同但 name 和 age 不同，按照 equals 方法它们被认为是相等的，但哈希码不同，违反了哈希表的规范。

（5）`DblCharSeq` 类

class DblCharSeq {
    char[] seq1;
    char[] seq2;
    public int hashCode() {
        int h = 0;
        for (char c1 : seq1) {
            for (char c2 : seq2) {
                h = 31 * (31 * h + c1) + c2;
            }
        }
        return h;
    }
    public boolean equals(Object o) {
        DblCharSeq d = (DblCharSeq) o;
        return Arrays.equals(seq1, d.seq1) && Arrays.equals(seq2, d.seq2);
    }
}