图结构与高级数据结构笔记二

学习内容:
- 哈希表（Hash Table）：
  - 哈希函数、冲突解决方法（拉链法、开放地址法）。
  - 哈希表的应用场景及优化策略。
- Trie树（前缀树）：
  - Trie树的基本概念及实现。
  - Trie树在字符串处理中的应用。
实践:
- 实现哈希表，处理冲突并优化性能。
- 实现Trie树，解决前缀匹配问题。

一、哈希表（Hash Table）

1. 哈希表的基本概念

哈希表是一种数据结构，通过键值对（key-value pair）存储数据。
哈希函数将键映射到表中的一个位置（索引）。
哈希表的核心操作：
- 插入（Insert）：将键值对插入表中。
- 查找（Search）：根据键查找对应的值。
- 删除（Delete）：根据键删除对应的键值对。

2. 哈希函数

定义：哈希函数接受一个键作为输入，并返回一个整数（哈希值），该整数对应哈希表中的索引位置。
哈希函数设计原则：
- 散列均匀：不同的键应尽量映射到不同的索引。
- 计算简单：哈希函数应尽量高效。
- 确定性：相同的键必须始终产生相同的哈希值。

示例：

def simple_hash(key, size):return key % size

3. 哈希冲突与解决方法

哈希冲突是指不同的键通过哈希函数映射到同一位置。常见的解决方法有：

3.1 拉链法

定义：使用链表存储相同哈希值的所有元素。
优点：简单直观，处理冲突灵活。
缺点：在极端情况下，所有键都映射到同一索引位置，链表退化为线性结构，查找效率降低。

示例：

class HashTable:def __init__(self, size):self.size = sizeself.table = [[] for _ in range(size)]def hash_function(self, key):return key % self.sizedef insert(self, key, value):index = self.hash_function(key)for kvp in self.table[index]:if kvp[0] == key:kvp[1] = valuereturnself.table[index].append([key, value])def get(self, key):index = self.hash_function(key)for kvp in self.table[index]:if kvp[0] == key:return kvp[1]return None

3.2 开放地址法

定义：在发生冲突时，寻找下一个空闲位置存放键值对。
常见策略：
- 线性探测：从冲突位置开始，依次探测下一个位置。
- 二次探测：根据二次函数探测新位置，减少聚集效应。
- 双重散列：使用另一个哈希函数计算步长。

示例（线性探测法）：

class HashTable:def __init__(self, size):self.size = sizeself.table = [None] * sizedef hash_function(self, key):return key % self.sizedef insert(self, key, value):index = self.hash_function(key)while self.table[index] is not None:index = (index + 1) % self.sizeself.table[index] = (key, value)def get(self, key):index = self.hash_function(key)while self.table[index] is not None:if self.table[index][0] == key:return self.table[index][1]index = (index + 1) % self.sizereturn None

4. 哈希表的应用场景及优化策略

4.1 应用场景

快速查找：如符号表、缓存、数据库索引等。
计数统计：如统计单词频率。
去重：如判断元素是否出现过。

4.2 优化策略

负载因子：控制负载因子（装载因子）在一定范围内（如0.7左右），保持哈希表的性能。
动态扩展：当负载因子过高时，自动扩展哈希表的容量并重新散列。
优化哈希函数：选择散列效果好的哈希函数，减少冲突。

二、Trie树（前缀树）

1. Trie树的基本概念

Trie树是一种多叉树，用于高效地存储和查找字符串的前缀。
特点：
- 每个节点代表一个字符。
- 从根节点到某一节点的路径表示一个字符串的前缀。
- 叶节点表示一个完整的字符串。

Trie树的结构：

          ""/  \"a"  "b"/     \"p"     "a"/       / \"p"     "r" "t"/       /"l"     "e"/         \
"e"       "s"

2. Trie树的实现

Trie树的基本操作：

插入：将一个字符串插入Trie树。
查找：判断一个字符串是否在Trie树中。
删除：从Trie树中删除一个字符串。

示例：

class TrieNode:def __init__(self):self.children = {}self.is_end_of_word = Falseclass Trie:def __init__(self):self.root = TrieNode()def insert(self, word):node = self.rootfor char in word:if char not in node.children:node.children[char] = TrieNode()node = node.children[char]node.is_end_of_word = Truedef search(self, word):node = self.rootfor char in word:if char not in node.children:return Falsenode = node.children[char]return node.is_end_of_worddef starts_with(self, prefix):node = self.rootfor char in prefix:if char not in node.children:return Falsenode = node.children[char]return True

3. Trie树在字符串处理中的应用

前缀匹配：快速查找具有相同前缀的单词，如搜索建议功能。
词频统计：在大量字符串中快速统计某个前缀出现的频率。
字符串排序：通过Trie树对字符串进行字典序排序。

前缀匹配示例：

trie = Trie()
words = ["apple", "app", "apex", "bat", "bar", "barn"]
for word in words:trie.insert(word)print(trie.starts_with("ap"))  # True
print(trie.starts_with("ba"))  # True
print(trie.starts_with("cat")) # False

三、实践：实现哈希表与Trie树

1. 实现哈希表

功能：
- 支持插入、查找和删除操作。
- 处理哈希冲突。
- 优化性能（如扩展哈希表、动态调整负载因子）。

代码实现：

class HashTable:def __init__(self, size=10):self.size = sizeself.table = [[] for _ in range(size)]self.count = 0self.load_factor = 0.75def hash_function(self, key):return hash(key) % self.sizedef resize(self):new_size = self.size * 2new_table = [[] for _ in range(new_size)]for bucket in self.table:for key, value in bucket:index = hash(key) % new_sizenew_table[index].append((key, value))self.size = new_sizeself.table = new_tabledef insert(self, key, value):if self.count / self.size > self.load_factor:self.resize()index = self.hash_function(key)for kvp in self.table[index]:if kvp[0] == key:kvp[1] = valuereturnself.table[index].append((key, value))self.count += 1def get(self, key):index = self.hash_function(key)for kvp in self.table[index]:if kvp[0] == key:return kvp[1]return Nonedef delete(self, key):index = self.hash_function(key)for i, kvp in enumerate(self.table[index]):if kvp[0] == key:del self.table[index][i]self.count -= 1return Truereturn False

2. 实现Trie树

功能
- 支持插入、查找和前缀匹配操作。
- 用于高效处理字符串集合。

代码实现：

class TrieNode:def __init__(self):self.children = {}self.is_end_of_word = Falseclass Trie:def __init__(self):self.root = TrieNode()def insert(self, word):node = self.rootfor char in word:if char not in node.children:node.children[char] = TrieNode()node = node.children[char]node.is_end_of_word = Truedef search(self, word):node = self.rootfor char in word:if char not in node.children:return Falsenode = node.children[char]return node.is_end_of_worddef starts_with(self, prefix):node = self.rootfor char in prefix:if char not in node.children:return Falsenode = node.children[char]return Truedef delete(self, word):def _delete(node, word, depth):if depth == len(word):if not node.is_end_of_word:return Falsenode.is_end_of_word = Falsereturn len(node.children) == 0char = word[depth]if char not in node.children:return Falsecan_delete_child = _delete(node.children[char], word, depth + 1)if can_delete_child:del node.children[char]return len(node.children) == 0return False_delete(self.root, word, 0)# 使用示例
trie = Trie()
words = ["apple", "app", "apex", "bat", "bar", "barn"]
for word in words:trie.insert(word)# 查找操作
print(trie.search("apple"))  # True
print(trie.search("app"))    # True
print(trie.search("bat"))    # True
print(trie.search("bats"))   # False# 前缀匹配操作
print(trie.starts_with("ap"))  # True
print(trie.starts_with("ba"))  # True
print(trie.starts_with("cat")) # False# 删除操作
trie.delete("app")
print(trie.search("app"))    # False
print(trie.search("apple"))  # True