Hash Table Implementation in Ruby

1. Introduction

A Hash Table is a data structure that provides fast insertion, deletion, and retrieval operations. It uses an array and a hash function to map keys to their respective indices in the array. Each position in the array might have a list or another data structure to handle collisions (when two keys are mapped to the same position).

2. Implementation Steps

1. Choose an initial size for the internal array (it's common to use prime numbers).

2. Define a simple hash function to convert keys to array indices.

3. Implement the insert, retrieve, and delete operations, considering the possibility of collisions.

4. Handle collisions using chaining, where each array position contains a list of all entries for that index.

3. Implementation in Ruby Programming

class HashTable
    def initialize(size = 31)
        @size = size
        @table = Array.new(size) { [] }
    end
    # Insert key-value pair into the hash table
    def insert(key, value)
        index = hash_function(key)
        @table[index] << [key, value]
    end
    # Retrieve value for a given key from the hash table
    def retrieve(key)
        index = hash_function(key)
        @table[index].each do |pair|
            return pair[1] if pair[0] == key
        end
        nil
    end
    # Delete a key-value pair from the hash table
    def delete(key)
        index = hash_function(key)
        @table[index].delete_if { |pair| pair[0] == key }
    end
    private
    def hash_function(key)
        key.to_s.sum % @size
    end
end
# Client code
hash_table = HashTable.new
hash_table.insert("name", "John")
hash_table.insert("age", 25)
puts "Name: #{hash_table.retrieve("name")}"
puts "Age: #{hash_table.retrieve("age")}"
hash_table.delete("name")
puts "Name after deletion: #{hash_table.retrieve("name")}"

Output:

Name: John
Age: 25
Name after deletion:

Explanation:

1. We initiate a HashTable class with a default size of 31 (a prime number) for the internal array, which is usually helpful in reducing collisions.

2. Each position in the @table array is initialized with an empty list to handle collisions.

3. The insert method calculates the index for a key using the hash_function and adds the key-value pair to the list at that index.

4. The retrieve method calculates the index for the key and traverses the list at that index to find the value for the given key.

5. The delete method removes the key-value pair from the list at the calculated index.

6. The hash_function converts the key to a string, calculates the sum of its characters' ASCII values, and returns the modulo with the table size. This approach ensures the generated index remains within the array's bounds.

7. The client code provides a simple demonstration of insertion, retrieval, and deletion operations.