哈希表（Hash Table）的基本概念
哈希表是一种数据结构，它可以在平均情况下提供非常快速的插入、删除和查找操作。其基本思想是通过一个哈希函数将键（key）映射到一个特定的索引（index），然后将对应的值（value）存储在该索引位置。
哈希函数（Hash Function）
- 哈希函数是哈希表的核心，它将输入的键转换为数组的索引。例如，对于一个简单的整数键的哈希函数可以是hash(key) = key % array_size，这里array_size是存储数据的数组的大小。
- 一个好的哈希函数应该尽量减少冲突（Collision），即不同的键被映射到相同的索引位置。常见的哈希函数构造方法包括直接定址法、除留余数法、数字分析法、平方取中法、折叠法、随机数法等。
处理冲突（Collision Resolution）
- 链地址法（Chaining）：当发生冲突时，在该索引位置创建一个链表，将新元素添加到链表中。这种方法简单且易于实现，但在最坏情况下，查找时间可能会退化到O(n)，其中n是链表的长度。
- 开放定址法（Open Addressing）：当发生冲突时，按照某种规则在哈希表中寻找下一个可用的位置。常见的开放定址法包括线性探测法、二次探测法和双重哈希法等。
哈希表的操作
- 插入（Insertion）：通过哈希函数计算键对应的索引，然后将值存储在该索引位置。如果该位置已经有元素（冲突），则根据冲突处理方法进行处理。
- 查找（Search）：根据键通过哈希函数找到对应的索引位置，然后在该位置查找对应的值。如果使用链地址法，可能需要在链表中进行查找；如果使用开放定址法，可能需要按照开放定址的规则进行多次探测。
- 删除（Deletion）：删除操作相对复杂一些，因为不能简单地删除元素，否则可能会影响后续的查找操作。在链地址法中，需要在链表中删除对应的节点；在开放定址法中，通常需要将删除的位置标记为已删除，而不是真正删除，以保证后续查找操作的正确性。
哈希表的应用场景
- 数据库索引：哈希表可以用于实现数据库中的索引，提高数据的检索速度。例如，在根据用户 ID 查找用户信息时，可以使用哈希表快速定位到存储用户信息的位置。
- 缓存系统：在缓存系统中，哈希表可以快速判断一个请求是否已经在缓存中，如果在，则直接返回缓存的结果，提高系统的响应速度。
- 编译器的符号表：在编译器中，哈希表可以用于存储变量名、函数名等符号信息，方便在编译过程中快速查找和管理这些符号。
CR 030. O(1) 时间插入、删除和获取随机元素: https://leetcode.cn/problems/FortPu/description/
代码语言：javascript复制import random
class RandomizedSet:
def __init__(self):
"""
Initialize your data structure here.
"""
self.data = []
self.map = {}
def insert(self, val: int) -> bool:
"""
Inserts a value to the set. Returns true if the set did not already contain the specified element.
"""
if val not in self.map or (val in self.map and self.map[val] == None):
self.data.append(val)
self.map[val] = self.data.index(val)
return True
else:
return False
def remove(self, val: int) -> bool:
"""
Removes a value from the set. Returns true if the set contained the specified element.
"""
if val in self.map and self.map[val] is not None:
self.map[val] = None
return True
else:
return False
def getRandom(self) -> int:
"""
Get a random element from the set.
"""
while True:
randomIdx = random.randint(0, len(self.data) - 1)
if self.data[randomIdx] in self.map and self.map[self.data[randomIdx]] is not None:
return self.data[randomIdx]
