HashTable implementation
The Specifics:
It uses a simple hash function, it recieves a string and adds the ASCII values of each caracter, this can cause problems if the string is big, but for this implementation the string passed to the hash function will have no more then 5 caracters.
It has a load factor of 0.5, if reached i it will duplicate the hashtable size to the nearest prime number. To reduce collisions the hashtable sizes will only be prime numbers.
The hashtable is made of an array of "buckets" where each "bucket" is a struct storing the user information, in this case, name and nick.
The hashtable keeps track of its size and number of elements.
The hashtable uses linear probing to deal with collisions.
Implemented Methods
- Create
- Insert
- Delete a specific item
- Contains
- get_Item
- Display
This is my first attemp at making a hashtable from scratch, here is the code:
#define initial_size 5
typedef struct user{
char nick[6];
char name[26];
bool occupied;
}user;
typedef struct hashtable{
int size;
int elements;
user **buckets;
}hashtable;
hashtable * create() {
hashtable *htable = (hashtable*)malloc(sizeof(hashtable));
htable->size = initial_size;
htable->elements = 0;
htable->buckets = malloc(initial_size * sizeof(htable->buckets));
for(int i=0; i <initial_size; i++){
htable->buckets[i] = malloc(sizeof(user));
htable->buckets[i]->occupied = false;
}
return htable;
}
int hash(char *string) {
int hashVal = 0;
for( int i = 0; i < strlen(string);i++){
hashVal += (int)string[i];
}
return hashVal;
}
bool load_factor(hashtable *ht){
if(ht->elements >= ht->size/2){
return true;
}
return false;
}
bool isPrime(int num){
if(num==2)
return true;
if(num % 2==0)
return false;
for(int i=3; i*i<num; i+=2){
if(num%i==0)
return false;
}
return true;
}
int Prime_num(int old_size){
for(int i = old_size; i < old_size * 2 +10; i++){
if(isPrime(i) && i >= 2*old_size){
return i;
}
}
}
void insert(hashtable *HashTable, char *name, char *nick){
int hash_value = hash(nick);
int new_position = hash_value % HashTable->size;
if (new_position < 0) new_position += HashTable->size;
int position = new_position;
while (HashTable->buckets[position]->occupied && position != new_position - 1) {
position++;
position %= HashTable->size;
}
strcpy(HashTable->buckets[position]->name, name);
strcpy(HashTable->buckets[position]->nick, nick);
HashTable->buckets[position]->occupied = true;
HashTable->elements++;
}
hashtable *resize_HashTable(hashtable *HashTable){
user *tmp_array = malloc(sizeof(user) * HashTable->size);
int tmp_array_pos = 0;
for(int i = 0; i < HashTable->size; i++){
if(HashTable->buckets[i]->occupied){
strcpy(tmp_array[tmp_array_pos].nick, HashTable->buckets[i]->nick);
strcpy(tmp_array[tmp_array_pos].name, HashTable->buckets[i]->name);
tmp_array_pos++;
}
}
int new_size = Prime_num(HashTable->size);
HashTable = realloc(HashTable, new_size * sizeof(user));
for(int i = 0; i < new_size; i++){
HashTable->buckets[i] = malloc(sizeof(user));
HashTable->buckets[i]->occupied = false;
}
HashTable->size = new_size;
HashTable->elements = 0;
for(int i = 0; i < tmp_array_pos; i++){
insert(HashTable, tmp_array[i].name, tmp_array[i].nick);
}
return HashTable;
}
int contains(hashtable *HashTable, char *nick){
int hash_value = hash(nick);
int position = (hash_value % HashTable->size);
int fixed_p = position;
while(position < HashTable->size){
if(strcmp(HashTable->buckets[position]->nick, nick) == 0)
return position;
else
position++;
if(position == fixed_p)
return -1;
if(position == HashTable->size)
position = 0;
}
}
user *get_item(hashtable *HashTable, char *nick){
user *item = malloc(sizeof(user));
int position = contains(HashTable, nick);
if(position != -1){
item = HashTable->buckets[position];
}
return item;
}
void delete(hashtable *HashTable, char *nick){
int position = contains(HashTable, nick);
if(position != -1){
HashTable->buckets[position]->occupied = false;
}
}
void display(hashtable *HashTable){
for(int i = 0; i<HashTable->size; i++){
printf("i: %d ", i);
if(HashTable->buckets[i]->occupied)
printf("nick: %s, name: %s\n",HashTable->buckets[i]->nick, HashTable->buckets[i]->name);
else
printf("nick: -, name: -\n");
}
}
Note: I posted this some hours ago, but then i noticed the implementation had some big flaws in the resize method so i deleted the post. The problem should be fixed now.
Lastest Edit: Since my implementation got "popular" and the presented one has flaws, i will share a link to my github containning the updated version
Updated code version: https://github.com/MiguelDordio/Data-Structures-Implementations/blob/master/hashtable.c
hash("ac") == hash("ca") == hash("bb")and many more. \$\endgroup\$