AlgoDaily - Hash Tables

Home > Data structure and algorithms > Data structure and algorithms > Hash Tables

When inserting data into a hash table, it's possible for two different keys to produce the same hash value. This is known as a collision. Handling collisions is an important aspect of hash table implementation.

There are several common collision resolution techniques:

1. Separate Chaining: In this technique, each bucket in the hash table is a linked list. When a collision occurs, the entry with the colliding key is added to the linked list at the corresponding bucket.

Here's an example of using separate chaining to handle collisions in Java:

TEXT/X-JAVA

1// Implementation of hash table with separate chaining
2import java.util.LinkedList;
3
4public class HashTable<K, V> {
5    private int size;
6    private LinkedList<Entry<K, V>>[] buckets;
7
8    public HashTable(int size) {
9        this.size = size;
10        this.buckets = new LinkedList[size];
11    }
12
13    // Other methods omitted for brevity
14}

xxxxxxxxxx
}
 
```java
import java.util.LinkedList;
​
public class HashTable<K, V> {
    private int size;
    private LinkedList<Entry<K, V>>[] buckets;
​
    public HashTable(int size) {
        this.size = size;
        this.buckets = new LinkedList[size];
    }
​
    public void put(K key, V value) {
        int index = getIndex(key);
        if (buckets[index] == null) {
            buckets[index] = new LinkedList<>();
        }
​
        LinkedList<Entry<K, V>> bucket = buckets[index];
        for (Entry<K, V> entry : bucket) {
            if (entry.key.equals(key)) {
                entry.value = value;
                return;
            }
        }
​
        bucket.add(new Entry<>(key, value));
    }
​

Programming Categories

Popular Lessons