哈希表（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]