An efficient Map of elements with continuous integer keys in Java

Question

Is there a data structure that implements the Map interface and holds an array of elements with continuous integer keys efficiently in Java?

In my view, to achieve best efficiency, it would be equivalent to wrapping an array or ArrayList with an index offset value in a Map interface, or a hash table with the hash function f(key) = key - offset and a minimum backing array.

I know this is quite simple but I don't want to reinvent the wheels. Is there such a data structure in JDK? Or is there a library that provides an implementation?

Can you show an example for 'an array of elements with continuous integer keys'? What would such a class look like? — , Mar 21 '19 at 11:50
I am not sure just how more "efficient" this solution gets, assuming hash map are O(1) already. and if you you use integer as keys, there is negligible overhead in the hashcode — Sharon Ben Asher, Mar 21 '19 at 11:50
@LutzHorn Like a series of objects with ID fields, and such IDs are continuous. — Shreck Ye, Mar 21 '19 at 11:53
@SharonBenAsher `HashMap` has a built in hash function which can't be modified. It may cause waste of memory or hash collision depending on the hash function. And when a hash collision occurs, it goes more than O(1). — Shreck Ye, Mar 21 '19 at 11:55
What efficiency do you exactly want? space or execution or both? — Laksitha Ranasingha, Mar 21 '19 at 12:04
@ShreckYe, `HashMap` uses `Object.hashcode()` to determine hash value of key. [`hashcode()` of `Integer`](https://docs.oracle.com/javase/7/docs/api/java/lang/Integer.html#hashCode()) returns the primitive value "as is". from there, it is just a matter of declaring the map with sufficient capacity, and you have real O(1) access. — Sharon Ben Asher, Mar 21 '19 at 12:04
@SharonBenAsher Yeah but in your case it wastes space. Actually there is a second hash function inside `HashMap` so the memory offset is not the `Integer` itself. See this: [What hashing function does Java use to implement Hashtable class?](https://stackoverflow.com/questions/9364134/what-hashing-function-does-java-use-to-implement-hashtable-class) — Shreck Ye, Mar 21 '19 at 12:08
Voilà: https://ideone.com/MTXAso (I can not guarantee that it will work, correctly) — Lino, Mar 21 '19 at 12:08
@ShreckYe, I am not sure about the space consumption of HashMap. regarding the "seconf hash function" - that is why I said it all depends on the initial capacity. if it is set correctly, you will never have collision — Sharon Ben Asher, Mar 21 '19 at 12:12
@Lino Yeah I think this is exactly what I want, but is there a library? — Shreck Ye, Mar 21 '19 at 12:12
@ShreckYe see the linked post, there are some suggestions which you may want to use — Lino, Mar 21 '19 at 12:13
@ShreckYe efficiency gain you could get is subjective (hash function, type of data, number of items etc). However, there are alternative implementations of Map interface. For example, have a look at https://bitbucket.org/trove4j/trove, it does best effort to use primitives rather than wrappers. — Laksitha Ranasingha, Mar 21 '19 at 12:16

score 1 · Accepted Answer · answered Mar 22 '19 at 13:31

If you don't need to support updates (which would make your problem a lot harder), consider passing in an IntFunction<T> to specify the mapping instead of a Map<Integer,T>

When you have a Map, you can pass map::get, and when you don't have a map, you have a lots of easy ways to specify a mapping. For example, you can use a lambda to define a simple mapping function like:

IntFunction<T> mapper = v -> {
    if (v < offset || v >= offset+array.length)
        return null;
    return array[v-offset];
}

score 0 · Answer 2 · answered Mar 26 '19 at 06:39

0

if you are looking for the keys to be sorted, then you can use the SortedMap interface in java https://www.geeksforgeeks.org/sortedmap-java-examples/

answered Mar 26 '19 at 06:39

Chandra Mohan G

26
2

`SortedMap` is just an interface. I am looking for an implementation. Surely as you mentioned it can implement `SortedMap`. – Shreck Ye Mar 26 '19 at 09:06

An efficient Map of elements with continuous integer keys in Java

2 Answers2