database - 处理以下用例要求的数据结构

Question

数据库中的所有记录都以(键，值)对格式保存。始终可以通过指定键值来检索记录。需要开发数据结构来处理以下场景

1. 以线性方式访问所有记录(数组或链表是此场景在 O(N) 时间内访问的最佳数据结构)
2. 通过提供键检索记录(可以实现哈希表以在 O(1) 复杂度中对其进行索引)
3. 检索键中特定字节值的记录集。例如:键中第二个数字(10 位)应为 5 的所有记录的列表，如果键为 256、1452、362、874，则应返回键、256 和 1452 的记录

Answer 1

我假设您的 key 最多为 d 位(十进制)。

一个普通的哈希表和一个额外的 10*d 二维数组(我们称它为 A)集合怎么样。 A[i][j] 是第 j 个位置有数字 i 的键集。如果将自己实现为哈希表，这些集合可以支持 O(1) 插入/删除操作。