java 哪种方法最好？

Question

要求

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

方法 1

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

方法 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，第一种方法将比其他方法更快，但当键很少时，其他方法可能会更快。