我有一组唯一的键值对,键和值都是字符串。对的数量非常庞大,找到某个字符串的值非常耗时。
这些对是预先计算的,并为某个程序给出。所以我可以写一个方法包含:
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
最佳答案
这正是一个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
元素。
关于java - 快速静态键值映射,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22146764/