Key not found in a HashMap for a composite object

Question

So, I made my own composite key in Java with 3 members

public class MyOwnKey{
int location;
int length;
String [] tokens;
}

Now I create two objects using the constructor

String [] tokens = "Stackoverflow is great".split("\\s+");
Object key1 = new MyOwnKey(0,0,tokens)
tokens = "Web is great".split("\\s+");
Object key2 = new MyOwnKey(0,0,tokens)

Now, I add the key in HashMap HashMap map = new HashMap(); map.put(key1,1);

Now, this is the problem when I do contains key, it gives false;

**map.containsKey(key2) //returns false whereas it should return true.**

Just so that it makes sense:

key1.equals(key2) returns true

and the hashcode codes are also equal. key1.hashCode() == key2.hashCode().

I have implemeneted my own version of hashCode, toEquals() and toCompare().

Not sure what's the problem.

Here is the code

import java.io.DataOutput;
import java.io.DataInput;
import java.io.IOException;

import org.apache.hadoop.io.WritableComparable;

public class PatternGeneratorKey implements WritableComparable<Object> {


    private String [] tokens;
    int location;
    int length;

    StringBuffer _toString = null;

    public PatternGeneratorKey(){
        tokens = new String[1];
        location =0;
        length=1;
    }

    public PatternGeneratorKey(int location, int length, String [] tokens){

        this.location = location;
        this.length = length;

        this.tokens=  new String[tokens.length];
        for(int i = 0; i < tokens.length;i++){
            this.tokens[i] = tokens[i];
        }

    }

    public int compareTo(Object o) {
        if (!(o instanceof PatternGeneratorKey))
            return -1;
        return this.compareTo((PatternGeneratorKey) o);
    }

    public void write(DataOutput out) throws IOException {

        out.writeInt(tokens.length);
        for(int i = 0; i<tokens.length;i++){
            out.writeUTF(tokens[i]);

        }
        out.writeInt(location);
        out.writeInt(length);
    }

    public void readFields(DataInput in) throws IOException {

        int l = in.readInt();

        tokens = new String[l];
        for(int i = 0; i < l ; i++){
            tokens[i] = in.readUTF();
        }
        location = in.readInt();
        length = in.readInt();
    }

    public int compareTo(PatternGeneratorKey k) {

        if(this.tokens.length - this.length != k.tokens.length - k.length){
            return this.tokens.length - this.length -( k.tokens.length - k.length);
        }

        if(this.location != k.location){
            return this.location  - k.location;
        }

        int i = 0 , j= 0;
        for(i = 0, j=0 ; i < this.tokens.length && j < k.tokens.length;){

            if(i == this.location ){
                i = i + length;
                continue;
            }
            if( j == k.location){
                j = j + k.length;
                continue;
            }
            if(!this.tokens[i].equalsIgnoreCase(k.tokens[j])){
                return this.tokens[i].compareTo(k.tokens[j]);
            }else{
                i++;
                j++;
            }
        }


        //TODO: add comparison on left out phrase
        return 0;
    }

    public int hashCode() {
        int hashCode=0;     
        for(int i = 0; i < tokens.length;){

            if(i == location ){

                i = i + length;
                continue;
            }
            hashCode += tokens[i++].hashCode();
        }

        hashCode+= location + tokens.length;
        return hashCode;
    }


    public String toString(){

        if(_toString == null){
            _toString = new StringBuffer();
            for(int k = 0; k < tokens.length ;k++){
                if(k==location){
                    _toString.append(":").append(" ");
                    k=k+length-1;
                }else{
                    _toString.append(tokens[k]).append(" ");
                }
            }
        }

        return _toString.toString();
    }

    public boolean equals(PatternGeneratorKey k) {

        if(this.tokens.length - this.length == k.tokens.length - k.length 
                && this.location == k.location){

            //assume second one is larger
            String tokens[] = k.tokens;
            int length = k.length;
            int location = k.location;

            String [] tokens1 = this.tokens;
            int length1 = this.length;
            int location1 = this.location;
            //make the local variable point to the largest of the two
            if( this.tokens.length > k.tokens.length){
                tokens = this.tokens;
                length = this.length;
                location = this.location;
                tokens1 = k.tokens;
                length1 = k.length;
                location1 = k.location;

            }

            int i = 0 , j= 0;
            for(i = 0, j=0 ; i < tokens.length;){

                if(i == location ){

                    i = i + length;
                    continue;
                }
//              if( j >= location1 && j<= location1 + length1 -1){
                if( j == location1){
                    j = j + length1;
                    continue;
                }
                if(!tokens[i++].equalsIgnoreCase(tokens1[j++])){
                    return false;
                }
            }
            return true;
        }else{
            return false;
        }
    }
}

And, this is the code I am testing on

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

import org.apache.hadoop.io.Text;


public class Test {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub

        String value = "gm used cars";
        // Compile all the words using regex
        String[] tokens = value.toString().split("\\s+");

        //to find pattern we need atleast two words in the query
        if(tokens.length <=1){
            return;
        }

        Map<PatternGeneratorKey,List> map = new HashMap<PatternGeneratorKey, List>();

        for(int l = 1 ; l < tokens.length; l++){
            for(int i = 0 ; i < tokens.length - (l-1); i++){
                String hit = new String(getPhrase(l, i, tokens));
                PatternGeneratorKey key1 = new PatternGeneratorKey(i, l, tokens);
                List list = null;
                for(int k = 0;k< tokens.length;k++){
                    System.out.println("i:" + i + ",l:" + l + ",tokens:" + tokens[k]);
                }
                System.out.println("hashcode:" + key1.hashCode());

                if(!map.containsKey(key1)){
                    list = new ArrayList<String>();
                    map.put(key1, list);
                }else{
                    list = (List) map.get(key1);
                }
                list.add(hit);
            }
        }
            value = "ford used cars";
            String[] tokens2= value.toString().split("\\s+");

            PatternGeneratorKey key2 = new PatternGeneratorKey(0, 1, tokens);

            //run a sliding window for length 1 to tokens length -1
            for(int l = 1 ; l < tokens2.length; l++){
                //genereate token pairs with sliding window. 
                for(int i = 0 ; i < tokens2.length - (l-1); i++){
                    //hit a single token or a + b if there are two.
                    String hit = new String(getPhrase(l, i, tokens2));
                    PatternGeneratorKey key1 = new PatternGeneratorKey(i, l, tokens2);

                    System.out.println();

                    System.out.println(key1.toString() + "|" + key2.toString() + "|"+ key1.equals(key2));
                    for(int k = 0;k< tokens2.length;k++){
                        System.out.println("i:" + i + ",l:" + l + ",tokens:" + tokens2[k]);
                    }
                    System.out.println("hashcode:" + key1.hashCode());

                    List list = null;
                    if(!map.containsKey(key1)){
                        list = new ArrayList<String>();
                        map.put(key1, list);
                    }else{
                        list = (List) map.get(key1);
                    }
                    list.add(hit);
                }
            }

            value = "ford used cars";
            tokens= value.toString().split("\\s+");


            PatternGeneratorKey key1 = new PatternGeneratorKey(0,1,tokens);


             tokens2 = "gm used cars".split("\\s+");
             key2 = new PatternGeneratorKey(0,1,tokens2);

            System.out.println(key1.equals(key2));
            System.out.println(key2.equals(key1));

            System.out.println(key1.hashCode() );
            System.out.println(key2.hashCode() );

            System.out.println(map);

    }

    private static String getPhrase(int l, int i, String[] tokens){

        StringBuffer strin = new StringBuffer();

        int index = 0;
        for(index = i ; index < i+l;index++){
            if(index < i+l-1){
                strin.append(tokens[index]).append("+");
            }
            else
            {
                strin.append(tokens[index]);

            }
        }
        return strin.toString();
    }


}

the problem is probably the equals and hashcode implementations. Posting them would be very helpful. — Affe, Apr 27 '11 at 17:30
can we see the full version of your MyOwnKey class, or atleast the part that calculates the hash code and equals etc? Also, why exactly should those 2 keys be equal? — Java Drinker, Apr 27 '11 at 17:31
After understand the solutions posted by members on my question, I did some more research and stumble upon this. http://stackoverflow.com/questions/185937/overriding-the-java-equals-method-quirk. — Kapil D, Apr 27 '11 at 18:01

score 4 · Accepted Answer · answered Apr 27 '11 at 17:42

4

Your problem is caused by the fact that equals(PatternGeneratorKey) doesn't override equals(Object) (but it overloads equals(Object), so that key1.equals(key2) returns true when key1 and key2 are variables of type PatternGeneratorKey!).

Since HashMap calls equals(Object) to check keys for equality, your method never gets called, so you need to implement equals(Object) instead.

answered Apr 27 '11 at 17:42

axtavt

239,438
41
511
482

Thanks! http://stackoverflow.com/questions/185937/overriding-the-java-equals-method-quirk – Kapil D Apr 27 '11 at 18:02
2

Great catch! If you always remember to add the @Override annotation to your 'supposedly' extended methods, these issues can be caught at compile time. – Java Drinker Apr 27 '11 at 18:03

score 2 · Answer 2 · answered Apr 27 '11 at 17:26

2

You have a bug in either hashCode() or equals(). Show us the code.

Wild guess: in your code key1.equals(key2) doesn't mean key2.equals(key1).

answered Apr 27 '11 at 17:26

Vladimir Dyuzhev

18,130
10
48
62

key2.equals(key1) also returns true. – Kapil D Apr 27 '11 at 17:40

score 2 · Answer 3 · answered Apr 27 '11 at 17:42

2

You created an overload for equals(MyOwnKey) instead of overriding equals(Object).

Use the @Override annotation on equals() and hashCode(). It will catch this fairly common error at compile time.

answered Apr 27 '11 at 17:42

erickson

265,237
58
395
493

score 1 · Answer 4 · answered Apr 27 '11 at 17:36

HashMap#containsKey overrides AbstractMap#containsKey - so there's a subtle difference in the way that the condition:

"Returns true if and only if this map contains a mapping for a key k such that (key==null ? k==null : key.equals(k))"

is implemented.

For a subclass of AbstractMap which doesn't override containsKey() then you may well be able to get away with just implementing equals() correctly. However, for a HashMap, you need to have the implementation of hashCode() correct and satisfying the appropriate identity as well.

In any case - show us the code.

score 1 · Answer 5 · answered Apr 27 '11 at 17:42

1

You haven't actually implemented equals.

public boolean equals(PatternGeneratorKey k) {

is not what HashMap uses. It's looking for public boolean equals(Object obj) {}

answered Apr 27 '11 at 17:42

Affe

47,174
11
83
83

Key not found in a HashMap for a composite object

5 Answers5