Java: Hashtable stores multiple items with same hash in one bucket

Question

Problem Description

While reading Oracle documentation about Hashtable I found that "in the case of a "hash collision", a single bucket stores multiple entries, which must be searched sequentially", so I try to find method which will return me items sequentially, if I have two items with the same hash, but can't find in the documentation. In order to reproduce this situation I try to write a simple code, which you can find below.

Oracle Documentation about Hashtable

An instance of Hashtable has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created. Note that the hash table is open: in the case of a "hash collision", a single bucket stores multiple entries, which must be searched sequentially. The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. The initial capacity and load factor parameters are merely hints to the implementation. The exact details as to when and whether the rehash method is invoked are implementation-dependent.

Simple Code

class Key {
    public final int mID;
    
    public Key(int id) {
        mID = id;
    }
    
    @Override
    public int hashCode() {
        if(mID == 1 || mID == 2) {
            System.out.println("Have same hashCode()");
            return 5673654;
        }
        return super.hashCode();
    }
};

public class HashtableTest {
    
    public static void main(String... args) {
        Hashtable<Key, String> dict = new Hashtable<Key, String>();
        dict.put(new Key(1), "One");
        dict.put(new Key(2), "Two");
    
        System.out.println(dict.size());             // Prints 2
        System.out.println(dict.get(new Key(1)));    // Prints null
    }

};

In the code above I try to add to the Hashtable two items which have same hashcode (anyway I think that they have :) ), so for that I create my Key class and override it's hashCode method, but this was useless as I can't even get item from the Hashtable and I think that items are not added sequentially.

Questions

1. How I can simulate situation of stores multiple entries in one bucket? (In order to more deeply understand how this work)
2. How I can access to the items in the Hashtable which are stored sequentially?

Answer 1

The Hashtable (and HashMap) already implement collision resolution by storing multiple keys that map to the same bucket number.

However, you also need to override the equals method in Key. For the Hashtable (or HashMap) to find a key that already exists in the map, the hash codes are used to find the bucket, but equals is used to distinguish any distinct keys in the same bucket. Because you aren't overriding equals, Key inherits equals from Object, which only determines if the two objects are the same object, not whether their contents are equal.

The equals method for class Object implements the most discriminating possible equivalence relation on objects; that is, for any non-null reference values x and y, this method returns true if and only if x and y refer to the same object (x == y has the value true).

Note that it is generally necessary to override the hashCode method whenever this method is overridden, so as to maintain the general contract for the hashCode method, which states that equal objects must have equal hash codes.

Answer 2

You need to implement equals method as well, below is a complete sample:

public class ClientPojo {

    private String firstName;
    private String lastName;

    public void setFirstName(String firstName) {
        this.firstName = firstName;
    }

    public String getFirstName() {
        return this.firstName;
    }

    public void setLastName(String lastName) {
        this.lastName = lastName;
    }

    public String getLastName() {
        return this.lastName;
    }

    @Override
    public boolean equals(Object obj) {
        return obj instanceof ClientPojo
                && this.firstName.equals(((ClientPojo) obj).getFirstName())
                && this.lastName.equals(((ClientPojo) obj).getLastName());
    }

    @Override
    public int hashCode() {
        return new org.apache.commons.lang3.builder.HashCodeBuilder(17, 37)
                .append(this.firstName)
                .append(this.lastName)
                .toHashCode();
    }
}

org.apache.commons.lang3.builder.HashCodeBuilder also makes it pretty easy to build hashes.

Answer 3

In your code new Key(1) and new Key(2) have same hashcode(==5673654),so they will go in same bucket.

when you are retrieving by dict.get(new Key(1))-n this case new Key(1) also have same HashCode so this will also search in same bucket.//fine

But earlier inserted both object(new Key(1) and new Key(2)) are not equal to this object(new Key(1)) so this giving no records.You need to implement equals method as well.

since-

new Key(1).equals(new Key(1))//false

new Key(2).equals(new Key(1))//false