How to create a HashMap with two keys (Key-Pair, Value)?
Solution 1
There are several options:
2 dimensions
Map of maps
Map<Integer, Map<Integer, V>> map = //...
//...
map.get(2).get(5);
Wrapper key object
public class Key {
private final int x;
private final int y;
public Key(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Key)) return false;
Key key = (Key) o;
return x == key.x && y == key.y;
}
@Override
public int hashCode() {
int result = x;
result = 31 * result + y;
return result;
}
}
Implementing equals()
and hashCode()
is crucial here. Then you simply use:
Map<Key, V> map = //...
and:
map.get(new Key(2, 5));
Table
from Guava
Table<Integer, Integer, V> table = HashBasedTable.create();
//...
table.get(2, 5);
Table
uses map of maps underneath.
N dimensions
Notice that special Key
class is the only approach that scales to n-dimensions. You might also consider:
Map<List<Integer>, V> map = //...
but that's terrible from performance perspective, as well as readability and correctness (no easy way to enforce list size).
Maybe take a look at Scala where you have tuples and case
classes (replacing whole Key
class with one-liner).
Solution 2
When you create your own key pair object, you should face a few thing.
First, you should be aware of implementing hashCode()
and equals()
. You will need to do this.
Second, when implementing hashCode()
, make sure you understand how it works. The given user example
public int hashCode() {
return this.x ^ this.y;
}
is actually one of the worst implementations you can do. The reason is simple: you have a lot of equal hashes! And the hashCode()
should return int values that tend to be rare, unique at it's best. Use something like this:
public int hashCode() {
return (X << 16) + Y;
}
This is fast and returns unique hashes for keys between -2^16 and 2^16-1 (-65536 to 65535). This fits in almost any case. Very rarely you are out of this bounds.
Third, when implementing equals()
also know what it is used for and be aware of how you create your keys, since they are objects. Often you do unnecessary if statements cause you will always have the same result.
If you create keys like this: map.put(new Key(x,y),V);
you will never compare the references of your keys. Cause everytime you want to acces the map, you will do something like map.get(new Key(x,y));
. Therefore your equals()
does not need a statement like if (this == obj)
. It will never occure.
Instead of if (getClass() != obj.getClass())
in your equals()
better use if (!(obj instanceof this))
. It will be valid even for subclasses.
So the only thing you need to compare is actually X and Y. So the best equals()
implementation in this case would be:
public boolean equals (final Object O) {
if (!(O instanceof Key)) return false;
if (((Key) O).X != X) return false;
if (((Key) O).Y != Y) return false;
return true;
}
So in the end your key class is like this:
public class Key {
public final int X;
public final int Y;
public Key(final int X, final int Y) {
this.X = X;
this.Y = Y;
}
public boolean equals (final Object O) {
if (!(O instanceof Key)) return false;
if (((Key) O).X != X) return false;
if (((Key) O).Y != Y) return false;
return true;
}
public int hashCode() {
return (X << 16) + Y;
}
}
You can give your dimension indices X
and Y
a public access level, due to the fact they are final and do not contain sensitive information. I'm not a 100% sure whether private
access level works correctly in any case when casting the Object
to a Key
.
If you wonder about the finals, I declare anything as final which value is set on instancing and never changes - and therefore is an object constant.
Solution 3
You can't have an hash map with multiple keys, but you can have an object that takes multiple parameters as the key.
Create an object called Index that takes an x and y value.
public class Index {
private int x;
private int y;
public Index(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public int hashCode() {
return this.x ^ this.y;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Index other = (Index) obj;
if (x != other.x)
return false;
if (y != other.y)
return false;
return true;
}
}
Then have your HashMap<Index, Value>
to get your result. :)
Solution 4
Implemented in common-collections MultiKeyMap
Solution 5
Use a Pair
as keys for the HashMap
. JDK has no Pair, but you can either use a 3rd party libraray such as http://commons.apache.org/lang or write a Pair taype of your own.
Crocode
Updated on February 09, 2022Comments
-
Crocode over 2 years
I have a 2D array of Integers. I want them to be put into a HashMap. But I want to access the elements from the HashMap based on Array Index. Something like:
For A[2][5],
map.get(2,5)
which returns a value associated with that key. But how do I create a hashMap with a pair of keys? Or in general, multiple keys:Map<((key1, key2,..,keyN), Value)
in a way that I can access the element with using get(key1,key2,...keyN).EDIT : 3 years after posting the question, I want to add a bit more to it
I came across another way for
NxN matrix
.Array indices,
i
andj
can be represented as a singlekey
the following way:int key = i * N + j; //map.put(key, a[i][j]); // queue.add(key);
And the indices can be retrevied from the
key
in this way:int i = key / N; int j = key % N;
-
BeeOnRope over 11 yearsOnly use a map of maps if you don't care about performance or memory use here (i.e, the map is small), or there are many keys with the same first index - since this solution means paying the overhead of a HashMap object for every single unique first index.
-
Pshemo over 11 years
-
Brett over 11 yearsYou need to override
hashCode
andequals
. -
Brett over 11 yearsReally bad idea. Firstly, it's just bad. Secondly, this technique will get copied for other types where different key may get mapped onto the same
String
with hilarious consequences. -
Matthieu almost 10 yearsIt seems to me that
i#j = j#i
wheni == j
so using themin/max
trick won't do. -
user1947415 almost 10 yearsHow to get map.get(2).get(1) and map.get(2).get(3)?
-
user1947415 almost 10 yearsthe hashCode implementation did not differentiate between (2,1) and (1,2)
-
pete over 9 yearsHi, others have x'or the two values when doing hashCode. Why do you use 31? I thought it has something to do with 32-bit integer, but when I think about it it doesn't make sense, because x=1 and y=0 still maps to the same hashcode as x=0 and y=31
-
enrey about 9 years@Matthieu what's the difference between
5#5
and5#5
swapped around? -
Matthieu about 9 years@enrey None. That's what I was pointing out. It really depends on the knowledge you have on your keys.
-
enrey about 9 years@Matthieu aha I see what you mean. I think that what @arutaku meant was when you want
5#3
to have same hash like3#5
, then you use min/max to enforce3#5
in this order. -
Matthieu about 9 years@enrey exactly. Unless the order is important. Again, it's all about the knowledge you have on your keys (order, duplicates, ...)
-
fncomp almost 9 years@pete Joshua Bloch, in Effective Java ch 3. s 9., recommends, "1. Store some constant nonzero value, say, 17, in an int variable called result ...", which works out better collision-wise if it's a prime. See also: stackoverflow.com/questions/3613102/…
-
Crocode about 8 yearsAnother way to do it. (for NxN matrix).
int key = i * N + j;
int i = key / N;
int j = key % N;
-
Ajak6 over 7 yearsThat is a collision. Hashcode does not need to guarantee different value for every different object. @user1947415
-
Roland almost 7 yearsInstead of the Wrapper key object why not use
Map.Entry<K, V>
as the key? -
Atul almost 7 yearsThanks! Would be nice to write how to
put
as well in the answer. -
Joaquin Iurchuk over 6 yearsWhat about
Map<Pair<Key1, Key2>, Value>
? -
xdavidliu almost 6 yearsnote that
hashCode()
can also be implemented with a single line asObjects.hash(x,y)
-
computingfreak over 5 years@Wilson I fixed the link now, waiting for peer review
-
mike rodent almost 5 years@computingfreak seems like a favourable view came through. Hurrah! NB this is the best answer IMHO. Unless you fancy spending hours competing with the expert Apache engineers over some very useful (as ever) but ultimately mundane piece of functionality.