O（1）随机插入/删除和O（1）随机访问的数据结构有哪些？ [英] What data structure for O(1) random insertion/deletion and O(1) random access?

问题描述

我不知道用什么数据结构来解决这个问题。我想要结构：

I don't know what data structure to use for this problem. I want the structure to have:

• 定时插入或删除。


• id。

实际系统是：

我有一个一堆对象，每个对象都有唯一的ID。我的程序将需要接收id的请求并返回相关对象。

I've got a bunch of objects each with a unique id. My program will need to receive requests for an id and return the relevant object.

无论何时收到请求，我想要：搜索结构以查看是否存在。如果是，返回。如果没有，请将其从磁盘加载到内存（将其放在结构中，以便下次请求时不必使用磁盘），然后返回。

Whenever it receives a request I want it to: search the structure to see if it's there. If it is, return it. If it isn't, load it from the disk into memory (put it in the structure so that next time it is requested it doesn't have to use the disk) and then return it.

我正在使用C。

这是一个类似的问题，但我不确定它是多么相关。

Here's a similar question but I'm not sure how relevant it is.

推荐答案

哈希表可能是在你的情况下，很好的解决方案 - 即使没有在O（1）有一个联合：这是一个非常有效的解决方案。

A Hash table might be a pretty good solution in your case -- even if it's not in O(1) when there's a colision : it's a quite efficient solution.

这篇关于O（1）随机插入/删除和O（1）随机访问的数据结构有哪些？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！