ArrayList as key in HashMap

Question

Would it be possible to add an ArrayList as the key of HashMap. I would like to keep the frequency count of bigrams. The bigram is the key and the value is its frequency.

For each of the bigrams like "he is", I create an ArrayList for it and insert it into the HashMap. But I am not getting the correct output.

public HashMap<ArrayList<String>, Integer> getBigramMap(String word1, String word2) {
    HashMap<ArrayList<String>, Integer> hm = new HashMap<ArrayList<String>, Integer>();
    ArrayList<String> arrList1 = new ArrayList<String>();
    arrList1 = getBigram(word1, word2);
    if (hm.get(arrList1) != null) {
        hm.put(arrList1, hm.get(arrList1) + 1);
    } else {
        hm.put(arrList1, 1);
    }
    System.out.println(hm.get(arrList1));
    return hm;
}


public ArrayList<String> getBigram(String word1, String word2) {
    ArrayList<String> arrList2 = new ArrayList<String>();
    arrList2.add(word1);
    arrList2.add(word2);
    return arrList2;
}

Solution 1

Yes you can have ArrayLists as a keys in a hash map, but it is a very bad idea since they are mutable.

If you change the ArrayList in any way (or any of its elements), the mapping will basically be lost, since the key won't have the same hashCode as it had when it was inserted.

The rule of thumb is to use only immutable data types as keys in a hash map. As suggested by Alex Stybaev, you probably want to create a Bigram class like this:

final class Bigram {

    private final String word1, word2;

    public Bigram(String word1, String word2) {
        this.word1 = word1;
        this.word2 = word2;
    }

    public String getWord1() {
        return word1;
    }

    public String getWord2() {
        return word2;
    }

    @Override
    public int hashCode() {
        return word1.hashCode() ^ word2.hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        return (obj instanceof Bigram) && ((Bigram) obj).word1.equals(word1)
                                       && ((Bigram) obj).word2.equals(word2);
    }
}

Solution 2

Why can't you use something like this:

class Bigram{
    private String firstItem;
    private String secondItem;

    <getters/setters>

    @Override
    public int hashCode(){
        ...
    }

    @Override 
    public boolean equals(){
        ...
    }
}

instead of using the dynamic collection for limited number of items (two).

Solution 3

From the documentation:

Note: great care must be exercised if mutable objects are used as map keys. The behavior of a map is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is a key in the map. A special case of this prohibition is that it is not permissible for a map to contain itself as a key. While it is permissible for a map to contain itself as a value, extreme caution is advised: the equals and hashCode methods are no longer well defined on such a map.

You have to take care when you are using mutable objects as keys for the sake of hashCode and equals.

The bottom line is that it is better to use immutable objects as keys.

Solution 4

I've come up with this solution. It is obviously not usable in all cases, for example over stepping the hashcodes int capacity, or list.clone() complications(if the input list gets changed, key stays the same as intended, but when the items of List are mutable, cloned list has the same reference to its items, which would result in changing the key itself).

import java.util.ArrayList;

public class ListKey<T> {
    private ArrayList<T> list;

    public ListKey(ArrayList<T> list) {
        this.list = (ArrayList<T>) list.clone();
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;

        for (int i = 0; i < this.list.size(); i++) {
            T item = this.list.get(i);
            result = prime * result + ((item == null) ? 0 : item.hashCode());
        }
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        return this.list.equals(obj);
    }
}

---------
    public static void main(String[] args) {

        ArrayList<Float> createFloatList = createFloatList();
        ArrayList<Float> createFloatList2 = createFloatList();

        Hashtable<ListKey<Float>, String> table = new Hashtable<>();
        table.put(new ListKey(createFloatList2), "IT WORKS!");
        System.out.println(table.get(createFloatList2));
        createFloatList2.add(1f);
        System.out.println(table.get(createFloatList2));
        createFloatList2.remove(3);
        System.out.println(table.get(createFloatList2));
    }

    public static ArrayList<Float> createFloatList() {
        ArrayList<Float> floatee = new ArrayList<>();
        floatee.add(34.234f);
        floatee.add(new Float(33));
        floatee.add(null);

        return floatee;
    }

Output:
IT WORKS!
null
IT WORKS!

Solution 5

Try this ,this will work.

 public Map<List, Integer> getBigramMap (String word1,String word2){
    Map<List,Integer> hm = new HashMap<List, Integer>();
    List<String> arrList1 = new ArrayList<String>();
    arrList1 = getBigram(word1, word2);     
    if(hm.get(arrList1) !=null){
        hm.put(arrList1, hm.get(arrList1)+1);
    }
    else {
        hm.put(arrList1, 1);
    }

    System.out.println(hm.get(arrList1));
    return hm;
}

View more solutions

Comments

[Joachim Sauer]

Actually ArrayList uses AbstractList.equals() which is implemented just right. In fact every correct List implementation is required to have conforming equals() and hashCode() implementations.

[Joachim Sauer]

Apart from it being mutable, it's probably a good idea to just introduce a Bigram class if that's what he's actually working with.

[Joachim Sauer]

I'd even leave out the setters and make it immutable. There's probably no reason to change objects of that class after construction.

[Stephen C]

+1 - in fact, this probably saves space, since the Bigram class won't have the overhead of a 32-bit length field.

[thetna]

The problem with this is, I am not able to paramaterized the List.Can you please give me idea on it too? Or i should start another thread for it.

[mcfinnigan]

Ah, thanks for the correction. I just did a quick scan of the ArrayList source and didn't bother to go further up - epic fail on my part.

[Joachim Sauer]

Hint: in Eclipse there's Ctrl-O to open an outline dialog, enter equals, see no definition, press Ctrl-O again to see inherited members as well and see that there are actually 4 inherited ones (Object, Collection, List and AbstractList). I'm sure that there are similar shortcuts in other IDEs as well.

[vikiiii]

Using this , you can pass any type of list to the map.List can be of string, integer or User defined object.

[mcfinnigan]

I use IDEA - ^N <classname> - I was lazy :-)

[Javo]

You see how I tested it, for some reason I still find the solution unreliable. Is it valid?