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

设计一个能够实现常数时间插入、删除、搜索和随机访问的数据结构，是计算机科学中的一个有趣问题。要在这些操作中获得一致的时间复杂度，有时需要权衡数据存储和访问的各种特性。本文深入探讨了构建此类数据结构的几种策略和方法的关键原则以及潜在实现。

引言

数据结构是高效计算的基础。追求一种在插入、删除、搜索和随机访问等关键操作中具有恒定时间复杂度的אata structure 一直是算法设计的重点。数组、链表、树和哈希表等传统数据结构各有其优点，但它们通常需要为同时执行所有这些操作提供常数时间。为了实现这一目标，通常会采用结合了这些结构特性的创新方法。

要求

在深入设计之前，理解数据结构的要求和约束至关重要。

1. 常数时间复杂度：所有操作，包括插入、删除、搜索和随机访问，都应在常数时间内执行，表示为 O(1)。
2. 动态调整大小：数据结构应能够处理动态调整大小，以适应不断变化的项的数量。
3. 支持随机访问：在常数时间内访问随机元素至关重要。
4. 无特定顺序要求：没有特定的顺序要求。元素不能像数组或列表那样存储。

可能的解决方案

哈希表和数组/列表 哈希表

在大多数情况下，插入、删除和搜索典型的哈希表需要 O(1) 的时间。然而，由于哈希函数的性质，要获得常数时间的随机访问需要时间。结合了允许随机访问的数组或列表的哈希表可以满足要求。

带额外索引的平衡树

对于大多数操作，如 AVL 或红黑树这样的平衡树提供 O(log n) 的时间复杂度。包含额外的索引机制（如指针数组）可以实现常数时间的随机访问。

哈希表可调整大小的数组

可调整大小的数组（如 Python 中的列表或 C++ 中的 vector）可以实现常数时间的随机访问。将其与包含数组索引的哈希表结合，理论上可以为所有操作提供常数时间。

设计：可调整大小的数组 + 哈希表

让我们来看一个结合了可调整大小的数组和哈希表的可能解决方案，以满足要求。

数据结构元素

可调整大小的数组（ArrayList）：一个动态调整其大小以接受项的数组。

哈希表（HashMap）：将组件映射到其数组索引。

操作

插入 (insert(element))

• 将元素添加到可调整大小的数组末尾。
• 将新添加元素的索引存储在哈希表中，以元素作为键。

删除 (delete(element))

• 在哈希表中查找元素的索引。
• 从数组中移除元素，并相应地更新哈希表中的索引。

搜索 (search(element))

• 从哈希表中检索元素的索引，并在数组中的该索引处返回元素。

GetRandom (getRandom())

• 生成一个在数组当前大小范围内的随机索引。
• 返回生成索引处的元素。

复杂性分析

插入、删除、搜索和 GetRandom：这些操作中的每一个都需要对哈希表和数组进行常数时间访问，从而确保满足 O(1) 复杂度条件。

实施

输出

说明

• ConstantTimeDS 以两种方式存储数字：一个数组和一个类似映射的系统 (hash_map) 以快速查找数组中的数字。
• Size 跟踪结构中有多少个数字。
• initializeDS：初始设置结构，为数字创建空间。
• Insert：如果数字尚不存在，则将其添加到结构中。
• Delete：从结构中移除数字。
• Search：检查数字是否存在于结构中。
• getRandom：从现有数字中检索一个随机数字。
• 插入和删除：确保结构不超过特定大小并保持唯一性。
• Search：检查数字是否存在。
• getRandom：从可用数字中选择一个随机数字。
• 限制为最大元素数量（由 MAX_SIZE 设置）。
• 由于大小固定，不适用于大规模应用。