CODEWITHSUNDEEP
javacollectionshashtable
Vrijendra Kumar Singh
Vrijendra Kumar Singh

Reputation: 33

HashTable: in case of collision

   Hashtable ht = new Hashtable();
    for (int i = 0; i < 100; i++) {
        ht.put(i%10, i);
    }

    Enumeration< Integer> eles = ht.elements();
    while(eles.hasMoreElements())
        System.out.println(eles.nextElement());

Above code snippet is printing 99, 98,.......90

But I want to print all 100 elements. How to get a list of numbers like ... 99,89,79,69,...19,9 98,88,78,68....18,8 97,87,77,67....17,7 .. .. 91,81,71,61....11,1

Basically all collision list.

Upvotes: 0

Views: 429

Answers (2)

przemek hertel
przemek hertel

Reputation: 4024

What you observe in your example is not collision effect. It is normal element replacement. After your 100 iteration there are only 10 elements in Hashtable.

You use numbers i%10 (0,1,...,9) as keys. So, you have only 10 different keys. For example: in your for-loop you put 10 values for key=5 (i=5, i=15, i=95) and each put(5, val) replaces old value associated with key=5.

Collision list is different concept.

For each key hashtable computes some hash value and uses this hash to select index in its inner bucket table. Next places {key,value} under that index. Collision is situation where 2 different keys has computed the same bucket index.

For example:

table index   |  map.entry
0             |  {0, "A"}
1             |  {3, "B"}
2             |  {2, "A"} -> {4, "C"}
3             |  {1, "D"} -> {5, "A} -> {6, "F}

In this example you have hashtable with 4-element inner table. This hashtable contains 7 element (7 different keys) but:

key 2 and 3 was placed to the same bucket (they have the same index computed upon hash value) key 1, 5, 6 was placed to the same bucket.

So we can say, there is collision between key=2 and key=3 and between 1,5,6. In other words keys 2 adn 3 are on the same collision list. The same to keys 1,5,6.

You cannot get such collistion list from Hashtable because it is Hashtable internal implementation marked as private:

/**
 * Hashtable bucket collision list entry
 */
private static class Entry<K,V> implements Map.Entry<K,V> {

int hash;
final K key;
V value;
Entry<K,V> next;

protected Entry(int hash, K key, V value, Entry<K,V> next) {
    this.hash = hash;
    this.key =  key;
    this.value = value;
    this.next = next;
}

...

public V setValue(V value) {
    if (value == null)
        throw new NullPointerException();

    V oldValue = this.value;
    this.value = value;
    return oldValue;
}

...

public int hashCode() {
    return hash ^ value.hashCode();
}

...

}

And Hashtable have its internal bucket table defined as:

/**
 * The hash table data.
 */
private transient Entry<K,V>[] table;

Hope this helps to figure out hashtable behavior.

Upvotes: 0

Duncan Jones
Duncan Jones

Reputation: 69409

You are currently using i % 10 as your hash map key, which only has ten values (0-9). Hence only the last ten values are stored in your map, all the others are overriden.

If you need to store more than one item in each bucket, use a list type as your value. For example:

Hashtable<Integer, List<Integer>> ht = new Hashtable<>();
for (int i = 0; i < 100; i++) {
  int key = i % 10;
  List<Integer> list = ht.get(key);
  if (list == null) {
    list = new ArrayList<>();
    ht.put(key, list);
  }
  list.add(i);      
}

Enumeration<List<Integer>> eles = ht.elements();
while (eles.hasMoreElements()) {
  System.out.println(Arrays.toString(eles.nextElement().toArray()));
}

Output:

[9, 19, 29, 39, 49, 59, 69, 79, 89, 99]
[8, 18, 28, 38, 48, 58, 68, 78, 88, 98]
[7, 17, 27, 37, 47, 57, 67, 77, 87, 97]
[6, 16, 26, 36, 46, 56, 66, 76, 86, 96]
[5, 15, 25, 35, 45, 55, 65, 75, 85, 95]
[4, 14, 24, 34, 44, 54, 64, 74, 84, 94]
[3, 13, 23, 33, 43, 53, 63, 73, 83, 93]
[2, 12, 22, 32, 42, 52, 62, 72, 82, 92]
[1, 11, 21, 31, 41, 51, 61, 71, 81, 91]
[0, 10, 20, 30, 40, 50, 60, 70, 80, 90]

Upvotes: 6

Related Questions