哈希表(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/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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]