从字符串映射到整数 - 各种方法的性能

Question

假设我需要从String一个整数进行映射.整数是唯一的,从0开始形成连续范围.即:

Hello -> 0
World -> 1
Foo   -> 2
Bar   -> 3
Spam  -> 4
Eggs  -> 5
etc.

至少有两种直接的方法可以做到这一点.使用hashmap:

HashMap<String, Integer> map = ...
int integer = map.get(string); // Plus maybe null check to avoid NPE in unboxing.

或者列表:

List<String> list = ...
int integer = list.indexOf(string); // Plus maybe check for -1.

我应该使用哪种方法,为什么？可以说相对性能取决于列表/地图的大小,因为List#indexOf()是使用String#equals()- > O(n)效率的线性搜索,而HashMap#get()使用哈希来缩小搜索范围 - >当地图很大时肯定更有效,但可能更低当只有很少的元素时(计算哈希值必须有一些开销,对吧？).

由于正确地对Java代码进行基准测试非常困难,所以我希望得到一些有根据的猜测.我的推理上面是否正确(列表更适合小型,地图更适合大型)？阈值大小约为多少？有什么区别做各种List与HashMap实现做什么呢？

Answer 1

第三种选择,也许我最喜欢的是使用trie:

                    

我敢打赌它胜过HashMap性能(没有冲突+ O(length of string)无论如何计算哈希代码的事实),并且List在某些情况下也可能是这种方法(例如,如果你的字符串有很长的公共前缀,因为indexOf会浪费很多时间在equals方法中).

在列表和地图之间进行选择时,我会选择Map(例如HashMap).这是我的推理:

• 可读性

  Map界面只是为这个用例提供了更直观的界面.

• 在正确的地方优化

  我会说如果你正在使用a List,那么无论如何你都会针对小案例进行优化.那可能不是瓶颈的位置.

第四种选择是使用a LinkedHashMap,如果大小很小则迭代它,如果大小则get使用相关的数字.

第五种选择是将决策封装在一个单独的类中.在这种情况下,您甚至可以实现它以在列表增长时在运行时更改策略.