0

我想存储我的数据，以便我在多个位置（每个位置都是一个对象）与一个城市（一个字符串）之间建立关系。我对数据结构感到困惑。

我应该去：

Map<String, List<Location>> data = new HashMap<String, List<Location>>

或者

Map<String, List<Location>> data = new TreeMap<String, List<<Location>>

哪一个最适合我的要求。我知道 Hash 和 Tree 如何在数据结构中工作，但不确定它是如何在 Java 中实现的。

如果有任何更好的方法可用，那么不介意这样做。

4

3 回答 3

2

如果您需要非常快速（恒定）的操作（查找、添加、删除）并且不关心映射键的有序迭代，请使用哈希映射。如果您想要快速（对数）操作但又想要按排序顺序迭代映射键，请使用树形映射。

于 2013-10-20T14:44:19.760 回答
0

使用 Guava 的Multimap怎么样。在评论部分和上面的@Justing 中提到了哪个实现。这非常有用，因为您提到手动操作有一些缺点（您需要检查密钥列表是否存在等）。

于 2013-10-20T14:46:41.367 回答
0

TreeMap 使用平衡二叉搜索树数据结构（红黑树），它使用 O(log n) 成本来查找、插入和删除数据。然而，另一方面 HashMap 会带来以下成本：

此实现为基本操作（get 和 put）提供恒定时间性能，假设哈希函数将元素正确地分散在桶中。HashMap 的实例有两个影响其性能的参数： 初始容量和负载因子。作为一般规则，默认负载因子 (.75)在时间和空间成本之间提供了良好的折衷。较高的值会减少空间开销但会增加查找成本（反映在 HashMap 类的大部分操作中，包括get和put）。在设置其初始容量时，应考虑映射中的预期条目数及其负载因子。因为，当哈希表中的条目数超过负载因子和当前容量的乘积时，对哈希表进行重新哈希处理。所以要尽量减少rehash操作的次数。如果初始容量大于最大条目数除以负载因子，则不会发生重新哈希操作。

所以我们最好问这个问题：

  1. 我们需要按顺序保存数据吗？如果是，那么我认为我应该使用 TreeMap
  2. 或者我们只需要具有键值关系的映射，然后我会使用 hashmap。

对于您的用例，我认为选择应该是 HashMap。

于 2013-10-20T14:49:47.110 回答