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


}

Answer 1

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.