我一直在研究寻找更快的列表替代方法。在一个算法书中，hashtable 似乎是使用分离链接法最快的方法。然后我发现 Java 实现了 hashtable，从我所读的资料来看它似乎也使用了分离链接法。然而，由于存在同步开销，因此建议使用 hashmap 来替代 hashtable。
我的问题是：
hashmap 是否是插入/删除/搜索最快的数据结构？hashmap 的内存使用量表示担忧。其中一篇帖子提到，一个空的 hashmap 占用 300 字节。相比之下，hashtable 是否更加内存高效？hash 函数对于 strings 来说是否都是最有效的？HashMap（或者更可能是HashSet）可能是你的起点。它不是完美的，而且它消耗的内存比如列表等数据结构多，但当你需要快速添加、删除和包含操作时，它应该是你的默认选择。虽然String.hashCode()实现不是最好的哈希函数，但它很快，并且对于大多数目的来说足够好。
正如您所指出的，Hashtable 是完全同步的，因此它取决于您的环境。如果您有许多线程，则 ConcurrentHashMap 将是更好的解决方案。但是您可以查看 Trove4J - 也许它会更适合您的需求。Trove 使用类似于哈希表的链接哈希。
HashMap（我相信HashTable也是）的访问时间为O(1)，因为在put()期间给定值的内部桶放置是通过计算（值的键的哈希）%（总桶数）来确定的。这个O(1)是平均访问时间，但如果许多键哈希到同一个桶中，则访问时间将趋向于O(n)，因为所有值都以链接列表方式放置在同一个桶中并且它们都会增长。
正如你所说，考虑到Hashtable内部同步的开销，我可能会选择HashMap。此外，您可以通过设置其各种参数（如负载因子）来微调Hashmap，从而提供内存优化的手段。我投票支持HashMap...
正如其他人指出的那样，集合（set）可以很好地替代列表（list），但不要忘记列表允许重复元素，而集合则不允许，因此虽然某些操作更快，例如存在性检查，但集合和列表代表了不同问题的解决方案。
首先，我建议使用 HashSet 或 TreeSet（如果排序很重要）。HashMap 将键映射到值，这是不同的。请参考 this discussion 以了解 HashMap 和 Hashtable 之间的区别。自 2007 年以来，我个人从未使用过 Hashtable。
最后，如果您不介意使用第三方库，我强烈推荐看一下 Guava 不可变集合。不可变性自动提供线程安全性和更易于理解的程序。
编辑: 关于效率问题，这是无关紧要的。作为指南，使用最适合您问题的数据结构（就数据结构的抽象概念而言），并选择可用的基本实现。如果您可以证明您的代码存在性能问题，那么您可能会开始考虑使用更高效的东西。这是引号，因为它是一个非常宽泛的定义：我们是在谈论内存效率、计算时间效率、垃圾收集效率还是其他什么？永远不要忘记 代码优化规则。
1. HashMap 是 Java 中实现插入/删除/搜索最快的数据结构之一，HashSet 在插入/删除/搜索方面与 HashMap 一样快，而 ArrayList 在向结尾插入元素时与 HashMap 一样快。
2. Hashtable 不比 HashMap 更节省内存，它们都是通过分离链接来实现的。
3. 这两种数据结构的哈希函数是相同的，但您可以编写一个子类扩展它们，然后重写哈希函数以使其最适合您的应用程序。