Hash Table with Chain Implementation

Using chain is one solution for collision. Each element in array of hash table is a linked list, which store all the key_value pair that share the same hash. Initially, all slots of array will be NULL. For push in a pair of key-value, hash value is calculated, then the pair will be added at the end of the linked list of corresponding hash value.

Illustration:

Source: www.necessaryandsufficient.net

Complexity

Assume that the distribution of value in hash code is urniform, basic operations (such as get, set, remove) will be TABLE_SIZE time faster than storing all key-value linearly.

Implementation

  • In the implementation below, key-value pairs are assumed to be int-int.
  • TABLE_SIZE (size of hash array) = 128
[HashTable] [++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>

using namespace std;

class LinkedHashEntry{
 	private:
    		int key;
    		int value;
    		LinkedHashEntry* next;
  	public:
		LinkedHashEntry( int key, int value ){
			this->key = key;
			this->value = value;
			this->next = NULL;
		}
		int getKey(){
			return this->key;
		}
		int getValue(){
			return this->value;
		}
		void setValue(int value){
			this->value = value;
		}
		LinkedHashEntry* getNext(){
			return this->next;
		}
		void setNext(LinkedHashEntry* next){
			this->next = next;
		}
};




const int TABLE_SIZE = 128;
class HashTable{
	private:
		LinkedHashEntry ** table;
	public:
		HashTable(){
			table = new LinkedHashEntry * [TABLE_SIZE];
			for (int i=0; i<TABLE_SIZE; i++) {
				table[i]= NULL;
			}
		}
		int get(int key) {
			int hash = (key %TABLE_SIZE);
			LinkedHashEntry* entry = table[hash];
			while (entry != NULL && entry->getKey()!=key) {
				entry = entry -> getNext();
			}
			if (entry == NULL)  
				return -1;
			else 
				return entry->getValue();
		}
		void set(int key, int value) {
			int hash = (key % TABLE_SIZE);
			LinkedHashEntry* entry = table[hash];
			LinkedHashEntry* last_entry = NULL;;

			while (entry != NULL && entry->getKey()!=key) {
				if (entry -> getNext() == NULL ) {
					last_entry = entry;	
				}
				entry = entry -> getNext();
			}
			if (entry != NULL) {
				entry -> setValue(value);
			} else {
				if (last_entry ==NULL) {
					table[hash]= new LinkedHashEntry(key,value);
				} else  {
					last_entry->setNext(new LinkedHashEntry(key,value) );
				}
			}
		}
		void remove(int key) {
			int hash = (key % TABLE_SIZE);
			LinkedHashEntry* entry = table[hash];
			LinkedHashEntry* pre_entry = NULL;

			while (entry != NULL && entry->getKey()!=key) {
				pre_entry = entry;
				entry = entry -> getNext();
			}
			if (entry !=NULL) {
				if (pre_entry == NULL) {
					table[hash] = entry->getNext();
					delete entry;
				} else {
					pre_entry->setNext(entry->getNext() );
					delete entry;
				}
			}
		}
		~HashTable(){
			LinkedHashEntry * entry;
			LinkedHashEntry * pre_entry;
			for (int i=0 ; i<TABLE_SIZE; i++){
				entry = table[i];
				while (entry !=NULL) {
					pre_entry = entry;
					entry = entry ->getNext();
					delete pre_entry;
				}
			}
			delete[] table;
		} 
};