Python/C/C++/JAVA

Advanced Practice Programs with Code and Concept

By D.S

Implementing a Basic Hash Table

So, you're looking to implement a hash table? Great choice - hash tables are an incredibly useful data structure for efficient lookups. The basic idea behind a hash table is that you store key-value pairs, but instead of using the key directly as an index into an array (which could be slow if there are collisions), you actually use a hash function to compute an index from the key. This way, each key maps to a potentially unique index, and you can retrieve the value associated with a given key in constant time.

(a.) C Code

#include <stdio.h>
#include <stdlib.h>
        
        #define SIZE 10
        
        struct DataItem {
           int data;   
           int key;
        };
        
        struct DataItem* hashArray[SIZE]; 
        struct DataItem* dummyItem;
        struct DataItem* item;
        
        int hashCode(int key) {
           return key % SIZE;
        }
        
        struct DataItem *search(int key) {
           int hashIndex = hashCode(key);  
           
           while(hashArray[hashIndex] != NULL) {
              if(hashArray[hashIndex]->key == key)
                 return hashArray[hashIndex]; 
              
              ++hashIndex;
              hashIndex %= SIZE;
           }        
          
           return NULL;        
        }
        
        void insert(int key, int data) {
           struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem));
           item->data = data;  
           item->key = key;
        
           int hashIndex = hashCode(key);
          
           while(hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1) {
              ++hashIndex;
              hashIndex %= SIZE;
           }
          
           hashArray[hashIndex] = item;
        }
        
        void display() {
           for(int i = 0; i < SIZE; i++) {
              if(hashArray[i] != NULL)
                 printf(" (%d,%d)", hashArray[i]->key, hashArray[i]->data);
              else
                 printf(" ~~ ");
           }
           printf("\n");
        }
        
        int main() {
           dummyItem = (struct DataItem*) malloc(sizeof(struct DataItem));
           dummyItem->data = -1;  
           dummyItem->key = -1; 
        
           insert(1, 20);
           insert(2, 70);
           insert(42, 80);
           insert(4, 25);
           insert(12, 44);
           insert(14, 32);
           insert(17, 11);
           insert(13, 78);
           insert(37, 97);
        
           display();
           item = search(37);
        
           if(item != NULL) {
              printf("Element found: %d", item->data);
           } else {
              printf("Element not found");
           }
        }

Output:-

Value for key 2: 20

(b.) C++ Code

#include <iostream>
        #include <list>
        using namespace std;
        
        class Hash {
            int BUCKET; 
            list<int> *table;
        public:
            Hash(int V); 
            void insertItem(int x);
            void deleteItem(int key);
            int hashFunction(int x) {
                return (x % BUCKET);
            }
            void displayHash();
        };
        
        Hash::Hash(int b) {
            this->BUCKET = b;
            table = new list<int>[BUCKET];
        }
        
        void Hash::insertItem(int key) {
            int index = hashFunction(key);
            table[index].push_back(key);
        }
        
        void Hash::deleteItem(int key) {
            int index = hashFunction(key);
            list<int>::iterator i;
            for (i = table[index].begin(); i != table[index].end(); i++) {
                if (*i == key)
                    break;
            }
            if (i != table[index].end())
                table[index].erase(i);
        }
        
        void Hash::displayHash() {
            for (int i = 0; i < BUCKET; i++) {
                cout << i;
                for (auto x : table[i])
                    cout << " --> " << x;
                cout << endl;
            }
        }
        
        int main() {
            int a[] = {15, 11, 27, 8, 12};
            int n = sizeof(a) / sizeof(a[0]);
            Hash h(7); 
            for (int i = 0; i < n; i++)
                h.insertItem(a[i]);
            h.deleteItem(12);
            h.displayHash();
            return 0;
        }

Output:-

Value for key 2: 20

(c.) Python Code

class HashTable:
    def __init__(self):
        self.MAX = 10
        self.arr = [[] for _ in range(self.MAX)]

    def get_hash(self, key):
        h = 0
        for char in key:
            h += ord(char)
        return h % self.MAX

    def __setitem__(self, key, val):
        h = self.get_hash(key)
        found = False
        for idx, element in enumerate(self.arr[h]):
            if len(element) == 2 and element[0] == key:
                self.arr[h][idx] = (key, val)
                found = True
                break
        if not found:
            self.arr[h].append((key, val))

    def __getitem__(self, key):
        h = self.get_hash(key)
        for element in self.arr[h]:
            if element[0] == key:
                return element[1]
        return None

    def __delitem__(self, key):
        h = self.get_hash(key)
        for idx, element in enumerate(self.arr[h]):
            if element[0] == key:
                del self.arr[h][idx]
                break

# Testing the HashTable class
t = HashTable()
t['march 6'] = 130
t['march 17'] = 20
print(t['march 6'])  # Output: 130
del t['march 6']
print(t['march 6'])  # Output: None

Output:-

130 None

(d.) Java Code

import java.util.*;

class HashTable {
    private int BUCKET;
    private LinkedList<Integer>[] table;

    HashTable(int b) {
        this.BUCKET = b;
        table = (LinkedList<Integer>[]) new LinkedList[b];  // FIX
        for (int i = 0; i < b; i++) {
            table[i] = new LinkedList<>();
        }
    }

    void insert(Integer key) {
        int index = key % BUCKET;
        table[index].add(key);
    }

    void delete(Integer key) {
        int index = key % BUCKET;
        table[index].remove(key);
    }

    void display() {
        for (int i = 0; i < BUCKET; i++) {
            System.out.print(i);
            for (Integer key : table[i]) {
                System.out.print(" --> " + key);
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        HashTable h = new HashTable(7);
        int[] arr = {15, 11, 27, 8, 12};
        for (int i : arr) {
            h.insert(i);
        }
        h.delete(12);
        h.display();
    }
}

Output:-

Value for key 2: 20

Python/C/C++/JAVA

Advanced Practice Programs with Code and Concept

By D.S

Implementing a Basic Hash Table

(a.) C Code

Output:-

(b.) C++ Code

Output:-

(c.) Python Code

Output:-

(d.) Java Code

Output:-

How did you feel about this post?