哈希表和列表并排? [英] Hashtable and list side by side?

问题描述

我需要一个有序的数据结构，但也可以提供快速的随机访问以及插入和删除操作.链表的排序和插入和删除速度很快，但是它们提供的随机访问速度很慢.哈希表可提供快速的随机访问，但没有顺序.

I need a data structure that is ordered but also gives fast random access and inserts and removes. Linkedlists are ordered and fast in inserts and removes but they give slow random access. Hashtables give fast random access but are not ordered.

因此，将它们一起使用似乎很好.在当前解决方案中，我的Hashtable包含列表的迭代器，而List包含实际项目.尼斯和有效.好的，它需要两倍的内存，但这不是问题.

So, it seems to nice to use both of them together. In my current solution, my Hashtable includes iterators of the list and the List contains the actual items. Nice and effective. Okay, it requires double the memory but that's not an issue.

我听说有些树结构也可以做到这一点，但是它们和这种解决方案一样快吗?

I have heard that some tree structures could do this also, but are they as fast as this solution?

推荐答案

我知道最有效的树结构是

The most efficient tree structure I know is Red Black Tree, and it's not as fast as your solution as it has O(log n) for all operations while your solution has O(1) for some, if not all, operations.

如果内存不是问题，并且您确定解决方案为O(1)，则意味着在结构中添加/删除/查找项目所需的时间与您拥有的项目数量无关，请继续.

If memory is not an issue and you sure your solution is O(1) meaning the time required to add/delete/find item in the structure is not related to the amount of items you have, go for it.

这篇关于哈希表和列表并排?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！