ArrayList as key in HashMap

问题:

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;
}

回答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);
    }
}

回答2:

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.

回答3:

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).

回答4:

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;
}

回答5:

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!

回答6:

Sure it possible. I suppose the issue in your put. Try obtain key for bigram, increment it, remove entry with this bigram and insert updated value

回答7:

Please check below my code in order to understand if key is ArrayList in Map and how JVM will do it for inputs: here i write hashCode and equals method for TesthashCodeEquals class.

package com.msq;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class TesthashCodeEquals {
    private int a;
    private int b;

    public TesthashCodeEquals() {
        // TODO Auto-generated constructor stub
    }



    public TesthashCodeEquals(int a, int b) {
        super();
        this.a = a;
        this.b = b;
    }



    public int getA() {
        return a;
    }

    public void setA(int a) {
        this.a = a;
    }

    public int getB() {
        return b;
    }

    public void setB(int b) {
        this.b = b;
    }

    public int hashCode() {

        return this.a + this.b;
    }

    public boolean equals(Object o) {

        if (o instanceof TesthashCodeEquals && o != null) {

            TesthashCodeEquals c = (TesthashCodeEquals) o;

            return ((this.a == c.a) && (this.b == c.b));

        } else
            return false;
    }
}

public class HasCodeEquals {
    public static void main(String[] args) {

        Map<List<TesthashCodeEquals>, String> m = new HashMap<>();

        List<TesthashCodeEquals> list1=new ArrayList<>();
        list1.add(new TesthashCodeEquals(1, 2));
        list1.add(new TesthashCodeEquals(3, 4));

        List<TesthashCodeEquals> list2=new ArrayList<>();
        list2.add(new TesthashCodeEquals(10, 20));
        list2.add(new TesthashCodeEquals(30, 40));


        List<TesthashCodeEquals> list3=new ArrayList<>();
        list3.add(new TesthashCodeEquals(1, 2));
        list3.add(new TesthashCodeEquals(3, 4));



        m.put(list1, "List1");
        m.put(list2, "List2");
        m.put(list3, "List3");

        for(Map.Entry<List<TesthashCodeEquals>,String> entry:m.entrySet()){
            for(TesthashCodeEquals t:entry.getKey()){
                System.out.print("value of a: "+t.getA()+", value of b: "+t.getB()+", map value is:"+entry.getValue() );
                System.out.println();
            }
            System.out.println("######################");
        }

    }
}

.

output:

value of a: 10, value of b: 20, map value is:List2
value of a: 30, value of b: 40, map value is:List2
######################
value of a: 1, value of b: 2, map value is:List3
value of a: 3, value of b: 4, map value is:List3
######################

so this will check the number of objects in List and the values of valriabe in object. if number of objects are same and the values of instance variables is also same then it will consider duplicate key and override the key.

now if i change only the value of object on list3

list3.add(new TesthashCodeEquals(2, 2));

then it will print:

 output
    value of a: 2, value of b: 2, map value is:List3
    value of a: 3, value of b: 4, map value is:List3
    ######################
    value of a: 10, value of b: 20, map value is:List2
    value of a: 30, value of b: 40, map value is:List2
    ######################
    value of a: 1, value of b: 2, map value is:List1
    value of a: 3, value of b: 4, map value is:List1
######################

so that It always check the number of objects in List and the value of instance variable of object.

thanks

回答8:

ArrayList.equals() is inherited from java.lang.Object - therefore equals() on ArrayList is independent of the content of the list.

If you want to use an ArrayList as a map key, you will need to override equals() and hashcode() in order to make two arraylists with the same content in the same order return true on a call to equals() and return the same hashcode on a call to hashcode().

Is there any particular reason you have to use an ArrayList as opposed to say a simple String as the key?

edit: Ignore me, as Joachim Sauer pointed out below, I am so wrong it's not even funny.