我的作业是算法介绍练习11.1-3，内容如下：
建议如何实现一个直接访问表，其中存储元素的键不需要是不同的，并且元素可以有卫星数据。所有三个字典操作（插入、删除和搜索）都应该在 O(1) 时间内运行。不要忘记 Delete 将指向要删除的对象的指针作为参数，而不是键。
好吧，插入是没有问题的，因为它只是意味着在表中的适当位置创建一个链表（如果它不存在）并将元素添加到其中。给定一个键的搜索可以返回任何与该键匹配的元素，所以它只是意味着我们需要返回表中匹配列表的头部。
我的问题是删除操作。如果我修改对象以向其添加指向其在链表中的节点的指针，那么我可以在O(1)中删除，但我不确定是否允许更改该对象。有没有办法在不改变给定对象的情况下做到这一点？
这是Cormen书中的问题吗？据我了解，通过阅读该书前面的段落，您存储在直接访问表中的对象是“您的”对象。因此，您可以按照您的建议将指向双向链表的指针存储在表中，每个列表元素都有一个指向用户对象的指针。然后，字典搜索操作返回一个列表元素，用户必须使用进一步的步骤来获取他的对象。同样，DELETE 操作采用指向列表元素的指针。
那有意义吗？我不想破坏你的作业！
我们可以在直接地址表的每个索引处使用双链表。插槽 j 将包含指向列表头部的指针，其中包含具有键值 j 的所有元素，如果没有这样的元素，则插槽 j 包含 NIL。INSERT-在列表头部插入 x 只需要 O(1) 时间。SEARCH - 它可以返回与给定键匹配的任何元素，因此返回列表的头部将只需要 O(1) 时间。删除 - 由于我们使用了双链表，我们可以使用指向前一个和下一个节点的指针在 O(1) 时间内删除一个元素。
我认为您可以利用要映射的卫星数据作为辅助键。然后它是一种 2 级哈希表。关于 DELETE 操作，首先我们使用主键。而当有重复的主键时，我们使用辅助键来获取对象。因此总时间仍然是 O(1)。
哈希表将在一定程度上为您工作。一旦你开始发生冲突，它就会变成 O(1+k/n)，其中 k 是键的数量，n 是你的表大小。如果您执行预定的散列调整大小和重新散列，那么您可能能够摆脱这种情况。不知道这是否会影响您的效率评级，因为它不会在插入、删除或搜索期间发生。
只需将散列引用指针设置为空即可实现不更改对象的删除。不会直接更改对象，但会更改对象容器。
我认为对于您给出的大多数限制，可以通过某些方式实现哈希表来绕过它们。在http://en.wikipedia.org/wiki/Hash_table#Performance_analysis上有更多关于如何实现哈希表的信息。
最重要的部分..“实现一个直接访问表，其中存储元素的键不需要是不同的”和“O(1) 时间内的字典操作。
如果元素相等（如 Q 所说的元素不需要不同），则在 O(1) 时间内也无法插入。
对于删除部分，您必须获取键和对象才能到达特定对象，并假设卫星数据中的键也可以到达特定对象。
我认为只有以上 2 个想法对 O(1) 时间有意义。