哈希表（极速学习版）

哈希表的定义与实现

概述

哈希表是一种高效的数据结构，它提供了快速的数据插入、删除和查找操作。

通过使用哈希函数，哈希表将输入的键映射到一个指定位置（索引）以快速访问存储在该位置的值。

哈希表通常用于实现字典、集合、数据库索引等功能。

关键概念：

1. 哈希函数（Hash Function）：将任意大小的输入（键）通过某种算法转换为固定大小输出（哈希值）的函数。理想的哈希函数应具有确定性、均匀分布和快速计算的特性。

   一个简单的哈希函数可以是对键取模数组长度：

int hashFunction(int key, int arraySize) {
    return key % arraySize;
}

2. 哈希值（Hash Value）：哈希函数的输出，用于确定键在哈希表中的存储位置。

3. 冲突（Collision）：当两个不同的键映射到同一哈希值时发生冲突。

4. 冲突解决策略：解决键冲突的方法。常见策略包括：

   • 链地址法（Chaining）：每个哈希值对应一个链表，冲突的键存储在同一链表中。
   • 开放寻址法（Open Addressing）：冲突时寻找表中的下一个空闲位置。
   • 双重哈希（Double Hashing）：使用第二个哈希函数来确定下一个探查位置。

哈希表的冲突解决方法

1. 链地址法 (Chaining)
   • 描述：在这种方法中，每个哈希表的桶（或槽）保存一个链表。每当发生冲突时，新的键值对就会被附加到对应桶的链表中。这意味着同一个哈希值的多个元素可以存在于同一个链表中。
   • 优点：
     • 动态扩展能力强，因为链表可以根据需要增加节点，理论上不受负载因子的限制。
     • 实现相对简单。
   • 缺点：
     • 在极端情况下（如所有键都哈希到同一位置），性能会下降到 O(n)。
     • 需要额外的指针空间来存储链表。

import java.util.LinkedList;

class HashTableChaining {
    private LinkedList<Node>[] table;
    private int size;

    class Node {
        String key;
        String value;

        Node(String key, String value) {
            this.key = key;
            this.value = value;
        }
    }

    // 初始化哈希表
    public HashTableChaining(int size) {
        this.size = size;
        table = new LinkedList[size];
        for (int i = 0; i < size; i++) {
            table[i] = new LinkedList<>();
        }
    }

    // 哈希函数
    private int hash(String key) {
        return key.hashCode() % size;
    }

    // 插入元素
    public void put(String key, String value) {
        int index = hash(key);
        LinkedList<Node> list = table[index];

        // 更新已存在的键
        for (Node node : list) {
            if (node.key.equals(key)) {
                node.value = value;
                return;
            }
        }

        // 插入新节点
        list.add(new Node(key, value));
    }

    // 获取元素
    public String get(String key) {
        int index = hash(key);
        LinkedList<Node> list = table[index];

        for (Node node : list) {
            if (node.key.equals(key)) {
                return node.value;
            }
        }
        return null; // 未找到
    }
}

2. 开放寻址法 (Open Addressing)
   • 描述：与链地址法不同，这种方法在发生冲突时，通过特定探查策略（如线性探查、平方探查等）找到哈希表中的下一个空位来存储新的键值对。
   • 探查方式：
     • 线性探查：每次冲突时，检查下一个位置（i+1、i+2等）直到找到空位。
     • 平方探查：探查位置是基于冲突发生次数的平方，比如 i^2。
   • 优点：
     • 避免了额外存储链表的开销，存储更加紧凑。
     • 不需要额外的指针或链表结构。
   • 缺点：
     • 随着负载因子的增加，查找、插入和删除的性能会明显下降，可能达到 O(n)。
     • 一旦表格接近满，聚集现象会增加查找冲突的概率。

class HashTableOpenAddressing {
    private String[] table;
    private int size;

    // 初始化哈希表
    public HashTableOpenAddressing(int size) {
        this.size = size;
        table = new String[size];
    }

    // 哈希函数
    private int hash(String key) {
        return key.hashCode() % size;
    }

    // 插入元素
    public void put(String key) {
        int index = hash(key);
        while (table[index] != null) {
            index = (index + 1) % size; // 线性探查
        }
        table[index] = key; // 当前位置为空，插入
    }

    // 获取元素
    public String get(String key) {
        int index = hash(key);
        int initialIndex = index;
        while (table[index] != null) {
            if (table[index].equals(key)) {
                return table[index];
            }
            index = (index + 1) % size; // 继续探查
            if (index == initialIndex) break; // 回到起始位置，表已循环
        }
        return null; // 未找到
    }
}

3. 双重哈希 (Double Hashing)
   • 描述：这是开放寻址法的扩展，使用第二个哈希函数来计算步长，以确定下一个探查位置。即在第一次冲突后，使用第二个哈希函数计算步长。
   • 公式：设 h1(k) 和 h2(k) 是两个哈希函数，则探查序列为 h(k, i) = (h1(k) + i * h2(k)) % m，其中 m 是哈希表的大小，i 是探查次数。
   • 优点：
     • 能有效减少聚集现象，提高性能，特别是在负载因子较高时。
     • 可以使用多个哈希函数对同一个键进行查找。
   • 缺点：
     • 实现相对复杂，需要管理两个哈希函数。
     • 如果选择的哈希函数不好，依然可能导致性能下降。

class HashTableDoubleHashing {
    private String[] table;
    private int size;

    // 初始化哈希表
    public HashTableDoubleHashing(int size) {
        this.size = size;
        table = new String[size];
    }

    // 第一个哈希函数
    private int hash1(String key) {
        return key.hashCode() % size;
    }

    // 第二个哈希函数
    private int hash2(String key) {
        return 1 + (key.hashCode() % (size - 1)); // 确保不为零
    }

    // 插入元素
    public void put(String key) {
        int index = hash1(key);
        int stepSize = hash2(key);

        while (table[index] != null) {
            index = (index + stepSize) % size; // 双重哈希
        }
        table[index] = key; // 当前位置为空，插入
    }

    // 获取元素
    public String get(String key) {
        int index = hash1(key);
        int stepSize = hash2(key);
        int initialIndex = index;

        while (table[index] != null) {
            if (table[index].equals(key)) {
                return table[index];
            }
            index = (index + stepSize) % size; // 继续探查
            if (index == initialIndex) break; // 回到起始位置，表已循环
        }
        return null; // 未找到
    }
}

性能分析

• 时间复杂度：

  • 最优情况下（无碰撞）：O(1)（插入、查找、删除）
  • 最坏情况下（所有元素都散列到同一索引）：O(n)，其中 n 是元素数量。

• 空间复杂度： O(n)，用于存储 n 个元素。

数学过程

1. 选择或设计哈希函数：根据键的特性选择或设计合适的哈希函数。
   例如，对于整数键，可以直接使用键值作为哈希值；
   对于字符串键，可以使用某种算法（如除留余数法、折叠法、乘法哈希等）来计算哈希值。

2. 计算哈希值：对于给定的键，使用哈希函数计算其哈希值。例如，对于字符串键 “Kimi”，简单的哈希函数可以是：
   $$H(K)=\sum _{i=1}^n{K}_i\times p^{i-1}\mathrm{mod}m$$
   其中，$K_i$ 是字符串中的第 $i$个字符的 ASCII 值，$p$ 是一个质数（如 31），$m$ 是哈希表的大小。

设计哈希函数

1. 留余数法（Modulus Method）

定义： 留余数法是最简单的哈希函数之一，直接利用模运算将输入映射到数组索引。

公式：
$\text{index}=\text{key}\mathrm{mod}\text{array\_size}$

特点：

• 简单易懂： 实现起来非常简单，计算速度快。
• 适用性： 适用于整数类型的键。

示例代码：

int hashFunction(int key, int arraySize) {
    return key % arraySize;
}

优点：

• 实现简单。
• 可以快速得出索引。

缺点：

• 散列性能依赖于 array_size 的选择。如果大小不是质数，可能会导致较多的碰撞。

2. 折叠法（Folding Method）

定义： 折叠法将键划分为几个部分，然后通过对这些部分进行求和（或其他操作）来生成哈希值。这种方法适合较长的键（如字符串或复合数据）。

实现步骤：

1. 将键分成若干个部分（常常是相等长度的子串）。
2. 将这些部分转化为整数值。
3. 将所有整数值相加（或其他组合），然后取模得到数组索引。

示例：
假设有一个字符串键 “12345678”：

• 分为 “123”、“456” 和 “78”。
• 将其各部分转化为整数并求和。
• 最后对数组大小取模得到索引。

优点：

• 可以有效处理长键。
• 更均匀地分布哈希值，减少碰撞。

缺点：

• 实现较复杂，可能需要处理更多的字符串操作。

3. 乘法哈希（Multiplicative Hashing）

定义： 乘法哈希利用乘法运算来生成哈希值，这种方法也可以适用于任何类型的键。它涉及将键乘以一个常数，然后取哈希值的特定部分。

实现步骤：

1. 选择一个常数 ( A )(通常是大于 0 但小于 1 的正数)。
2. 计算哈希值：
   $h(k)=\lfloor \text{m}\cdot (k\cdot A\mathrm{mod}1)\rfloor$
   其中 $\text{m}$ 是哈希表的大小。

示例代码：

int multiplicativeHash(int key, int arraySize) {
    double A = (Math.sqrt(5) - 1) / 2;  // 常数
    return (int) (arraySize * ((key * A) % 1));
}

优点：

• 更加均匀地分布哈希值，从而减少碰撞。
• 适用于整数和字符串等不同类型的键。

缺点：

• 相对实现更加复杂。
• 需要选择合适的常数$A$ 。

总结

• 留余数法：简单易用，适合整数，但对数组大小选择敏感。
• 折叠法：适合处理长键，具有较好的分布性，但实现较复杂。
• 乘法哈希：能够生成更均匀的哈希值，适用性广，但实现相对复杂。

哈希表动态调整

为什么需要动态调整

在使用哈希表时，随着数据的插入或删除，哈希表的负载因子（即表中元素数量与数组长度的比例）可能会变化。

当负载因子过高时，表会过于拥挤，导致冲突的增加，进而影响查找、插入和删除操作的效率。为了保持哈希表的性能，通常会在以下情况下进行动态调整：

• 扩展（Resize Up）：当负载因子超过某个阈值时（如 0.7），为了减少冲突，哈希表会扩展到一个更大的数组。
• 缩减（Resize Down）：当负载因子低于某个阈值时（如 0.2），为了节省空间，哈希表会缩减到一个更小的数组。

动态调整的过程

1. 确定新大小：计算新哈希表的大小，通常是当前大小的两倍或减半。
2. 创建新数组：初始化一个新的数组，大小为新计算的大小。
3. 重新哈希：将原数组中的每个元素重新映射到新数组中，使用新的哈希函数（通常是相同的哈希函数，因为元素的数量变化了）。
   • 遍历原数组中的每一个元素，计算其新的哈希值，并插入到新数组中。由于数组大小改变，可能会导致哈希值的计算方式改变，因此每个元素需要重新计算其位置。
4. 替换旧数组：将旧的哈希表数组替换为新的数组，并更新相应的控制变量（如当前大小、负载因子等）。

动态调整的复杂度

• 扩展和缩减操作：在哈希表动态调整时，重新哈希的时间复杂度为 O(n)，其中 n 是当前哈希表中的元素数量，因为每个元素都需要重新计算其位置。
• 插入/删除操作：在平均情况下，插入和删除操作的时间复杂度为 O(1)，但在动态调整时，会变为 O(n)，所以动态调整的代价可能会影响到性能。

示例

import java.util.Arrays;

public class HashTable {
    private int size; // 哈希表的大小
    private int count; // 当前存储的键值对数量
    private Entry[] table; // 存储键值对的数组

    // 内部类表示一个键值对
    private static class Entry {
        String key; // 存储的键
        Object value; // 存储的值

        Entry(String key, Object value) {
            this.key = key;
            this.value = value;
        }
    }

    // 构造函数，初始化哈希表，指定初始大小
    public HashTable(int initialSize) {
        this.size = initialSize; // 设置初始大小
        this.count = 0; // 初始化计数为0
        this.table = new Entry[size]; // 创建存储数组
    }

    // 默认构造函数，设置默认大小为8
    public HashTable() {
        this(8);
    }

    // 计算哈希值
    private int hash(String key) {
        return Math.abs(key.hashCode() % size); // 使用 hashCode 的绝对值与当前大小求余
    }

    // 插入键值对
    public void insert(String key, Object value) {
        // 检查负载因子（load factor），如果超出0.7则扩展哈希表
        if ((double) count / size > 0.7) {
            resize(size * 2); // 将哈希表大小扩大至两倍
        }

        int index = hash(key); // 计算哈希值得到索引
        while (table[index] != null) { // 线性探测冲突
            index = (index + 1) % size; // 在当前位置已被占用，检查下一个位置
        }
        table[index] = new Entry(key, value); // 将键值对插入
        count++; // 增加当前计数
    }

    // 扩展哈希表大小，并重新插入项
    private void resize(int newSize) {
        Entry[] oldTable = table; // 保存旧的哈希表
        size = newSize; // 设置新的大小
        table = new Entry[newSize]; // 创建新的哈希表
        count = 0; // 重置计数

        // 将旧哈希表中的所有项重新插入新表
        for (Entry entry : oldTable) {
            if (entry != null) {
                insert(entry.key, entry.value); // 重新插入
            }
        }
    }

    // 根据键获取值
    public Object get(String key) {
        int index = hash(key); // 计算哈希值
        while (table[index] != null) { // 线性探测查找
            if (table[index].key.equals(key)) { // 找到对应的键
                return table[index].value; // 返回值
            }
            index = (index + 1) % size; // 检查下一个位置
        }
        return null; // 未找到
    }

    // 主方法，测试哈希表功能
    public static void main(String[] args) {
        HashTable hashTable = new HashTable(); // 创建哈希表实例
        hashTable.insert("key1", "value1"); // 插入键值对
        hashTable.insert("key2", "value2"); // 插入键值对

        // 测试获取功能
        System.out.println("Get key1: " + hashTable.get("key1")); // 输出: value1
        System.out.println("Get key2: " + hashTable.get("key2")); // 输出: value2
        System.out.println("Get key3: " + hashTable.get("key3")); // 输出: null
    }
}

使用场景

哈希表适合以下情况：

• 需要快速查找数据的场合，如缓存、字典。
• 处理大量唯一数据，如用户标识、商品编号。
• 需要快速统计频次，如单词频率统计。

实际应用案例：任务管理器

在开发一个任务管理器应用时，哈希表（如 HashMap）可以用于高效管理任务。在该应用中，用户可以添加、更新和删除任务，并能够快速查找特定任务。任务信息包括任务ID、名称、优先级、截止日期等。

具体实现

1. 数据结构选择：使用 HashMap 存储任务。键为任务ID，值为任务对象，包含所有相关信息。

2. 操作示例：

   • 添加任务：

     HashMap<Integer, Task> taskMap = new HashMap<>();
     Task newTask = new Task(1, "完成报告", "高", "2024-11-30");
     taskMap.put(newTask.getId(), newTask);
     

   • 查找任务：

     Task taskToFind = taskMap.get(1); // O(1) 时间复杂度
     if (taskToFind != null) {
         System.out.println("找到任务: " + taskToFind.getName());
     }
     

   • 更新任务：

     if (taskMap.containsKey(1)) {
         Task taskToUpdate = taskMap.get(1);
         taskToUpdate.setPriority("中");
     }
     

3. 优势分析：

   • 快速查找：使用哈希表后，查找响应速度显著提升，平均响应时间从几十毫秒降低到几毫秒，用户体验大幅改善。
   • 简洁的代码：清晰的代码结构使得任务的增删改查逻辑更加易于维护。