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.
1 | #ifndef list_h |
2 | #define list_h |
3 | |
4 | template<class T> |
5 | class List { |
6 | private: |
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 |      |
162 | public: |
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 |
1 | #ifndef hashtable_h |
2 | #define hashtable_h |
3 | #include <cstdlib> |
4 | #include <string> |
5 | |
6 | class Hashtable { |
7 | private: |
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 |      |
21 | public: |
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 |
1 | #include <iostream> |
2 | #include "list.h" |
3 | #include "hashtable.h" |
4 | using namespace std; |
5 | |
6 | int 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 | } |