Can an array be used as a HashMap key?

Question

If a HashMap's key is a String[] array:

HashMap<String[], String> pathMap;

Can you access the map by using a newly created String[] array, or does it have to be the same String[] object?

pathMap = new HashMap<>(new String[]{"korey", "docs"}, "/home/korey/docs");
String path = pathMap.get(new String[]{"korey", "docs"});

Frankforter

Answer 1

It will have to be the same object. A HashMap compares keys using equals() and two arrays in Java are equal only if they are the same object.

If you want value equality, then write your own container class that wraps a String[] and provides the appropriate semantics for equals() and hashCode(). In this case, it would be best to make the container immutable, as changing the hash code for an object plays havoc with the hash-based container classes.

EDIT

As others have pointed out, List<String> has the semantics you seem to want for a container object. So you could do something like this:

HashMap<List<String>, String> pathMap;

pathMap.put(
    // unmodifiable so key cannot change hash code
    Collections.unmodifiableList(Arrays.asList("korey", "docs")),
    "/home/korey/docs"
);

// later:
String dir = pathMap.get(Arrays.asList("korey", "docs"));

Gitlow

I think it also uses hashCode() to determine the hash of an object. – Mural

@Mural - Indeed. And two arrays are unlikely to have the same hash code. However, this is not a requirement for any Java implementation. In any case, two references with the same hashCode() are then compared using equals() to determine if they are the same key. – Gitlow

@TedHopp I decided to use your suggestion to make a container class. Thanks! – Frankforter

@KoreyHinton - You're welcome. :) Before doing that, though, check whether List does what you need. See my edited answer. – Gitlow

@TedHopp Cool I just now saw your edit, thanks for showing a working example! – Frankforter

This all sounded very promising, but when I try to do containsKey I get a ClassCastException: java.util.Collections$UnmodifiableList cannot be cast to java.lang.Comparable, still researching... – Schedule

@MarkBennett - Weird. AFAIK HashMap.containsKey does not require keys to implement Comparable. It only relies on hashCode() and equals(). Something else must be going on in your code. – Gitlow

Note that the collection returned by Collections.unmodifiableList(List) is not immutable--if the underlying list is later modified, the hashcode of the unmodifiable list wrapping it will change. So the call to Collections.unmodifiableList protects the keys from modification by, for example, a malicious or misguided consumer iterating the keyset and modifying keys, but if the underlying list used as a key could later change, defensive copying is also necessary. – Coen

@TheodoreMurdock - Good point. The usual idiom for using Collections.unmodifiableList(List) is to not keep a reference to the argument (as in my sample code), so this usually isn't a problem. It's only when the argument is separately modifiable (through a separate reference) that things can get messed up. – Gitlow

The question would be then: Is there a suitable container class that will wrap an array and provide the needed hasCode() and equals()? It looks like a very generic thing. – Hefner

@FlorianF - You mean for an array of mutable objects? I think an identity hash is the only sensible approach in that case. If the hash code for key objects can change dynamically, a hash-based data structure is unsuitable right from the start. – Gitlow

Answer 2

No, but you can use List<String> which will work as you expect!

Pericarditis

This works with a caveat. If you're going to use a List<String> as a key in a hash-based collection, the list should be unmodifiable. If the hash code for an object changes while the object is being used as a key in a hash-based collection, the collection generally breaks. – Gitlow

List is an interface, and there no guarantee that an implementation properly overrides equals and hashCode – Lavinia

@SteveKuo - Yes there is. The documentation for List requires any implementation to use a specific semantics for equals() and hashCode(). The required semantics matches what OP seems to want. – Gitlow

Indeed, the AbstractList class which is the superclass all list implementations inherit from overrides both hashCode() and equals() methods, so that the element-wise comparison, rather than reference comparison, is reflected. – Wooded

Answer 3

Arrays in Java use Object's hashCode() and don't override it (the same thing with equals() and toString()). So no, you cannot shouldn't use arrays as a hashmap key.

Narvik

You can use them as a key, it will just use whatever Object does for its hashCode... Not what he wants, but nothing stopping you from doing it. – Boddie

Answer 4

You cannot use a plain Java Array as a key in a HashMap. (Well you can, but it won't work as expected.)

But you could write a wrapper class that has a reference to the Array and that also overrides hashCode() and equals().

Mural

No need write a new array wrapper class, one already exists - ArrayList – Lavinia

@SteveKuo Yes, indeed. But maybe you want to write your own, since ArrayList is mutable and the array underneath can be replaced internally without you noticing it. – Mural

@Mural - One can always use Collections.unmodifiableList(someList) to turn a List into an immutable object. – Gitlow

@TedHopp: an unmodifiableList is not an immutable one.You still can modify the source list directly. – Flue

@Flue - Yes, you are correct. This was pointed out in this comment to my own answer above. See also my response to that comment. – Gitlow

Answer 5

In most cases, where the Strings inside your array are not pathological and do not include commas followed by a space, you can use Arrays.toString() as a unique key. i.e. your Map would be a Map<String, T>. And the get/put for an array myKeys[] would be

T t = myMap.get(Arrays.toString(myKeys));

myMap.put(Arrays.toString(myKeys), myT);

Obviously you could put in some wrapper code if desired.

A nice side effect is that your key is now immutable. Of course, of you change your array myKeys and then try a get(), you won't find it.

Hashing of Strings is highly optimized. So my guess is that this solution, though it feels a bit slow and kludgy, will be both faster and more memory efficient (less object allocations) than @Ted Hopp solution using an immutable List. Just think about whether Arrays.toString() is unique for your keys. If not, or if there is any doubt, (e.g. the String[] comes from user input) use the List.

Heman

Answer 6

Like said you need a wrapper class around your array which overrides equality and hashCode.

e.g.

/** 
 * We can use this instance as HashKey,
 * the same anagram string will refer the same value in the map.
 */
class Anagram implements CharSequence {

    private final char[] anagram;

    public Anagram(String anagram) {

        this.anagram = anagram.toCharArray();
        Arrays.sort(this.anagram);
    }

    @Override
    public boolean equals(Object o) {

        if (this == o) {
            return true;
        }
        if (o == null || getClass() != o.getClass()) {
            return false;
        }
        Anagram that = (Anagram) o;
        return Arrays.equals(this.anagram, that.anagram);
    }

    @Override
    public int hashCode() {

        return Arrays.hashCode(this.anagram);
    }

    @Override
    public int length() {

        return anagram.length;
    }

    @Override
    public char charAt(int index) {

        return anagram[index];
    }

    @Override
    public CharSequence subSequence(int start, int end) {

        return new String(anagram).subSequence(start, end);
    }

    @Override
    public String toString() {

        return Arrays.toString(anagram);
    }
}

Otherwise declare your map as IdentityHashMap, then the user knows we need to use the same instance for your CRUD.

Elkins

Answer 7

Ted Hopp is right it will have to be same object.

For information see this example:

public static void main(String[] args) {
    HashMap<String[], String> pathMap;
    pathMap = new HashMap<String[], String>();
    String[] data = new String[]{"korey", "docs"};
    pathMap.put(data, "/home/korey/docs");
    String path = pathMap.get(data);
    System.out.println(path);
}

When you run the above code, it will print "docs".

Distrait

LOL, thats because you use the same object as key, try to use same array but new created. – Urania

Answer 8

Since Java 9, you can use Arrays::compare method as a comparator for TreeMap that compares the contents of arrays.

Map<String[], String> map = new TreeMap<>(Arrays::compare);

String[] key1 = {"one", "two"};
String[] key2 = {"one", "two"};
String[] key3 = {"one", "two"};

map.put(key1, "value1");
map.put(key2, "value2");

System.out.println(map.size()); // 1
System.out.println(map.get(key1)); // value2
System.out.println(map.get(key2)); // value2
System.out.println(map.get(key3)); // value2

---

^{See also: How to make a Set of arrays in Java?}

Handcar

Answer 9

A running example using the Arrays utility and the hash code it provides:

String[] key1 = { "korey", "docs" };
String value1 = "/home/korey/docs";
HashMap<Integer, String> map = new HashMap<Integer, String>();
map.put(Arrays.hashCode(key1), value1);
System.out.println(map);

{-1122550406=/home/korey/docs}

This approach is useful if your focus is in storing only. Retrieving using the readable (original) key is simple:

String retrievedValue = map.get(Arrays.hashCode(key1));
System.out.println(retrievedValue);

/home/korey/docs

Levenson

The problem with this approach is that it cannot deal with hash collision when 2 string[] has the same hashCode under Arrays.hashCode(). – Wooded