﻿ C Program: Hash Table with Open Addressing

# C Program: Hash Table with Open Addressing

## C Program to implement Hash Tables: Exercise-7 with Solution

Write a C program that implements a hash table using open addressing techniques like linear probing or quadratic probing to resolve collisions.

Sample Solution:

C Code:

``````// Including necessary header files
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TABLE_SIZE 10

// Structure for a key-value pair
struct KeyValuePair {
char key[50];
char value[50];
};

// Structure for the hash table
struct HashTable {
int size;
int itemCount;
struct KeyValuePair* table;
};

// Function to create a new key-value pair
struct KeyValuePair createKeyValuePair(const char* key, const char* value) {
struct KeyValuePair newPair;
strcpy(newPair.key, key);
strcpy(newPair.value, value);
return newPair;
}

// Function to create a new hash table
struct HashTable createHashTable(int size) {
struct HashTable newTable;
newTable.size = size;
newTable.itemCount = 0;
newTable.table = (struct KeyValuePair*)calloc(size, sizeof(struct KeyValuePair));
return newTable;
}

// Hash function for strings (djb2 algorithm)
unsigned long hashFunction(const char* str) {
unsigned long hash = 5381;
int c;

while ((c = *str++) != '\0') {
hash = ((hash << 5) + hash) + c; // hash * 33 + c
}

return hash;
}

// Function to resolve collisions using linear probing
int linearProbe(int index, int attempt, int size) {
return (index + attempt) % size;
}

// Function to insert a key-value pair into the hash table using linear probing
void insert(struct HashTable* hashTable, const char* key, const char* value) {
if (hashTable->itemCount >= hashTable->size) {
printf("Hash table is full. Cannot insert more items.\n");
return;
}

unsigned long index = hashFunction(key) % hashTable->size;
int attempt = 0;

// Probe until an empty slot is found
while (hashTable->table[index].key[0] != '\0') {
attempt++;
index = linearProbe(index, attempt, hashTable->size);
}

// Insert the new pair
hashTable->table[index] = createKeyValuePair(key, value);
hashTable->itemCount++;
}

// Function to retrieve the value associated with a key
const char* retrieve(struct HashTable* hashTable, const char* key) {
unsigned long index = hashFunction(key) % hashTable->size;
int attempt = 0;

// Probe until the key is found or an empty slot is encountered
while (strcmp(hashTable->table[index].key, key) != 0 && hashTable->table[index].key[0] != '\0') {
attempt++;
index = linearProbe(index, attempt, hashTable->size);
}

if (strcmp(hashTable->table[index].key, key) == 0) {
return hashTable->table[index].value; // Key found, return the value
} else {
}
}

// Function to display the contents of the hash table
void displayHashTable(struct HashTable* hashTable) {
for (int i = 0; i < hashTable->size; i++) {
printf("[%d] -> (%s, %s)\n", i, hashTable->table[i].key, hashTable->table[i].value);
}
}

int main() {
struct HashTable hashTable = createHashTable(TABLE_SIZE);

// Insert key-value pairs
insert(&hashTable, "Red", "#ff0000");
insert(&hashTable, "Green", "#008000");
insert(&hashTable, "Blue", "#0000FF");
insert(&hashTable, "Yellow", "#FFFF00");
insert(&hashTable, "Orange", "#FFA500");

// Display the hash table
printf("Hash Table:\n");
displayHashTable(&hashTable);

// Retrieve and print values for specific keys
printf("\nValue for key 'Red': %s\n", retrieve(&hashTable, "Red"));
printf("Value for key 'Yellow': %s\n", retrieve(&hashTable, "Yellow"));
printf("Value for key 'White': %s\n", retrieve(&hashTable, "White"));

return 0;
}
```
```

Output:

```Hash Table:
[0] -> (Green, #008000)
[1] -> (Blue, #0000FF)
[2] -> (Orange, #FFA500)
[3] -> (, )
[4] -> (, )
[5] -> (, )
[6] -> (, )
[7] -> (, )
[8] -> (Red, #ff0000)
[9] -> (Yellow, #FFFF00)

Value for key 'Red': #ff0000
Value for key 'Yellow': #FFFF00
```

Explanation:

In the exercise above,

• Structures:
• KeyValuePair: Represents a key-value pair with fields for the key and value.
• HashTable: Represents the hash table with fields for size, item count, and an array of key-value pairs.
• Hash Function (hashFunction):
• Utilizes the djb2 algorithm to hash strings and generate an index.
• Probing Function (linearProbe):
• Resolves collisions using linear probing, which means it probes linearly through the array until an empty slot is found.
• createKeyValuePair Function:
• Creates a new key-value pair.
• createHashTable Function:
• Creates a new hash table with a specified size.
• insert Function:
• Inserts a key-value pair into the hash table.
• Uses the hash function to find an initial index and linear probing to handle collisions.
• retrieve Function:
• Retrieves the value associated with a key from the hash table.
• Utilizes the hash function and linear probing to find the correct index.
• displayHashTable Function:
• Displays the contents of the hash table.
• main Function:
• Create a hash table.
• Inserts several key-value pairs into the hash table.
• Displays the contents of the hash table.
• Retrieves and prints values for specific keys.

Flowchart:

C Programming Code Editor:

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.

﻿