算法学习——哈希表（理论基础）
目录
一、认识哈希表
1. 哈希表的定义
哈希表（Hash Table）是一种通过键（Key）快速访问值（Value）的数据结构，核心思想是通过关于键值的函数，将所需查询的数据映射到存储位置。这个映射函数叫做哈希函数，存放记录的数组叫做哈希表。
2. 哈希表的优缺点
- 优点：
-
数据访问高效：在理想情况下，由于哈希函数能够快速将键映射到对应的数组索引，哈希表的插入、查找和删除操作平均时间复杂度均为 O(1)。
-
容易实现：哈希表的基本原理和实现方式相对直观，通过简单的数组和哈希函数就能构建出基础的哈希表结构。
- 数据存储灵活：哈希表支持各种类型的键值对存储。
- 缺点：
-
哈希冲突问题：由于哈希函数的定义域通常远大于值域，不同的键值可能会被映射到哈希表的同一个索引位置，从而产生哈希冲突。
-
哈希函数依赖：一个设计不佳的哈希函数可能导致数据分布不均匀，产生大量哈希冲突。
-
空间占用问题：为了减少哈希冲突，哈希表需预先分配一定的空闲空间。
二、设计哈希表
1. 哈希函数
一个好的哈希函数应具备以下特点：
- 快速计算：能够在短时间内完成对键的计算。
- 均匀分布：尽量将不同的键均匀映射到哈希表的各个位置，减少冲突的发生。
常见哈希函数有：
-
直接定址法：取关键字或关键字的某个线性函数值为哈希地址，即
Hash(key) = key或Hash(key) = a * key + b，其中a和b为常数。 -
除留余数法：这是最常用的方法之一。通过将键对一个质数取模得到哈希值。例如，
hash(key) = key % p，其中p是一个质数。 -
随机函数法：取关键字的随机函数值作为哈希地址，即
Hash(key) = random(key)。 -
数字分析法：分析每个关键字的数字分布情况，选取数字分布均匀的若干位作为哈希地址。
-
平方取中法：先计算键的平方，然后取中间几位数字作为哈希值。
-
折叠法：将键分成若干部分，然后将这些部分相加或进行其他运算得到哈希值
2. 哈希冲突
当不同的键经过哈希函数计算后得到相同的索引值时，就会发生哈希冲突。
常见的冲突处理方法有：
2.1 链地址法
原理：在哈希表的每个位置上维护一个链表，当发生冲突时，将冲突的元素添加到对应位置的链表中。Java 中的HashMap就采用了这种方式。
时间复杂度：O(1 + α)（负载因子 α：链中存储元素的平均数量。如果哈希表大小为 m 且存储 n 个元素，则 α = n/m）
常用操作：
- 初始化
class HashTableWithChaining {
private LinkedList<Node>[] table;
private int size;
public HashTableWithChaining(int size) {
this.size = size;
table = new LinkedList[size];
for (int i = 0; i < size; i++) {
table[i] = new LinkedList<>(); // 初始化每个槽位的链表
}
}
// 哈希函数示例：简单取模法
private int hashFunction(int key) {
return key % size;
}
}- 链表节点定义
class Node {
int key;
String value;
Node next;
public Node(int key, String value) {
this.key = key;
this.value = value;
this.next = null;
}
}- 查找操作
public String search(int key) {
int hashId = hashFunction(key);
LinkedList<Node> slot = table[hashId];
for (Node node : slot) {
if (node.key == key) {
return node.value;
}
}
return null; // 未找到
}- 插入操作
public void insert(int key, String value) {
int hashId = hashFunction(key);
LinkedList<Node> slot = table[hashId];
// 遍历链表检查是否已存在相同key
for (Node node : slot) {
if (node.key == key) {
node.value = value; // 更新已存在的键值对
return;
}
}
// 插入新节点到链表尾部
slot.add(new Node(key, value));
}- 删除操作
public boolean delete(int key) {
int hashId = hashFunction(key);
LinkedList<Node> slot = table[hashId];
Iterator<Node> iterator = slot.iterator();
while (iterator.hasNext()) {
Node node = iterator.next();
if (node.key == key) {
iterator.remove(); // 利用迭代器安全删除
return true;
}
}
return false; // 未找到
}- 判断哈希表是否已满：返回False
2.2 开放寻址法
原理：当发生冲突时，按特定规则在哈希表中寻找下一个空闲位置。
常用规则：
-
线性探测：当 hash(key) 发生冲突时，依次检查 hash(key) + 1、hash(key) + 2、hash(key) + 3等位置，直到找到空闲位置。
-
平方探测：当 hash(key) 发生冲突时，依次检查 hash(key) + 1²、hash(key) + 2²、hash(key) + 3²等位置。
-
双重哈希：使用两个哈希函数 hash1(key) 和 hash2(key)。当hash1(key)发生冲突时，使用hash2(key)计算下一个位置。
时间复杂度：
常见操作：
- 初始化
class HashTableWithOpenAddressing {
private Entry[] table;
private int size;
private static final double LOAD_FACTOR_THRESHOLD = 0.7; // 扩容阈值
private static final Entry TOMBSTONE = new Entry(-1, null); // 墓碑标记
public HashTableWithOpenAddressing(int initialSize) {
this.size = initialSize;
table = new Entry[size];
}
// 哈希函数示例：双重哈希（主哈希）
private int hashFunction(int key) {
return key % size;
}
// 线性探测函数
private int probe(int index, int attempt) {
return (index + attempt) % size; // 线性探测公式
}
}
// 哈希表条目定义
class Entry {
int key;
String value;
public Entry(int key, String value) {
this.key = key;
this.value = value;
}
}- 插入操作（以探测函数 h(k,i) = (h(k) + i) % m 为例）
public void insert(int key, String value) {
int attempt = 0;
int index = hashFunction(key);
while (table[index] != null && table[index] != TOMBSTONE) {
if (table[index].key == key) { // 更新已存在键
table[index].value = value;
return;
}
index = (index + 1) % size; // 线性探测
attempt++;
if (attempt >= size) throw new RuntimeException("Table full");
}
table[index] = new Entry(key, value);
}- 查找操作
public String search(int key) {
// 遍历所有可能的探测位置
for (int attempt = 0; attempt < size; attempt++) {
int pos = probe(key, attempt); // 计算探测位置
Entry entry = table[pos];
if (entry == null) {
// 遇到空槽，说明键不存在
return null;
} else if (entry != TOMBSTONE && entry.key == key) {
// 找到目标键
return entry.value;
}
}
return null; // 遍历完所有槽位未找到
}
// 探测函数示例（线性探测）
private int probe(int key, int attempt) {
int baseHash = hashFunction(key);
return (baseHash + attempt) % size;
}- 删除操作：
直接删除的问题：假设存在三个键 x0,x1,x2 哈希到同一位置，插入顺序如下：
table[probe(x0, 0)] = x0;
table[probe(x0, 1)] = x1;
table[probe(x0, 2)] = x2;
若直接删除 x1 并标记为空，后续查找 x2 时，探测位置1发现空槽，会误判 x2 不存在。
因此，正确删除实现（使用墓碑标记）如下：
public boolean delete(int key) {
for (int attempt = 0; attempt < size; attempt++) {
int pos = probe(key, attempt);
Entry entry = table[pos];
if (entry == null) {
return false; // 键不存在
} else if (entry != TOMBSTONE && entry.key == key) {
table[pos] = TOMBSTONE; // 标记为墓碑
return true;
}
}
return false;
}三、Java 中的哈希表相关类
1. HashMap
HashMap 是 Java 中最常用的哈希表实现类。它允许 null 键和 null 值，并且是非线程安全的。
import java.util.HashMap;
public class HashMapExample {
public static void main(String[] args) {
// 创建一个 HashMap
HashMap<String, Integer> hashMap = new HashMap<>();
// 插入元素
hashMap.put("apple", 10);
hashMap.put("banana", 20);
// 获取元素
int value = hashMap.get("apple");
System.out.println("Value of apple: " + value);
// 删除元素
hashMap.remove("banana");
// 遍历 HashMap
for (String key : hashMap.keySet()) {
System.out.println("Key: " + key + ", Value: " + hashMap.get(key));
}
}
}2. HashSet
HashSet 是基于 HashMap 实现的，它用于存储不重复的元素。HashSet 中的元素是无序的，并且不允许重复。
import java.util.HashSet;
public class HashSetExample {
public static void main(String[] args) {
// 创建一个 HashSet
HashSet<String> hashSet = new HashSet<>();
// 添加元素
hashSet.add("one");
hashSet.add("two");
hashSet.add("one"); // 重复元素，不会被添加
// 遍历 HashSet
for (String element : hashSet) {
System.out.println(element);
}
}
}3. Hashtable
Hashtable 是线程安全的，不允许 null 键和 null 值。由于其线程安全特性，在多线程环境下使用 Hashtable 可以避免数据不一致的问题。
import java.util.Hashtable;
public class HashtableExample {
public static void main(String[] args) {
// 创建一个 Hashtable
Hashtable<String, Integer> hashtable = new Hashtable<>();
// 插入元素
hashtable.put("key1", 100);
hashtable.put("key2", 200);
// 获取元素
int value = hashtable.get("key1");
System.out.println("Value of key1: " + value);
}
}四、哈希表的常见应用
哈希表在算法题中应用广泛，其核心优势是快速查找和记录映射关系。
- 查找元素：判断一个元素是否在集合中存在是哈希表的基本应用。例如，给定一个整数数组和一个目标值，判断数组中是否存在两个数的和等于目标值。可以遍历数组，将每个元素作为键，其索引作为值存入哈希表。在遍历过程中，对于每个元素
x，检查target - x是否在哈希表中，如果存在，则找到满足条件的两个数。 - 频率统计：可以用来统计数组中每个元素出现的次数。例如，给定一个字符串，统计字符串中每个字符出现的次数。可以遍历字符串，将每个字符作为键，出现的次数作为值存入哈希表。遍历结束后，哈希表中就存储了每个字符的出现次数。
- 去重：在处理数据时，经常用于去除重复的元素。例如，给定一个整数数组，去除数组中的重复元素，只保留每个元素的第一次出现。可以利用哈希表来记录已经出现过的元素，遍历数组时，对于每个元素，检查其是否已经在哈希表中，如果不在，则将其加入哈希表，并将其保留在数组中；如果已经在哈希表中，则说明是重复元素，将其从数组中删除。
- 分组：根据元素的某些特征将它们分组。例如，给定一个字符串数组，将所有异位词（由相同字符组成但顺序不同的字符串）分组在一起。可以对每个字符串进行排序，将排序后的字符串作为键，原始字符串作为值存入哈希表。这样，所有异位词都会被分组到同一个键下。
这些将在下一篇刷题练习中详细讲解。
哈希表是一种极为高效的数据结构，凭借其快速访问和存储灵活的特性，在算法和程序设计领域有着广泛应用。
本篇文章全面介绍了哈希表的定义、优缺点，深入剖析了哈希函数和哈希冲突处理方法（链地址法和开放寻址法），还展示了 Java 中相关类（HashMap、HashSet、Hashtable）的使用，最后列举了哈希表在查找元素、频率统计、去重和分组等方面的常见应用。
下期将深入探讨 LeetCode 上常用的哈希表练习题，并提供详细的解题思路和代码示例。这些练习题将助力你巩固哈希表的知识，提升算法思维和编程能力。
谢谢大家的支持~
更多推荐
14
0- 0
已为社区贡献1条内容
所有评论(0)