java哪种方法最好？

Question

需求

1. 有一个给定的 Map<String, String>
2. 百分比编码每个键/值条目
3. 按编码键排序条目
4. 将它们作为单个字符串添加 ?a=b&c=d

方法1

1. 准备一个TreeMap.
2. 将这些编码的键/值条目放入此映射.
3. 迭代映射时连接输出字符串.

方法2

1. 准备ArrayList预测大小(source-map.size*2)
2. 在找到正确的位置时插入这些编码键/值
3. 迭代列表时连接输出字符串

方法3

1. 准备一个 LinkedList
2. 在找到正确的位置时插入这些编码键/值
3. 迭代列表时连接输出字符串

哪种方法最好？

Answer 1

渐近复杂度,n是键值对的数量:

方法1:O(n log n)

方法2:O(n ^ 2)

方法3:O(n ^ 2)

对于相当大的n,第一种方法将比其他方法更快,但是当键很少时,其他方法可能更快.