在Java中查找键值对的最快、最有效的方法是什么？

Question

免责声明：
本问题不旨在争论！

什么是最快和最省内存的搜索键值对的方法？我将以键值对的方式存储项目，并且需要快速访问它们。我应该使用SQLite数据库吗？映射表？哈希表？ HashMap？请提供使用任何搜索方法的优缺点。

- Mohit Deshpande

Answer 1

任何基于哈希的Map结构都是不错的选择，只要你的关键字hash function效率高。在搜索时，您可以使用值ID作为查找结果以节省内存。

如果您的数据已经在数据库中，则可以完全将此搜索留给RDBMS，毕竟它们就是为这些事情而生的。

- Esko

Answer 2

如果你的数据在内存中，Map通常是你的好伙伴 - 它们就是为此而设计的。

然而，不要使用Hashtable。它比新的Map实现慢得多，因为它的方法是同步的，而大多数情况下并不需要同步（当需要同步时，有一种更好的替代方案 - 请参见下文）。

在单线程上下文中，HashMap可能会很好用。

如果你需要线程安全，请使用ConcurrentHashMap。

- Péter Török

---

HashTable不是同步的，在单线程环境中比ConcurrentHashMap更快，因为它没有任何锁定！如果对映射的访问是多线程的，ConcurrentHashMap确实是最好的解决方案。 - Tobias P.

@Tobias，“与新的集合实现不同，Hashtable是同步的”-来自http://java.sun.com/j2se/1.5.0/docs/api/java/util/Hashtable.html - Péter Török

既然我们在谈论语义学……“ConcurrentHashMap的实现在几乎所有情况下都比HashMap表现更好。它还允许同时并发读写，并且具有支持常见复合操作的方法，否则这些操作是不安全的。如果Java 5是部署环境，请从ConcurrentHashMap开始。”《代码整洁之道》, 罗伯特·C.马丁, 第183页 - Esko

@Esko，好发现，我没想起来 :-) 然而，差异似乎是微不足道的。《Java Generics and Collections》第16.4.1章节说：“忽略锁定开销，例如刚才描述的那些，ConcurrentHashMap 操作的成本与 HashMap 相似。” 它建议在单线程使用时使用 HashMap。 - Péter Török

啊，我说的是HashMap而不是HashTable，它没有同步，因此是单线程环境下最好的解决方案。《Java并发实践》也建议在不需要锁定时使用非锁定集合。 - Tobias P.

这是一本@Esko在参考的好书。对于喜欢构建灵活代码的任何人来说，值得一看。 - nckbrz