---

Introduction

---

Hashing is a fundamental concept in computer science used to efficiently map data of arbitrary size to fixed-size values, known as hash values or hash codes. This process involves the use of hash functions and hash tables, which enable fast data retrieval, insertion, and deletion. In this post, we will delve into the principles of hashing, explore the structure and functionality of hash tables, and demonstrate how to implement them in Java.

---

What is Hashing?

---

Hashing is the process of converting an input (or ‘key’) into a fixed-size string of bytes, typically for the purpose of indexing data. The output, called a hash code, is generated by a hash function. Hashing is commonly used in data structures like hash tables, which use hash codes to quickly locate a data record given its search key.

---

Hash Functions

---

A hash function is a mathematical algorithm that maps data of arbitrary size to a fixed-size value. A good hash function has the following properties:

1. Deterministic: The same input should always produce the same output.
2. Fast: The function should compute the hash value quickly.
3. Uniform Distribution: Hash values should be uniformly distributed to minimize collisions.
4. Minimal Collisions: Different inputs should produce different hash values as often as possible.

---

Hash Tables

---

A hash table (or hash map) is a data structure that stores key-value pairs. It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found. The primary operations supported by hash tables are insertion, deletion, and lookup.

---

Handling Collisions

---

Collisions occur when two keys hash to the same index. There are several methods to handle collisions:

1. Chaining: Each bucket contains a linked list of elements that hash to the same index.
2. Open Addressing: All elements are stored in the array itself. When a collision occurs, the algorithm searches for the next empty slot.

---

Example Implementation in Java

---

Let’s implement a simple hash table in Java using chaining to handle collisions.

Step 1: Define the Entry Class

class Entry<K, V> {
    K key;
    V value;
    Entry<K, V> next;

    public Entry(K key, V value) {
        this.key = key;
        this.value = value;
        this.next = null;
    }
}

Step 2: Define the HashTable Class

public class HashTable<K, V> {
    private Entry<K, V>[] table;
    private int capacity;

    @SuppressWarnings("unchecked")
    public HashTable(int capacity) {
        this.capacity = capacity;
        this.table = new Entry[capacity];
    }

    private int hash(K key) {
        return Math.abs(key.hashCode()) % capacity;
    }

    public void put(K key, V value) {
        int index = hash(key);
        Entry<K, V> newEntry = new Entry<>(key, value);

        if (table[index] == null) {
            table[index] = newEntry;
        } else {
            Entry<K, V> current = table[index];
            while (current.next != null) {
                if (current.key.equals(key)) {
                    current.value = value;
                    return;
                }
                current = current.next;
            }
            if (current.key.equals(key)) {
                current.value = value;
            } else {
                current.next = newEntry;
            }
        }
    }

    public V get(K key) {
        int index = hash(key);
        Entry<K, V> current = table[index];

        while (current != null) {
            if (current.key.equals(key)) {
                return current.value;
            }
            current = current.next;
        }
        return null;
    }

    public void remove(K key) {
        int index = hash(key);
        Entry<K, V> current = table[index];
        Entry<K, V> previous = null;

        while (current != null) {
            if (current.key.equals(key)) {
                if (previous == null) {
                    table[index] = current.next;
                } else {
                    previous.next = current.next;
                }
                return;
            }
            previous = current;
            current = current.next;
        }
    }

    public static void main(String[] args) {
        HashTable<String, String> hashTable = new HashTable<>(10);
        hashTable.put("key1", "value1");
        hashTable.put("key2", "value2");
        hashTable.put("key3", "value3");

        System.out.println("key1: " + hashTable.get("key1"));
        System.out.println("key2: " + hashTable.get("key2"));
        System.out.println("key3: " + hashTable.get("key3"));

        hashTable.remove("key2");
        System.out.println("key2 after removal: " + hashTable.get("key2"));
    }
}

---

Explanation

---

• Entry Class:

  • This class represents each entry in the hash table. It contains a key, a value, and a reference to the next entry in case of a collision (chaining).

• HashTable Class:

  • The HashTable class contains an array of Entry objects and methods to perform the basic operations:

    • hash: Computes the index for a given key.
    • put: Inserts a new key-value pair into the hash table.
    • get: Retrieves the value associated with a given key.
    • remove: Removes the key-value pair associated with a given key.

• Main Method:

  • Demonstrates the usage of the hash table by adding, retrieving, and removing key-value pairs.

---

Conclusion

---

Hashing is a powerful technique used in various applications, from data retrieval to cryptography. Understanding hash tables and hash functions is essential for efficient data storage and retrieval. This post provides a comprehensive overview of hashing principles and a practical implementation example in Java. By mastering these concepts, you can improve the performance of your applications and gain deeper insights into algorithm design.

---