Mapping int to int (in Java)

Question

In Java.

How can I map a set of numbers(integers for example) to another set of numbers? All the numbers are positive and all the numbers are unique in their own set.

The first set of numbers can have any value, the second set of numbers represent indexes of an array, and so the goal is to be able to access the numbers in the second set through the numbers in the first set. This is a one to one association.

Speed is crucial as the method will have to be called many times each second.

Edit: I tried it with SE hashmap implementation, but found it to be slow for my purposes.

Answer 1

There's an article, devoted to this problem (with a solution): Implementing a world fastest Java int-to-int hash map

Code can be found in related GitHub repository. (Best results are in class IntIntMap4a.java )

Citation from the article:

---

Summary

If you want to optimize your hash map for speed, you have to do as much as you can of the following list:

• Use underlying array(s) with capacity equal to a power of 2 - it will allow you to use cheap & instead of expensive % for array index
• Do not store the state in the separate array - use dedicated fields for free/removed keys and values.
• Interleave keys and values in the one array - it will allow you to load a value into memory for free.
• Implement a strategy to get rid of 'removed' cells - you can sacrifice some of remove performance in favor of more frequent get/put.

• Scramble the keys while calculating the initial cell index - this is required to deal with the case of consecutive keys.

  _{Yes, I know how to use citation formatting. But it looks awful and doesn't handle bullet lists well.}

Answer 2

Sounds like HashMap<Integer,Integer> is what you're looking for.

Answer 3

Your requirements can be satisfied by the Map interface. As an example, see HashMap<K,V>.

See Map and HashMap

Answer 4

The structure you are looking for is called an associative array. In computer science, an associative array, map, symbol table, or dictionary is an abstract data type composed of a collection of (key, value) pairs, such that each possible key appears just once in the collection.

In java in particular as already mentioned this is easily done with a HashMap.

HashMap<Integer, Integer> cache = new HashMap<Integer, Integer>();

You can insert elements with the method put

cache.put(21, 42);

and you can retrieve a value with get

Integer key = 21
Integer value = cache.get(key);
System.out.println("Key: " + key +" value: "+ value); 

Key: 21 value: 42

If you want to iterate through data you need to define an iterator:

Iterator<Integer> Iterator = cache.keySet().iterator();

while(Iterator.hasNext()){
  Integer key = Iterator.next();
  System.out.println("key: " + key + " value: " + cache.get(key));
}

Answer 5

If you are willing to use an external library, you can use apache's IntToIntMap, which is a part of Apache Lucene.

It implements a pretty efficient int to int map that uses primitives for tasks that should not suffer the boxing overhead.

Answer 6

If you have a limit for the size of the first list, you can just use a large array. Suppose you know there first list only has numbers 0-99, you can use int[100]. Use the first number as an array index.