哈希表的工作原理

6.1 哈希表的定义和结构

哈希表 是一种数据结构，提供快速查找、插入和删除元素的能力，使用哈希函数来计算数组或列表中的索引。哈希表通常用于实现关联数组，即字典。

哈希表的重要方面

数组 是哈希表的主要组件，它存储指向元素或元素列表的指针。

哈希函数： 将字典键转换为数组索引的函数。

冲突： 当两个不同的键具有相同的哈希值时的情况。用于解决冲突的方法有链地址法或开放寻址法。

字典示例：

{
   "apple": 101,
   "banana": 102,
   "cherry": 103
}

哈希表结构示例：

6.2 哈希表的基本操作

哈希表的基本操作：插入、查找、删除

1. 插入 (Insertion): 将新元素 (键-值对) 添加到哈希表中的过程。

插入步骤：

1. 通过哈希函数计算键的哈希值。
2. 根据哈希值在数组中找到索引。
3. 如果该索引处已有元素（冲突），则将元素添加到列表中（对于链地址法）或找到下一个可用的索引（对于开放寻址法）。

使用链地址法插入到哈希表的示例：

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

    def hash_function(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        index = self.hash_function(key)
        if self.table[index] is None:
            self.table[index] = [(key, value)]
        else:
            for i, kv in enumerate(self.table[index]):
                k, v = kv
                if k == key:
                    self.table[index][i] = (key, value)
                    return
            self.table[index].append((key, value))

# 使用示例：
hash_table = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.table)

2. 查找 (Search): 在给定键的情况下查找哈希表中的值的过程。

查找步骤：

1. 通过哈希函数计算键的哈希值。
2. 根据哈希值在数组中找到索引。
3. 检查列表中的键（对于链地址法）或索引处的键（对于开放寻址法）是否存在。

使用链地址法查找哈希表的示例：

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

    def hash_function(self, key):
        return hash(key) % self.size

    def search(self, key):
        index = self.hash_function(key)
        if self.table[index] is None:
            return None
        for k, v in self.table[index]:
            if k == key:
                return v
        return None

# 使用示例：
hash_table = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.search("banana"))  # 输出: 2
print(hash_table.search("grape"))   # 输出: None

3. 删除 (Deletion): 从哈希表中删除元素 (键-值对) 的过程。

删除步骤：

1. 通过哈希函数计算键的哈希值。
2. 根据哈希值在数组中找到索引。
3. 从列表中删除元素（对于链地址法）或将索引处的值设为 None（对于开放寻址法）。

使用链地址法从哈希表删除的示例：

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

    def hash_function(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        index = self.hash_function(key)
        if self.table[index] is None:
            self.table[index] = [(key, value)]
        else:
            for i, kv in enumerate(self.table[index]):
                k, v = kv
                if k == key:
                    self.table[index][i] = (key, value)
                    return
            self.table[index].append((key, value))

    def delete(self, key):
        index = self.hash_function(key)
        if self.table[index] is None:
            return
        for i, kv in enumerate(self.table[index]):
            k, v = kv
            if k == key:
                del self.table[index][i]
                return

# 使用示例：
hash_table = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.table)
hash_table.delete("banana")
print(hash_table.table)
print(hash_table.search("banana"))  # 输出: None

6.3 哈希表的时间复杂度

哈希表操作的时间复杂度

插入 (Insertion):

• 平均情况: O(1)
• 最坏情况: O(n) （在发生大量冲突或所有元素都落在相同位置时）

查找 (Search):

• 平均情况: O(1)
• 最坏情况: O(n)（在发生大量冲突或所有元素都落在相同位置时）

删除 (Deletion):

• 平均情况: O(1)
• 最坏情况: O(n)（在发生大量冲突或所有元素都落在相同位置时）

解释：

平均情况: 在平均情况下，哈希函数会将元素均匀分布在表中，每个元素都有自己独特的槽，这样访问时间是恒定的 O(1)。

最坏情况: 在最坏的情况下，由于糟糕的哈希函数或大量冲突，所有元素都落在同一个槽中。此时，哈希表会退化成链表，操作的时间复杂度变为 O(n)。

6.4 哈希表的使用示例

1. 实现字典（关联数组）

哈希表常用于实现字典，允许存储键值对并通过键快速访问。

示例:

# 创建字典
dictionary = {}

# 插入元素
dictionary["apple"] = 1
dictionary["banana"] = 2
dictionary["cherry"] = 3

# 查找元素
print(dictionary["banana"])  # 输出: 2

# 删除元素
del dictionary["cherry"]

# 检查键是否存在
if "apple" in dictionary:
    print("键 'apple' 存在于字典中")  # 输出: 键 'apple' 存在于字典中

现在，你对Python中的字典和它的结构了解更多了。

2. 缓存计算结果

哈希表用于缓存昂贵计算的结果，以加速后续的请求。

示例:

# 缓存存储结果
cache = {}

def expensive_computation(x):
    if x in cache:
        return cache[x]
    result = x * x  # 示例昂贵计算
    cache[x] = result
    return result

# 使用缓存
print(expensive_computation(10))  # 输出: 100（计算并缓存）
print(expensive_computation(10))  # 输出: 100（来自缓存）

3. 统计文本中的词频

哈希表用于统计每个单词在文本中出现的次数。

示例:

from collections import defaultdict

text = "this is a simple text with some simple words this is simple"
word_count = defaultdict(int)

for word in text.split():
    word_count[word] += 1

# 输出结果
for word, count in word_count.items():
    print(f"单词 '{word}' 出现 {count} 次")

4. 在列表中查找重复项

哈希表用于高效查找列表中的重复项。

def find_duplicates(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

# 使用示例
arr = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr))  # 输出: [2, 4]