Welcome to our comprehensive guide on C Open Addressing! In this lesson, we'll delve into the fascinating world of Hash Tables, a crucial data structure used in various real-world applications. Whether you're a beginner or an intermediate learner, we've got you covered. Let's get started! 📝
Understanding Hash Tables 📝
Introduction to Open Addressing 📝
C Implementation of Open Addressing - Linear Probing 📝
C Implementation of Open Addressing - Quadratic Probing 📝
Advanced Topics 📝
Practical Applications 📝
What is the main advantage of using Hash Tables?
Hash Tables, also known as Dictionaries or Associative Arrays, are a data structure that allows efficient storage and retrieval of data using keys.
A Hash Table is an array-like structure where each index is associated with a key-value pair. The key is used to quickly locate the position of the associated value within the Hash Table.
Hash Tables play a vital role in many real-world applications such as databases, compilers, and web browsers, due to their ability to provide fast access to elements.
Open Addressing is a method used to resolve collisions (when two keys map to the same index) in Hash Tables.
Open Addressing works by rehashing (re-computing the hash function) and storing the key-value pair at a new index, if a collision occurs.
There are several types of Open Addressing techniques, including Linear Probing, Quadratic Probing, and Double Hashing. We will explore Linear Probing and Quadratic Probing in this lesson.
In Linear Probing, when a collision occurs, the next available index is searched sequentially starting from the next index.
#include <stdio.h>
#define SIZE 10
int hash(int key, int tableSize) {
return key % tableSize;
}
int linearProbe(int key, int currentIndex, int tableSize) {
return (currentIndex + 1) % tableSize;
}
void insert(int key, int value, int table[]) {
int hashIndex = hash(key, SIZE);
int currentIndex = hashIndex;
while (table[currentIndex] != -1) {
currentIndex = linearProbe(key, currentIndex, SIZE);
}
table[currentIndex] = key;
table[currentIndex + 1] = value;
}
void displayTable(int table[]) {
printf("Hash Table:\n");
for (int i = 0; i < SIZE; i++) {
if (table[i] != -1) {
printf("(%d, %d) ", table[i], table[i + 1]);
}
}
printf("\n");
}
int main() {
int table[SIZE] = {-1}; // Initialize table with -1 to denote empty slots
insert(10, 20, table);
insert(14, 35, table);
insert(18, 46, table);
displayTable(table);
return 0;
}In Quadratic Probing, when a collision occurs, the next available index is searched sequentially by skipping over a series of indices determined by the key.
#include <stdio.h>
#define SIZE 10
int hash(int key, int tableSize) {
return key % tableSize;
}
int quadraticProbe(int key, int currentIndex, int tableSize) {
int probe = 1;
while (table[(currentIndex + probe) % tableSize] != -1) {
probe += probe * probe;
}
return (currentIndex + probe) % tableSize;
}
void insert(int key, int value, int table[]) {
int hashIndex = hash(key, SIZE);
int currentIndex = hashIndex;
while (table[currentIndex] != -1) {
currentIndex = quadraticProbe(key, currentIndex, SIZE);
}
table[currentIndex] = key;
table[currentIndex + 1] = value;
}
void displayTable(int table[]) {
printf("Hash Table:\n");
for (int i = 0; i < SIZE; i++) {
if (table[i] != -1) {
printf("(%d, %d) ", table[i], table[i + 1]);
}
}
printf("\n");
}
int main() {
int table[SIZE] = {-1}; // Initialize table with -1 to denote empty slots
insert(10, 20, table);
insert(14, 35, table);
insert(18, 46, table);
displayTable(table);
return 0;
}In this lesson, we've covered Linear Probing and Quadratic Probing. However, there are other techniques like Double Hashing and Open Addressing with Chaining that you can explore further to deepen your understanding of Hash Tables.
Hash Tables are used extensively in real-world projects such as databases, web servers, and compilers. They offer fast access to data, making them essential for many applications that require efficient data management.
That's all for our comprehensive guide on C Open Addressing! We hope you found it helpful and informative. Happy coding! 🚀