Is there an array based Map implementation?

Question

As far as I'm aware of, the only Map implementation in the Java Collections API that orders its entries by insertion order is the LinkedHashMap, which maintians a linked list.

Why is there no something like ArrayMap that uses an array or ArrayList internally? Does the differences that separates ArrayList and LinkedList no longer matter in a Map? Or am I missing something that makes this data structure in general a bad idea? And if that is the case, is LinkedHashMap my only option for Map implementation within the Java standard library if I want insertion order?

You could write a version that uses arrays to order its contents. What possible advantage do you foresee that having? — khelwood
– khelwood, Commented Mar 25, 2019 at 8:45
Why would using an ArrayList internally guaranteee ordering by insertion order? Which is that that you want? ArrayList internally? if so, why? Insertion order? If so, why not LinkedHashMap? — user207421
– user207421, Commented Mar 25, 2019 at 8:59
@user207421 because a List is supposed to guarantee insertion order. I'm just curious if there are ArrayList and LinkedList, why not in Map? Does the differences of the data structures no longer matter for a Map? — Eric
– Eric, Commented Mar 25, 2019 at 16:35

displayName · Accepted Answer · 2019-03-26 04:54:45Z

1

A HashMap is already an array-based data structure. When you insert an entry, the key is hashed, and the exact index is computed by compressing the hash. The entry is then put at that index.

The extra part needed to make a LinkedHashMap from a HashMap is that the Entry of a LinkedHashMap contains a previous and next pointer as well.

Making an array based LinkedHashMap will require moving all the entries back by one index to create space for the new entry in the front, effectively making it an O(n) operation, which is happening in O(1) with the current implementation.

answered Mar 26, 2019 at 4:54

displayName

14.4k9 gold badges65 silver badges77 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Matt Timmermans · Accepted Answer · 2019-03-26 01:12:27Z

0

The Map interface exposes the Map.Entry objects for each entry in the map. That forces Map implementations to actually have those objects, which are then easy to link together into a doubly-linked list.

Also, when an entry is removed from the map, it needs to be removed from wherever it is in the insertion-order list, which is more efficient in a linked structure than it is in an array if you do it in the obvious way.

Both of those things are fixable, and it would be possible to make a Map that maintains insertion order backed by an array, but it would be a bit more complicated and there's no advantage to it.

answered Mar 26, 2019 at 1:12

Matt Timmermans

60.9k3 gold badges57 silver badges106 bronze badges

Collectives™ on Stack Overflow

Is there an array based Map implementation?

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related