How to make HashMap work with Arrays as key?
Solution 1
You cannot do it this way. Both t
and a
will have different hashCode()
values because the the java.lang.Array.hashCode()
method is inherited from Object
, which uses the reference to compute the hash-code (default implementation). Hence the hash code for arrays is reference-dependent, which means that you will get a different hash-code value for t
and a
. Furthermore, equals
will not work for the two arrays because that is also based on the reference.
The only way you can do this is to create a custom class that keeps the boolean
array as an internal member. Then you need to override equals
and hashCode
in such a way that ensures that instances that contain arrays with identical values are equal and also have the same hash-code.
An easier option might be to use List<Boolean>
as the key. Per the documentation the hashCode()
implementation for List
is defined as:
int hashCode = 1;
Iterator<E> i = list.iterator();
while (i.hasNext()) {
E obj = i.next();
hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
}
As you can see, it depends on the values inside your list and not the reference, and so this should work for you.
Solution 2
It is not possible to do this with arrays, as any two different arrays don't compare equals
, even if they have the same elements.
You need to map from container class, for example ArrayList<Boolean>
(or simply List<Boolean>
. Perhaps BitSet
would be even more appropriate.
Solution 3
Map
implementations relies on key's equals
and hashCode
methods. Arrays in java are directly extends from Object
, they use default equals
and hashCode
of Object
which only compares identity
.
If I were you, I would create a class Key
class Key {
private final boolean flag1;
private final boolean flag2;
public Key(boolean flag1, boolean flag2) {
this.flag1 = flag1;
this.flag2 = flag2;
}
@Override
public boolean equals(Object object) {
if (!(object instanceof Key)) {
return false;
}
Key otherKey = (Key) object;
return this.flag1 == otherKey.flag1 && this.flag2 == otherKey.flag2;
}
@Override
public int hashCode() {
int result = 17; // any prime number
result = 31 * result + Boolean.valueOf(this.flag1).hashCode();
result = 31 * result + Boolean.valueOf(this.flag2).hashCode();
return result;
}
}
After that, you can use your key with Map
:
Map<Key, Integer> map = new HashMap<>();
Key firstKey = new Key(false, false);
map.put(firstKey, 1);
Key secondKey = new Key(false, false) // same key, different instance
int result = map.get(secondKey); // --> result will be 1
Reference: Java hash code from one field
Solution 4
Problems
As others have said, Java arrays inherit
.hashcode()
and.equals()
from Object, which uses a hash of the address of the array or object, completely ignoring its contents. The only way to fix this is to wrap the array in an object that implements these methods based on the contents of the array. This is one reason why Joshua Bloch wrote Item 25: "Prefer lists to arrays." Java provides several classes that do this or you can write your own usingArrays.hashCode()
andArrays.equals()
which contain correct and efficient implementations of those methods. Too bad they aren't the default implementations!Whenever practical, use a deeply unmodifiable (or immutable) class for the keys to any hash-based collection. If you modify an array (or other mutable object) after storing it as a key in a hashtable, it will almost certainly fail future
.get()
or.contains()
tests in that hashtable. See also Are mutable hashmap keys a dangerous practice?
Specific Solution
// Also works with primitive: (boolean... items)
public static List<Boolean> bList(Boolean... items) {
List<Boolean> mutableList = new ArrayList<>();
for (Boolean item : items) {
mutableList.add(item);
}
return Collections.unmodifiableList(mutableList);
}
ArrayList implements
.equals()
and.hashCode()
(correctly and efficiently) based on its contents, so that everybList(false, false)
has the same hashcode as, and will be equal to every otherbList(false, false)
.Wrapping it in
Collections.unmodifiableList()
prevents modification.
Modifying your example to use bList() requires changing just a few declarations and type signatures. It is as clear as, and almost as brief as your original:
public class main {
public static HashMap<List<Boolean>, Integer> h;
public static void main(String[] args){
List<Boolean> a = bList(false, false);
h = new HashMap<>();
h.put(a, 1);
if(h.containsKey(a)) System.out.println("Found a");
List<Boolean> t = bList(false, false);
if(h.containsKey(t)) System.out.println("Found t");
else System.out.println("Couldn't find t");
}
}
Generic Solution
public <T> List<T> bList(T... items) {
List<T> mutableList = new ArrayList<>();
for (T item : items) {
mutableList.add(item);
}
return Collections.unmodifiableList(mutableList);
}
The rest of the above solution is unchanged, but this will leverage Java's built-in type inference to work with any primitive or Object (though I recommend using only with immutable classes).
Library Solution
Instead of bList()
, use Google Guava's ImmutableList.of()
, or my own Paguro's vec()
, or other libraries that provide pre-tested methods like these (plus immutable/unmodifiable collections and more).
Inferior Solution
This was my original answer in 2017. I'm leaving it here because someone found it interesting, but I think it's second-rate because Java already contains ArrayList and Collections.unmodifiableList() which work around the problem. Writing your own collection wrapper with .equals() and .hashCode() methods is more work, more error-prone, harder to verify, and therefore harder to read than using what's built-in.
This should work for arrays of any type:
class ArrayHolder<T> {
private final T[] array;
@SafeVarargs
ArrayHolder(T... ts) { array = ts; }
@Override public int hashCode() { return Arrays.hashCode(array); }
@Override public boolean equals(Object other) {
if (array == other) { return true; }
if (! (other instanceof ArrayHolder) ) {
return false;
}
//noinspection unchecked
return Arrays.equals(array, ((ArrayHolder) other).array);
}
}
Here is your specific example converted to use ArrayHolder:
// boolean[] a = {false, false};
ArrayHolder<Boolean> a = new ArrayHolder<>(false, false);
// h = new HashMap<boolean[], Integer>();
Map<ArrayHolder<Boolean>, Integer> h = new HashMap<>();
h.put(a, 1);
// if(h.containsKey(a)) System.out.println("Found a");
assertTrue(h.containsKey(a));
// boolean[] t = {false, false};
ArrayHolder<Boolean> t = new ArrayHolder<>(false, false);
// if(h.containsKey(t)) System.out.println("Found t");
assertTrue(h.containsKey(t));
assertFalse(h.containsKey(new ArrayHolder<>(true, false)));
I used Java 8, but I think Java 7 has everything you need for this. I tested hashCode and equals using TestUtils.
Solution 5
You could create a class that contains the array. Implements the hashCode() and equals() methods for that class, based on values:
public class boolarray {
boolean array[];
public boolarray( boolean b[] ) {
array = b;
}
public int hashCode() {
int hash = 0;
for (int i = 0; i < array.length; i++)
if (array[i])
hash += Math.pow(2, i);
return hash;
}
public boolean equals( Object b ) {
if (!(b instanceof boolarray))
return false;
if ( array.length != ((boolarray)b).array.length )
return false;
for (int i = 0; i < array.length; i++ )
if (array[i] != ((boolarray)b).array[i])
return false;
return true;
}
}
You can then use:
boolarray a = new boolarray( new boolean[]{ true, true } );
boolarray b = new boolarray( new boolean[]{ true, true } );
HashMap<boolarray, Integer> map = new HashMap<boolarray, Integer>();
map.put(a, 2);
int c = map.get(b);
System.out.println(c);
gaganbm
I write code for Amazon.com. Have coded in Java, Scala, C, C++, Python, Groovy, Bash, ABAP etc. More here.
Updated on February 22, 2020Comments
-
gaganbm about 4 years
I am using boolean arrays as keys for a HashMap. But the problem is HashMap fails to get the keys when a different array is passed as key, although the elements are same. (As they are different objects).
How can I make it work with arrays as keys ? Here is the code :
public class main { public static HashMap<boolean[], Integer> h; public static void main(String[] args){ boolean[] a = {false, false}; h = new HashMap<boolean[], Integer>(); h.put(a, 1); if(h.containsKey(a)) System.out.println("Found a"); boolean[] t = {false, false}; if(h.containsKey(t)) System.out.println("Found t"); else System.out.println("Couldn't find t"); } }
Both the arrays
a
andt
contain the same elements, but HashMap doesn't return anything fort
.How do I make it work ?