-
学习内容:
- 哈希表(Hash Table):
- 哈希函数、冲突解决方法(拉链法、开放地址法)。
- 哈希表的应用场景及优化策略。
- Trie树(前缀树):
- Trie树的基本概念及实现。
- Trie树在字符串处理中的应用。
- 哈希表(Hash Table):
-
实践:
- 实现哈希表,处理冲突并优化性能。
- 实现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
3. 实践总结
- 哈希表和Trie树是常见的数据结构,广泛用于快速数据检索、字符串处理等场景。
- 哈希表通过哈希函数将键映射到索引位置,处理冲突的方式主要包括拉链法和开放地址法。优化策略包括控制负载因子和动态扩展哈希表。
- Trie树适合处理前缀匹配问题,可以快速插入、查找和删除字符串,特别在实现自动补全、词频统计等功能时有明显优势。
- 实践过程中,通过实现哈希表和Trie树,进一步理解了这些数据结构的内部机制和应用场景,为解决实际问题奠定了基础。