CS61B 课程笔记（Lecture 23 Hashing)

哈希基础

哈希代码

  • 定义：哈希代码是用于确定哈希表中索引的值。

  • 计算方法：在Java中，可以使用以下代码计算哈希表的索引：

    1
    int index = Math.floorMod(key.hashCode(), array.length);
    • 这里array是表示哈希表的底层数组。
    • 说明：
      • Math.floorMod函数用于计算模，并能够正确处理负整数。
      • %运算符在处理负数时可能会得到负结果，这可能导致索引错误。

有效哈希码的定义

有效哈希码的两个属性

  1. 确定性：

    • 当两个对象A和B相等（A.equals(B) == true）时，它们的哈希码必须相同。这意味着哈希函数不能依赖于equals方法中未反映的属性。

    • 代码示例：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      @Override
      public boolean equals(Object obj) {
          if (this == obj) return true;
          if (!(obj instanceof MyObject)) return false;
          MyObject other = (MyObject) obj;
          return this.field.equals(other.field);
      }

      @Override
      public int hashCode() {
          return field.hashCode(); // 确保与equals一致
      }

  2. 一致性：

    • 哈希码函数每次调用同一对象实例时必须返回相同的整数。哈希码函数应独立于时间、随机数生成器等因素。

    • 代码示例：

      1
      2
      MyObject obj = new MyObject("example");
      System.out.println(obj.hashCode()); // 每次调用应返回相同值

良好哈希码的特性

良好哈希码的属性

  • 哈希码必须有效。

  • 哈希码的值应均匀分布在所有整数集上，以减少冲突。

  • 哈希码计算应快速，理想情况下为O(1)常数时间复杂度。

  • 实现示例：

    1
    2
    3
    4
    @Override
    public int hashCode() {
        return 31 * field1.hashCode() + field2.hashCode(); // 示例的良好哈希实现
    }

处理冲突：线性探测与外部链接

冲突

  • 当多个元素在数组中具有相同的索引时发生冲突。

两种常见的处理冲突的方法

  1. 线性探测：

    • 将冲突的键存储在数组的下一个空位中。

    • 代码示例：

      1
      2
      3
      4
      5
      6
      7
      public void put(K key, V value) {
          int index = Math.floorMod(key.hashCode(), array.length);
          while (array[index] != null) { // 找到下一个空位
              index = (index + 1) % array.length;
          }
          array[index] = new Entry<>(key, value);
      }

  2. 外部链接：

    • 将所有具有相同哈希值的键存储在一个集合中，如链表。这样的集合称为“桶”。

    • 代码示例：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      class Bucket {
          List<Entry<K, V>> entries = new LinkedList<>();
      }

      public void put(K key, V value) {
          int index = Math.floorMod(key.hashCode(), array.length);
          Bucket bucket = array[index];
          if (bucket == null) {
              bucket = new Bucket();
              array[index] = bucket;
          }
          bucket.entries.add(new Entry<>(key, value)); // 添加到链表中
      }

哈希表的调整与性能

扩展哈希表

  • 如果哈希表的底层数组较小且插入许多键，会导致更多冲突，因此应在达到一定负载因子时扩展数组。
  • 负载因子：插入的元素数量与数组总长度的比率。

重要方程

  • 定义最大负载因子。如果插入后负载因子超出最大值，哈希表应调整大小，通常是将数组长度加倍。

  • 代码示例：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    public void put(K key, V value) {
        if (loadFactor() > MAX_LOAD_FACTOR) {
            resize(); // 调整大小
        }
        // 插入逻辑
    }

    private void resize() {
        // 复制旧数组到新数组
        // 调整哈希值并重新插入
    }

示例

  • 假设哈希表的数组长度为10，当前包含7个元素，负载因子为0.7。插入另一个元素后，负载因子将达到0.8，超出最大负载因子，因此需要将数组长度调整为20。

总结

  • 本章介绍了哈希的强大技术，如何将复杂对象（如字符串）转化为数值（如整数）。
  • 哈希表结合了哈希函数和常数时间索引的数组特性，构建HashMap允许以摊销常数时间访问任何键值对。
  • 本实现的缺点包括表示不同对象的能力、内存效率和冲突问题。
  • 讨论了哈希码函数的重要性及其对哈希表运行时的影响，以及如何通过外部链接解决冲突，探索了基于负载因子的动态调整功能。