CODEWITHSUNDEEP
javaandroidcollections
MLProgrammer-CiM
MLProgrammer-CiM

Reputation: 17257

Collection with access by both ordinality and key lookup

What I am after is a default unordered collection backed by an array or arraylist that allows by-key lookup. Or an associative map that can be traveled ordered by insertion time.

The case is as follows, I have an adapter that moves through the collection via position, and insertion is like a list, but at the same time I would like to change individual elements finding them by key instead of iterating through the whole list.

What I don't want is to have to reimplement a whole Collection from scratch, or intercept the calls for another, because that's bound to error.

Upvotes: 0

Views: 100

Answers (4)

MLProgrammer-CiM
MLProgrammer-CiM

Reputation: 17257

Based on @aa333 comment I whipped up my own implementation, it's probably incomplete so suggestions are welcome.

https://gist.github.com/anonymous/7a93535a3cfb63623a54

It passes this Q&D test cases:

public static void main(String[] args) {
    Map<String, String> preMap = new HashMap<String, String>();
    preMap.put("subZero", "-1");
    preMap.put("zero", "0");
    IterableLinkedMap<String, String> map = new IterableLinkedMap<String, String>();
    map.putAll(preMap);
    map.put("one", "1");
    map.put("two", "2");
    map.put("three", "3");
    map.put("four", "4");
    map.put("five", "5");
    map.put("six", "6");
    map.remove("three");
    map.put("eight", "8");
    map.put("seven", "7");
    map.remove("one");
    map.put("three", "33");
    map.put("five", "actually five");
    for (int i = 0; i < map.size(); i++){
        System.out.println(map.getPosition(i));
    }
    map.clear();
    System.out.println(map.getPosition(0));
}

Results:

0
-1
2
4
actually five
6
8
7
33
null

Upvotes: 0

Louis Wasserman
Louis Wasserman

Reputation: 198321

If you need O(1) indexed lookup as well as O(1) lookup by key, you could do it if you don't need to put new entries into the map, only building the map once (though possibly modifying the entries in the map), with Guava's ImmutableMap, which also preserves insertion order. Like a normal Map, you can do lookups by key, and you can also do map.values().asList().get(i), which gets out an element in constant time. I don't believe there's anything built into the JDK that does both, however.

Upvotes: 0

aa333
aa333

Reputation: 2576

LinkedHashMap is your best bet.

It works like a HashMap that has a doubly linked list running through its Map.Entry items. You can use the list for iteration and being a HashMap it will give you O(1) lookups.

You can chose insertion order or access order.

Upvotes: 3

Jigar Joshi
Jigar Joshi

Reputation: 240948

LinkedHashMap will give you close to O(1) with insertion order

Upvotes: 1

Related Questions