How does HashMap locate the correct value when multiple values are in the same bucket?

[Faz Ali]

Hi All,

From what i've learned so far HashMap maps key/value pairs and uses the hashCode() of the key to determine how to store the value. Therefore if the hashCode is pooly implemented (code example of a poor one is below), this allows for the possibility of multiple values landing in the same bucket (if they have the same hashCode).
The above makes perfect sense but the part I don't understand is, if there are multiple items in a bucket, how does the HashMap return the element associated with supplied key when searching through this one bucket contianing multiple items. - How does it know what it's looking for?
From what I've read it uses the equals() method but on what? - The only thing I can think of is both the key/value pair being stored in the bucket as opposed to just the value but I am unsure if this is the case. Confirmation on this would be great.

The following code demonstrates my example of having multiple items in same bucket yet the HashMap returns the correct value:

import java.util.Map;
import java.util.HashMap;

public class MapTesting
{
	public static void main(String[] args)
	{
		Watch watch1 = new Watch("Emporio Armani");
		Watch watch2 = new Watch("Emporio");
		Map<Watch, String> map = new HashMap<Watch, String>();
		map.put(watch1, "Hello");
		map.put(watch2, "World");
		
		System.out.println(map.get(watch1));
		System.out.println(map.get(watch2));
	}
}

class Watch
{
	public String brandName;
	
	Watch(String brandName)
	{
		this.brandName = brandName;
	}
	
	public boolean equals(Object o)
	{
		if((o instanceof Watch) && (this.brandName.equals(((Watch)o).brandName)))
		{
			return true;
		}
		return false;
	}
	
	public int hashCode()
	{
		return 1;
	}
}

[Paul Clapham]

Each bucket contains a set of keys, so when the Map implementation is looking through the bucket, it's looking for whatever key was given to it. Or more precisely, it's looking for an object which is equal to the key it was given. That's why your key objects have to implement equals() correctly.

[Paul Clapham]

By the way: the code

if (b) {
  return true;
}
  return false;

can be expressed more concisely like this:

return b;

[Campbell Ritchie]

. . . and beware: the instanceof keyword is only reliable in the equals() method when you are in a final class. I would suggest this

public class Watch
{
 . . .
   @Override // To throw an error if there is even the tiniest spelling error
   public boolean equals(Object o)
   {
        return o == this ||        // If the two objects are the same object, no need for any further testing
               o != null &&        // necessary to permit null being passed without Exception
               o.getClass() == getClass() &&    // Same Class<T> object
               (brandName == null
                                ?                                  // Use the ?: operator to get the test into one line.
                                ((Watch)o).brandName == null
                                :
                                brandName.equals(((Watch)o).brandName)); // Allows for the brandName field to be null
   }
}