4

我需要一个提供键值映射的数据结构，例如 a Map，但这也允许我基于（int）索引（例如myKey = myDS.get(index)）获取键，而无需遍历数据结构以获取所需的键指数。

我想过使用LinkedHashMap，但我看不到在给定索引处获取密钥的方法。我错过了什么LinkedHashMap吗？或者我可以使用另一种数据结构吗？

编辑：
这不是重复的。另一个问题的正确答案是使用某种SortedMap; 但是，这不是这个问题的正确答案，因为我希望能够Entry通过Integer索引从数据结构中检索一个，这在任何 Java 库中都不支持。

4

5 回答 5

5

LinkedHashMap提供了接口的哈希表/双向链表实现Map。由于 it extends HashMap，它仍然由一个数组支持，但还有一个Entry对象的双向链表，以确保迭代顺序是可预测的。

所以，基本上这意味着当你像这样遍历地图时：

for (Map.Entry<keyType,valueType>> entry : linkedHashMap.entrySet())
{
   System.out.println("Key: " + entry.getKey().toString() + 
                     " Value: " + entry.getValue.toString());
}

它将按照您添加键的顺序打印，而不是未链接的 Map，它不会按插入顺序打印。您不能随意访问数组的元素，因为支持散列的数组不是 in order。只有双向链表是有序的。

解决方案：

您正在寻找的是来自 Apache Commons的LinkedMap 。

于 2013-08-11T04:31:05.443 回答
2

AFAIK, there is no single data structure that will do this. There is certainly not one in the standard Java collection suite.

Also LinkedHashMap is not the solution because you cannot efficiently index a LinkedHashMap.

If you want to do index-based lookup as well as keep-based lookup, solution needs to be a combination of two data structures.

  • A Map<Key, Value> and an ArrayList<Value> is the simpler approach, but it has a couple of problems: - Insertion and deletion of values from the ArrayList is expensive, unless you are inserting / deleting at the tail end of the list. - Insertion and deletion makes the list positions unstable,.

  • If you want stable indexes and scalable insertion and deletion, then you need a Map<Key, Value> and a Map<Integer, Value> ... and a way to manage (i.e. recycle) the index values.

The Apache Commons LinkedMap class is a possible solution, except that it suffers from the problem that index values are not stable in the face of insertions and deletions.

于 2013-08-11T04:46:38.220 回答
1

如何使用：

Map<String, String> map = new LinkedHashMap<String, String>();
List<Entry<String, String>> mapAsList = new ArrayList<Map.Entry<String,String>>(map.entrySet());

 mapAsList.get(index);
于 2013-08-11T03:21:20.567 回答
0

标准 Java Collections API 中没有直接的 DS 来提供索引映射。但是，以下内容应该可以让您获得结果：

// An ordered map
Map<K, V> map = new LinkedHashMap<K, V>();
// To create indexed list, copy the references into an ArrayList (backed by an array)
List<Entry<K, V>> indexedList = new ArrayList<Map.Entry<K, V>>(map.entrySet());
// Get the i'th term
<Map.Entry<K,V>> entry = indexedList.get(index);
K key = entry.getKey();
V value = entry.getValue();

您可能仍希望将地图中的数据持久性问题与检索分开。

更新：或者按照史蒂夫的建议使用来自 Apache Commons 的 LinkedMap。

于 2013-08-11T04:37:33.980 回答
0

我不相信有这样的集合；集合要么基于您想知道元素的确切位置（列表） ，要么基于某些键或标准（地图）快速访问的想法；两者都做将非常耗费资源来维护。

当然，正如火箭男孩的回答所暗示的那样，你可以做这样的事情，但我猜这并不是真的可以提高效率。

于 2013-08-11T04:03:19.783 回答