设计一种支持常数时间插入、删除、搜索和 getRandom 的数据结构。

在设计支持插入、删除、搜索和检索元素等基本操作的数据结构时，运行时效率对可伸缩性至关重要。随着数据结构保存的信息越来越多，保持这些操作的快速性变得具有挑战性。虽然数组或链表等主要数据结构允许某些高效的操作，但在其他操作上却表现不佳，尤其是在它们变得庞大时。最佳解决方案是采用混合数据结构，它结合了简单结构体的优点，不仅能对一项，而是对所有四个关键操作实现快速的常数时间性能。在本文中，我们将讨论一种混合数据结构，它将哈希表与动态数组配对，能够在海量数据集上以保证的 O(1) 时间支持插入、删除、搜索和随机获取。通过了解这些相互关联的格式之间的协同作用，开发人员可以构建为速度和可伸缩性量身定制的数据容器。

主要亮点是：需要能够处理大数据的高效数据结构；更简单数据结构的局限性；提出使用哈希表+数组组合来实现所有必需操作的效率；以及这种混合格式如何利用这两种结构的优点。

如何设计数据结构？

哈希表

哈希表可以使用 Python 中的字典来实现。字典提供高效的键值查找、插入和删除，非常适合实现哈希表。

我们可以定义一个字典，将每个键映射到一个索引值。这个索引将链接到数组中元素的位置。字典操作（如设置/获取元素）只需要 O(1) 时间。

字典的大小也应与 N 成比例（不考虑负载因子），以存储 N 个元素。当底层字典容器开始填满时调整其大小，可以确保运行时承诺得到履行。

键到数组索引的确切映射取决于所使用的哈希函数。哈希函数应提供均匀的哈希分布以最大程度地减少冲突。常见的选择包括 MD5、SHA256 或任何现有的哈希库。

Array

Python 列表非常适合用作动态数组。向列表追加、插入、删除和访问列表元素都很快。这满足了我们的所有要求。

列表将存储插入到我们数据结构中的每个元素。通过将哈希表中的索引链接到此列表中的位置，可以随时高效地访问或操作元素。

我们可以从一个初始化为适当容量的列表开始，并在它开始填满时根据需要进行扩展。选择正确的初始大小和扩展参数会影响性能。

了解操作

插入操作

插入操作允许将新元素添加到数据结构中。具体来说，它支持以下功能：

1. 如果容量允许，则为新元素值分配内存。
2. 更新内部数据结构跟踪以反映新元素的出现。这通常涉及更新索引表、指针等。
3. 在某些情况下，可能还需要维护元素之间的插入顺序。

插入的时间复杂度取决于数据结构类型及其实现。目标是无论数据结构大小如何，都能实现 O(1) 的常数时间插入。

删除操作

删除操作有助于从数据结构中移除现有元素。这需要几个关键任务：

1. 通常基于某个标识符或键，通过搜索查找要删除的元素。
2. 释放为要删除的元素分配的任何内存。
3. 通过修改索引、指针等来更新内部数据结构跟踪，以反映该元素的逻辑删除。
4. 数据结构中的任何其他元素也可能需要移动或重新定位，以填补元素删除留下的空间并保持结构的连续性。

与插入一样，删除操作的目标是 O(1) 的时间复杂度，同样独立于存在的元素总数。

搜索操作

搜索功能允许检查给定元素当前是否存在于数据结构中。以下是涉及的广泛步骤：

1. 接受包含要查找的元素键或标识符值的搜索查询。
2. 扫描数据结构跟踪元数据（如索引表、节点指针等）以定位元素。
3. 如果找到匹配的元素，则返回 true 或 false。

虽然 O(1) 的查找时间是理想的，但通过二叉搜索树，O(log N) 仍然被认为是高效的。

getRandom 操作

getRandom 操作从数据结构中均匀随机地获取一个任意元素。主要步骤是：

1. 在数据结构边界内生成均匀随机整数索引。
2. 使用索引访问存储在内存中该位置的元素。
3. 返回访问到的随机元素。

获取随机元素也以 O(1) 的时间为目标，与上述操作类似。

此 DS 的 Python 实现

此程序实现了一种随机数据结构，支持高效的搜索、插入、删除和随机访问操作。该结构结合了哈希表和动态数组来随机存储元素，从而实现快速查找和访问。

此数据结构提供的一些关键功能：

• 对元素的快速 O(1) 搜索
• 高效的 O(1) 元素删除和插入
• 在 O(1) 时间内快速访问随机元素
• 以随机顺序存储元素，允许访问的随机性

随机排序和快速访问使其适用于需要随机性的应用程序，例如播放列表随机播放、游戏、采样等。

算法步骤

1. 初始化一个哈希表（Python 字典）以存储将元素映射到其索引的键值对
2. 初始化一个动态数组（Python 列表）以随机存储元素
3. 要插入一个元素
   • 检查元素是否已存在于哈希表中
   • 如果不存在，则将其追加到动态数组的末尾
   • 将元素到其数组索引的映射存储在哈希表中
4. 要删除一个元素
   • 从哈希表中获取要删除元素的索引
   • 将数组中的最后一个元素替换要删除的元素
   • 更新最后一个元素的索引映射
   • 从数组中弹出最后一个元素（原始副本）
5. 要搜索一个元素
   • 直接从哈希表中检索索引
   • 如果找到元素则返回索引，否则返回 -1
6. 要获取一个随机元素
   • 使用 choice() 方法选择一个随机索引
   • 访问数组中该索引处的元素

输出

说明

RandomizedDS 类实现了一种随机存储元素并支持高效搜索、插入、删除和随机访问的数据结构。下面是分步说明：

1. init 方法初始化两个数据成员：
   • self.data - 一个哈希表（Python 字典），它将每个元素映射到其在列表中的索引
   • self.elements - 一个包含所有已插入元素的列表
2. insert() 方法
   • 使用哈希表检查元素是否已存在（O(1) 检查）
   • 如果不存在，则将元素追加到列表末尾。
   • 通过将插入的元素映射到其在列表中的新索引来更新哈希表
   • 如果插入成功则返回 True，否则返回 False
3. remove() 方法
   • 使用哈希表在 O(1) 时间内检索要删除元素的索引
   • 获取列表中的最后一个元素并将其放在要删除元素的位置
   • 更新哈希表中最后一个元素的索引
   • 弹出（删除）列表末尾的重复最后一个元素
   • 从哈希表中删除要删除的键
4. getRandom() 方法使用 random.choice() 从列表中随机选择一个元素。
5. search() 方法使用哈希表在 O(1) 时间内检索元素的索引。如果元素存在，否则返回 -1。
6. 用法示例
   1. 创建一个 RandomizedDS 对象
   2. 插入元素
   3. 搜索已插入的元素（True 表示找到）
   4. 打印随机选择的元素
   5. 尝试删除该元素
   6. 再次搜索以检查删除情况

结论

简单来说，我们看到了如何混合两种基本数据结构——哈希表和数组——可以为我们提供在各个方面都表现出色的定制容器。通过利用它们各自的优点，我们得到了一个快速的全能型选手。

哈希表使用巧妙的编号直接访问数据条目。数组按顺序放置项，以便于插入和随机选取。它们的组合弥补了各自的不足。联合结构使我们能够快速地添加、删除、查找和随机获取元素，即使是在大型集合中。

我们所需的技术在高层次上也很容易掌握。哈希函数以均衡的方式将键映射到数组位置。预留额外的空间可以避免拥挤，后者会降低速度。虽然使用这些想法编写自然系统会增加复杂性，但其概念是直观的。

我们专门研究了在 Python 中构建可定制数据存储的指导方针。其标准的字典和列表类型已经提供了实现高效率所需的组件。只需正确地将它们组合起来，就可以轻松地构建出通用的结构。

在数据分析领域，这种可定制的容器是构建块。即使数据量很大，也能提供强大的速度保证，这使得构建可扩展的架构成为可能。创新产品通过提供响应式的信息存储、检索和共享来造福最终用户。

对于从事分析管道工作的工程师来说，理解这些创建定制化数据结构的基本技术至关重要。

本文展示了如何通过结合互补的方法，获得比各部分之和更重要的、可定制且高效的解决方案。使用这些乐高积木可以构建满足实际需求的分析系统。