Repository navigation
Expand file tree
/
Copy pathhashtableopenaddressing.h
More file actions
143 lines (128 loc) · 4.69 KB
/
Copy pathhashtableopenaddressing.h
File metadata and controls
143 lines (128 loc) · 4.69 KB
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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#ifndef HASHTABLEOPENADDRESSING_JL
#define HASHTABLEOPENADDRESSING_JL
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
#define HASHTABLE_OA_SIZE 13 // The number of slots. A prime number spreads the keys better.
#define SLOT_EMPTY 0 // The slot has never been used.
#define SLOT_OCCUPIED 1 // The slot stores a (key, value) pair.
#define SLOT_DELETED 2 // The slot stored a pair that was deleted (a "tombstone"): the search must continue after it.
// Define how a slot of the table is structured.
typedef struct{
int key; // The key that identifies the element.
int value; // The value associated to the key.
int state; // SLOT_EMPTY, SLOT_OCCUPIED or SLOT_DELETED.
} HashSlot;
// Define how our (non linear and static) hash table with open addressing is structured.
// When a slot is taken, we try the next one (linear probing) until we find a free slot.
typedef struct{
HashSlot slots[HASHTABLE_OA_SIZE]; // The internal array to store our pairs.
int size; // The number of (key, value) pairs stored in our table.
} HashTableOA;
/********************/
/* FUNCTIONS */
/********************/
// Set Up the Hash Table. We start with every slot empty and size 0.
void initHashTableOA(HashTableOA *table){
for(int i = 0; i < HASHTABLE_OA_SIZE; i++){
table->slots[i].state = SLOT_EMPTY;
}
table->size = 0;
}
// Calculate the First Slot of a Key. Returns a position between 0 and HASHTABLE_OA_SIZE-1 (also for negative keys).
int hashOpenAddressing(int key){
return ((key % HASHTABLE_OA_SIZE) + HASHTABLE_OA_SIZE) % HASHTABLE_OA_SIZE;
}
// Check if the Hash Table is Empty. Returns 1 if it's empty or 0 if it has elements.
int isEmptyHashTableOA(HashTableOA *table){
if(table->size == 0){
return 1;
}
else{
return 0;
}
}
// Check if the Hash Table is Full. Returns 1 if it's full or 0 if it's not full.
int isFullHashTableOA(HashTableOA *table){
if(table->size >= HASHTABLE_OA_SIZE){
return 1;
}
else{
return 0;
}
}
// Find the Slot of a Key following the probe sequence. Returns its position or -1 if the key is not in the table.
int findSlotHashTableOA(HashTableOA *table, int key){
int start = hashOpenAddressing(key);
for(int i = 0; i < HASHTABLE_OA_SIZE; i++){
int index = (start + i) % HASHTABLE_OA_SIZE;
if(table->slots[index].state == SLOT_EMPTY){
return -1;
}
if(table->slots[index].state == SLOT_OCCUPIED && table->slots[index].key == key){
return index;
}
}
return -1;
}
// Insert a (key, value) Pair. If the key already exists, its value is updated. Returns 1 if successful or 0 if the table is full.
int insertHashTableOA(HashTableOA *table, int key, int value){
int index = findSlotHashTableOA(table, key);
if(index != -1){
table->slots[index].value = value;
return 1;
}
// The key is new: we use the first slot that is not occupied (empty or deleted).
int start = hashOpenAddressing(key);
for(int i = 0; i < HASHTABLE_OA_SIZE; i++){
index = (start + i) % HASHTABLE_OA_SIZE;
if(table->slots[index].state != SLOT_OCCUPIED){
table->slots[index].key = key;
table->slots[index].value = value;
table->slots[index].state = SLOT_OCCUPIED;
table->size++;
return 1;
}
}
return 0;
}
// Search for a Key. Returns 1 if found (and its value through the pointer) or 0 if it's not.
int searchHashTableOA(HashTableOA *table, int key, int *value){
int index = findSlotHashTableOA(table, key);
if(index == -1){
return 0;
}
else{
*value = table->slots[index].value;
return 1;
}
}
// Delete a Key and its Value (its slot becomes a tombstone). Returns 1 if successful or 0 if the key is not found.
int deleteHashTableOA(HashTableOA *table, int key){
int index = findSlotHashTableOA(table, key);
if(index == -1){
return 0;
}
else{
table->slots[index].state = SLOT_DELETED;
table->size--;
return 1;
}
}
// Print every Slot of the Hash Table. Displays one line per slot: "(key, value)", "empty" or "deleted".
void printHashTableOA(HashTableOA *table){
for(int i = 0; i < HASHTABLE_OA_SIZE; i++){
printf(" %2d: ", i);
if(table->slots[i].state == SLOT_OCCUPIED){
printf("(%d, %d)\n", table->slots[i].key, table->slots[i].value);
}
else if(table->slots[i].state == SLOT_DELETED){
printf("deleted\n");
}
else{
printf("empty\n");
}
}
}
#endif //HASHTABLEOPENADDRESSING_JL