java - “散列”比“线性”搜索更有效吗？

Question

我决定修改 Java 集合框架，所以我从内部实现开始。一个问题出现在我的脑海中，我无法解决。希望有人可以对以下内容做出明确的解释。

ArrayList 使用线性或二分搜索（两者都有优点/缺点），但我们可以用它们做任何事情！我的问题是为什么所有“散列”类（如 HashMap fe）都使用散列原理？例如，他们不能解决线性或二分搜索吗？为什么不将键/值对存储在数组中？相反，为什么不（例如 ArrayList 存储在 hashTable 中）？

标签： javahashcollections

Answer 1

集合框架的目的是程序员将选择适合用例的数据结构。根据您使用它的目的，不同的数据结构是合适的。

正如您所说，散列类使用散列原理，因为如果您选择它们​​，那么这就是您想要使用的。（散列通常是简单、直接查找的最佳选择。）螺丝刀使用拧螺丝原理，因为如果你拿起螺丝刀，你想把东西拧进去；如果你有钉子需要钉进去，你就会拿起锤子。

但是，如果您不打算执行查找，或者如果线性搜索对您来说足够好，那么 anArrayList就是您想要的。将哈希表添加到永远不会使用它的集合中是不值得的，并且它会花费 CPU 和内存来执行您不需要的事情。