Hash Table

Hash table is a data structure for big data for insert or remove operations with constant expenditure of time in computer science.

In best case with none collision and none degeneracy is an expenditure of time next to O(1).

In worst case by increasing data inputs raised the possibility of collisions and degeneracy and time complexity is by O(n).

The hash table combines an array with a simply linked list and the hash algorithm defined distribution of items in its buckets.

list.h
1#ifndef list_h
2#define list_h
3
4template<class T>
5class List {
6private:
7    struct Item {
8        T data;
9        struct Item *next;
10    };
11    
12    struct Item *list;
13    
14    struct Item *append_item(T data) {
15        struct Item *new_item = new struct Item;
16        new_item->data = data;
17        new_item->next = NULL;
18        return new_item;
19    }
20    
21    struct Item *append_item(struct Item **head_ref, T data) {
22        struct Item *curr = *head_ref;
23        if(curr != NULL) return append_item(&curr->next, data);
24        return (*head_ref) = append_item(data);
25    }
26    
27    struct Item *push_item(struct Item **head_ref, T new_data) {
28        //allocate new node
29        struct Item *new_node = new struct Item;
30        
31        //put in data
32        new_node->data = new_data;
33        
34        //link the old list off the new node
35        new_node->next = (*head_ref);
36        
37        //move the head to point to the new node
38        return (*head_ref) = new_node;
39    }
40    
41    struct Item *erase_item(struct Item **head_ref, struct Item **curr_ref, T data) {
42        struct Item *head = *head_ref;
43        struct Item *curr = *curr_ref;
44        if(head == NULL) return (*head_ref);
45        if(curr->data == data) {
46            struct Item *temp = curr;
47            if(curr != head) {
48                //delete middle item
49                if(curr->next != NULL) {
50                    curr->data = curr->next->data;
51                    temp = curr->next;
52                    curr->next = curr->next->next;
53                    delete temp;
54                    return (*curr_ref);
55                }
56                //delete tail item
57                else {
58                    delete temp;
59                    return (*curr_ref) = NULL;
60                }
61            }
62            //delete head item
63            else {
64                delete temp;
65                return (*curr_ref) = curr->next;
66            }
67        }
68        return erase_item(&head, &curr->next, data);
69    }
70    
71    struct Item *erase_list(struct Item **head_ref) {
72        struct Item *curr = *head_ref;
73        if(curr == NULL) return (*head_ref);
74        else {
75            struct Item *temp;
76            if(curr->next != NULL) {
77                temp = curr->next;
78                curr->data = curr->next->data;
79                curr->next = curr->next->next;
80                delete temp;
81            }
82            else {
83                temp = curr;
84                delete temp;
85                curr = NULL;
86            }
87        }
88        return (*head_ref) = erase_list(&curr);
89    }
90    
91    int length(struct Item **head_ref) {
92        struct Item *curr = *head_ref;
93        int counter = 0;
94        while(curr != NULL) {
95            counter++;
96            curr = curr->next;
97        }
98        return counter;
99    }
100    
101    void print(struct Item **head_ref) {
102        struct Item *curr = *head_ref;
103        if(curr == NULL) return;
104        else {
105            std::cout << curr->data << " ";
106            print(&curr->next);
107        }
108    }
109    
110    struct Item *reverse_list(struct Item **head_ref) {
111        struct Item *prev = NULL;
112        struct Item *curr = *head_ref;
113        struct Item *next;
114        while(curr != NULL) {
115            next = curr->next;
116            curr->next = prev;
117            prev = curr;
118            curr = next;
119        }
120        return (*head_ref) = prev;
121    }
122    
123    struct Item *search(struct Item **head_ref, T item) {
124        struct Item *curr = *head_ref;
125        if(curr->next == NULL) return (*head_ref);
126        if(curr->data != item) return search(&curr->next, item);
127        return (*head_ref);
128    }
129    
130    struct Item *swap(struct Item **head_ref, T x, T y) {
131        if(x == y) return (*head_ref);
132        
133        struct Item *prev_x = NULL;
134        struct Item *curr_x = *head_ref;
135        while(curr_x && curr_x->data != x) {
136            prev_x = curr_x;
137            curr_x = curr_x->next;
138        }
139        
140        struct Item *prev_y = NULL;
141        struct Item *curr_y = *head_ref;
142        while(curr_y && curr_y->data != y) {
143            prev_y = curr_y;
144            curr_y = curr_y->next;
145        }
146        
147        if(curr_x == NULL || curr_y == NULL) return (*head_ref);
148        
149        if(prev_x != NULL) prev_x->next = curr_y;
150        else (*head_ref) = curr_y;
151        
152        if(prev_y != NULL) prev_y->next = curr_x;
153        else (*head_ref) = curr_x;
154        
155        struct Item *temp = curr_x->next;
156        curr_x->next = curr_y->next;
157        curr_y->next = temp;
158        
159        return (*head_ref);
160    }
161    
162public:
163    List() {
164        list = NULL;
165    }
166    
167    ~List() {
168        erase_list(&list);
169    }
170    
171    void append(T data) {
172        append_item(&list, data);
173    }
174    
175    void push(T data) {
176        push_item(&list, data);
177    }
178    
179    void erase(T item) {
180        erase_item(&list, &list, item);
181    }
182    
183    void erase() {
184        erase_list(&list);
185    }
186    
187    int length() {
188        return length(&list);
189    }
190    
191    void print() {
192        print(&list);
193        std::cout << std::endl;
194    }
195    
196    void reverse() {
197        reverse_list(&list);
198    }
199    /*
200    struct Item *search(T item) {
201        return search(&list, item);
202    }
203    */
204    void search(T data) {
205      std::cout << std::endl << "Searching item " << data << "..." << std::endl;
206      struct Item *wanted = search(&list, data);
207      if(wanted->data == data) std::cout << data << " found!";
208      else std::cout << data << " not found!";
209      std::cout << std::endl;
210    }
211    
212    void swap(T x, T y) {
213        swap(&list, x, y);
214    }
215};
216
217#endif
hashtable.h
1#ifndef hashtable_h
2#define hashtable_h
3#include <cstdlib>
4#include <string>
5
6class Hashtable {
7private:
8    List<std::string> *array;
9    int length;
10    
11    int hash(std::string data) {
12        int value = 0;
13        
14        for(int i = 0; i < data.length(); i++) {
15            value += data[i];
16        }
17        
18        return (value * data.length()) % length;
19    }
20    
21public:
22    Hashtable(int table_length = 13) {
23        if(table_length <= 0) {
24            table_length = 13;
25        }
26        
27        array = new List<std::string>[table_length];
28        length = table_length;
29    }
30    
31    ~Hashtable() {
32        for(int i = 0; i < length; i++) {
33            array[i].erase();
34        }
35        
36        delete [] array;
37    }
38    
39    void insert(std::string data) {
40        int index = hash(data);
41        array[index].push(data);
42        
43    }
44    
45    void remove_item(std::string data) {
46        int index = hash(data);
47        array[index].erase(data);
48    }
49    
50    int get_length() {
51        return length;
52    }
53    
54    void print_histogram() {
55        std::cout << std::endl << "Hash Table Contains ";
56        std::cout << get_number_of_items() << " Items total" << std::endl;
57        for(int i = 0; i < length; i++) {
58            std::cout << i + 1 << ":\t";
59            for(int j = 0; j < array[i].length(); j++) {
60                std::cout << " X";
61            }
62            
63            std::cout << std::endl;
64        }
65    }
66    
67    //Returns the number of Items in the Hash Table.
68    int get_number_of_items() {
69        int counter = 0;
70        
71        for(int i = 0; i < length; i++) {
72            counter += array[i].length();
73        }
74        
75        return counter;
76    }
77    
78    void search(std::string data) {
79        int index = hash(data);
80        
81        array[index].search(data);
82    }
83    
84    void print_table() {
85        std::cout << std::endl << "Hash Table:" << std::endl;
86        
87        for(int i = 0; i < length; i++) {
88            std::cout << "Bucket " << i + 1 << ": ";
89            array[i].print();
90        }
91    }
92};
93
94#endif
main.cpp
1#include <iostream>
2#include "list.h"
3#include "hashtable.h"
4using namespace std;
5
6int main() {
7    Hashtable *hash = new Hashtable;
8    hash->insert("Apple");
9    hash->insert("Banana");
10    hash->insert("Carrot");
11    hash->insert("Date");
12    hash->insert("Egypt");
13    hash->insert("Fennel");
14    hash->insert("Goods");
15    hash->insert("House");
16    hash->insert("Isle");
17    hash->insert("Job");
18    hash->insert("Kiwi");
19    hash->insert("Lemmon");
20    hash->insert("Melon");
21    hash->insert("Noodle");
22    hash->insert("Orange");
23    hash->insert("Pear");
24    hash->insert("Quark");
25    hash->insert("Rice");
26    hash->insert("Salt");
27    hash->insert("Tomato");
28    hash->insert("Underworld");
29    hash->insert("Volcano");
30    hash->insert("Wagon");
31    hash->insert("Xylophon");
32    hash->insert("Yellow");
33    hash->insert("Zebra");
34    hash->print_table();
35    hash->print_histogram();
36    
37    hash->search("Beans");
38    
39    
40    delete hash;
41   
42    return 0;
43}