Use a specific object-property to index, using a Map structure

Question

I'd like to use the integer-id-value of my vertex-class as an index, in my Map-structure, without using a parallel data structure.

class Vertex {
    private int v;
    private int label;

    //...
}

I store vertex objects, in a Map<Vertex,ArrayList<Edge>> adjMap.

Is it possible use the v-property of my Vertex class, as an index-key in my Map?

You mean Map key should work on based on v property of Vertex? — TheCodingFrog, Jul 26 '15 at 13:02

score 1 · Answer 1 · answered Jul 26 '15 at 13:02

It depends on the Map implementation you are using. For example, for a HashMap you can override equals and hashCode of your Vertex class so that two vertices will be considered equal if their v properties are equal.

class Vertex {
    private int v;
    private int label;

    public Vertex (int v)
    {
        this.v = v;
    }

    @Override
    public boolean equals (Object o)
    {
        if (!(o instanceof Vertex))
            return false;
        Vertex ov = (Vertex)o;
        return this.v == ov.v;
    }

    @Override
    public int hashCode ()
    {
        return v;
    }
}

Now, to locate the value for a given v value in your Map :

adjMap.containKey(new Vertex(v));

score 0 · Accepted Answer · answered Jul 26 '15 at 13:05

0

Ok. Then your equals and hashcode should only use property v. Code below:

public class Vertex {

    private int v;
    private int label;

 public static void main(String[] args) {
    Map<Vertex, String> map = new HashMap<Vertex, String>();

    Vertex vertex = new Vertex();
    vertex.v = 5;
    vertex.label = 10; 

    map.put(vertex, "vertex");

    Vertex vertex2 = new Vertex();
    vertex2.v = 5;
    vertex2.label = 100;  

    System.out.println("Value:: "+ map.get(vertex2));
}

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + v;
        return result;
    }
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Vertex other = (Vertex) obj;
        if (v != other.v)
            return false;
        return true;
    }
}

Output: Value:: vertex

answered Jul 26 '15 at 13:05

TheCodingFrog

3,406
3
21
27

when `v` is unique, you don't have to do any extra calculations to calculate `hasCode`. Just returning `v` would do. – Karthik Jul 26 '15 at 13:10
Read http://stackoverflow.com/questions/3613102/why-use-a-prime-number-in-hashcode – TheCodingFrog Jul 26 '15 at 13:13
You use prime number to avoid collisions in generating `hasCode`. – Karthik Jul 26 '15 at 13:23
Ok so you know the answer to your own question. – TheCodingFrog Jul 26 '15 at 13:24
2

Your `hashCode` method is equivalent to `return 31+v;`. Since you are not multiplying any member of the Vertex class by 31, it makes no difference and you might as well just `return v;`. – Eran Jul 26 '15 at 16:08
Good point Eran! Understood and thanks to both of you for clarifying. – TheCodingFrog Jul 27 '15 at 01:42

Use a specific object-property to index, using a Map structure

2 Answers2