哈希表和列表并排吗？

我需要一个有序的数据结构，但也提供快速的随机访问和插入和删除。链表被排序和快速插入并删除，但他们给予缓慢的随机访问。散列表提供快速的随机访问，但没有排序。哈希表和列表并排吗？

所以，它们似乎很好地使用它们在一起。在我当前的解决方案中，我的Hashtable包含列表的迭代器，List包含实际的项目。好而有效。好吧，它需要双倍的内存，但这不是一个问题。

我听说一些树形结构能做到这一点还，但他们一样快，这个解决方案？

来源

2010-11-07 glhfgg

如果我没错，内存使用不应该成为一个问题。所有你需要的是为链表存储一些额外的指针/引用，对吧？ – TinkerTank 2010-11-07 14:42:16

你想如何随机访问？你会如何随机访问？ – nawfal 2014-06-06 08:06:58

我知道的最有效的树结构是Red Black Tree，它不像解决方案那样快，因为它对所有操作都有O（log n），而对于一些操作（即使不是全部操作），您的解决方案有O（1）。

如果内存不是问题，并且您确定您的解决方案是O（1），这意味着在结构中添加/删除/查找项目所需的时间与您拥有的项目数量无关，请参阅。

来源

2010-11-07 14:28:34

的Java实际上包含LinkedHashTable，它类似于您所描述的数据结构。有时候这可能会令人惊讶地有用。

树结构可以工作为好，看他们能执行（O log n）的时间随机存取（和大多数其他操作）。不如哈希表（O 1）快，但仍然很快，除非您的数据库非常大。

树木的唯一真正的好处是，你不需要事先对容量决定。一些HashTable实现可以根据需要增加容量，但只需通过将所有项目复制到一个新的更大的散列表（当它们的容量已超出其容量时非常缓慢）即可实现。（O N）

来源

2010-11-07 14:30:25 TinkerTank

你应该考虑一个Skip List，这是一个有序链表与O（log n）的访问时间。换句话说，你可以枚举它O（n）和索引/插入/删除是O（log n）。

来源

2010-11-07 14:34:42 Gabe

树是为此而制作的。最合适的是自我平衡的树像AVL tree或Red Black tree。如果处理的数据量非常大，则创建B-tree（例如，它们用于文件系统）也可能很有用。

关于您的实现：它可能是或多或少高效然后树木取决于数据量和你一起工作和散列表实施。例如。一些非常密集数据的哈希表可能不会在O（1）中提供访问，而是在O（log n）甚至O（n）中提供访问。另外请记住，从数据计算散列也需要一些时间，因此对于退出的小数据来说，计算散列的绝对时间可能更多，因此可能在树中搜索它。

来源

2010-11-07 14:49:15 ffriend

你所做的几乎是正确的选择。

这个很酷的事情是，通过使用双端双向链表向现有映射实现添加排序实际上并没有改变其渐近复杂性，因为所有相关的列表操作（添加和删除）都有一个Θ（1）的最坏情况步骤复杂性。（是的，删除也是Θ（1）。究其原因通常是Θ（n）是因为你必须找到元素删除第一，这是Θ（N），但实际删除本身是Θ（1）。在这个特定的情况下，你让地图做的发现，这是一样的东西Θ（1）摊销最坏情况步骤复杂或Θ（日志_b＆thinsp; n）的最坏情况下的步骤的复杂性，这取决于地图的类型）

例如，Ruby 1.9中的Hash类是一个有序映射，它至少在YARV和Rubinius中作为嵌入链表的哈希表实现。

树木通常具有Θ最坏情况步骤复杂（日志_b＆thinsp; N）用于随机接入，而散列表可以是在最坏的情况更差（Θ（n））的，但通常缓冲至Θ （1），前提是你不要搞乱哈希函数或调整大小函数。

[注：我故意只在这里谈论渐近行为，又名“无限大”的收藏。如果你的系列很小，那么只需选择一个具有最小常数的系列。]

来源

2010-11-07 16:41:01

哈希表和列表并排吗？

回答

相关问题