java - 快速静态键值映射

Question

我有一组唯一的键值对，键和值都是字符串。对的数量非常庞大，找到某个字符串的值非常耗时。

这些对是预先计算的，并为某个程序给出。所以我可以写一个方法包含:

public String getValue(String key)
{
    //repeat for every pair
    if(key.equals("abc"))
    {
        return "def";
    }
}

但我说的是超过 250,000 对，也许对它们进行排序会更快......

我有一个包含 getValue() 方法的类，可以使用它的构造函数，但没有连接到任何数据库/文件系统等。所以每一对都必须在类中定义.

您有什么想法可以比大量的 if 语句更快吗？也许使用一个排序映射来对这些对进行预排序。也许通过反序列化已创建的 map 来缩短构造时间？

我希望您的答案包含您的方法的基本代码示例，我将评论答案及其对应的时间，它花费了一组对!

时间范围:1 次构造函数调用和 20 次 getValue() 调用 1000 毫秒。

键的大小为 256，值的大小为 < 16

Answer 1

这正是一个hash table是为了。它提供了O(1) lookup 如果实现正确，这意味着只要你有足够的内存并且你的散列函数和碰撞策略很聪明，它可以在恒定时间内获取键的值。 Java 有多个哈希支持的数据结构，从事物的声音来看 HashMap<String, String>会帮你解决问题的。

你可以这样构造它:

 Map<String, String> myHashTable = new HashMap<String, String>();

像这样添加值:

 myHashTable.put("abcd","value corresponding to abcd");

并像这样获取键的值:

myHashTable.get("abcd");

当您直觉遍历所有键并检查效率不高时，您就走在了正确的轨道上，那将是 O(n)运行时方法，因为您必须运行所有 n元素。