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

假设我需要从以下位置进行映射String为一个整数。整数是唯一的，并且形成从0开始的连续范围。即：

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

至少有两种简单的方法可以做到这一点。使用哈希图：

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 and HashMap实施使？

第三种选择可能我最喜欢的是使用trie http://en.wikipedia.org/wiki/Trie:

我打赌它会击败HashMap性能方面（没有冲突+计算哈希码的事实是O(length of string)无论如何），也可能是List在某些情况下（例如，如果您的字符串具有很长的公共前缀，因为 indexOf 会在equals方法）。

在列表和地图之间进行选择时，我会选择Map（例如HashMap）。这是我的推理：

• 可读性

  Map 界面只是为此用例提供了更直观的界面。

• 在正确的地方进行优化

  我想说如果你使用的是List无论如何，你都会针对小情况进行优化。这可能不是瓶颈所在。

第四个选项将使用一个LinkedHashMap，如果尺寸很小，则迭代它，并且get如果尺寸较大，则关联编号。

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