Data Structure

LECTURE # 9

OPEN ADDRESSING AND CHAINING IN HASHING

Introduction to Hashing

Hashing is a technique used to uniquely identify a specific object from a group of similar objects. It pertains particularly to data structures that provide efficient data retrieval. The core concept of hashing involves using a hash function to map data to a fixed-size array (hash table).

Applications of Hashing

1. Efficient data retrieval
2. Implementing associative arrays
3. Storing unique elements
4. Caching data for quick access

Hash Table

A hash table is an array of linked lists (or other structures) where each index is called a bucket. The hash function maps keys to buckets. However, collisions can occur when two keys hash to the same bucket, and this is where open addressing and chaining come into play.

Collision Resolution Techniques

1. Chaining

In chaining, each bucket of the hash table contains a linked list (or another data structure) that holds all the elements that hash to the same index. This means that if a collision occurs, we simply add the new element to the linked list of the corresponding bucket.

Advantages and Disadvantages of Chaining�

1. Simple to implement
2. Dynamic resizing is easier
3. Handles large numbers of collisions well

Disadvantages of Chaining

1. Requires additional memory for pointers
2. Performance can degrade if many elements hash to the same bucket

Implementation of Chaining�

#include <iostream>

#include <list>

#include <iterator>

#include <vector>

 class HashTable {

private:

int tableSize;

std::vector<std::list<int>> table; // Using a vector of lists

  std::cout << "nullptr" << std::endl;

std::cout << "Hash Table: " << std::endl;

public:

HashTable(int size): tableSize(size), table(size) {}

int hashFunction(int key) {

return key % tableSize; // Simple modulus hash function

}

  void insert(int key) {

int index = hashFunction(key);

table[index].push_back(key); // Insert into the list at the index

}

  bool search(int key) {

int index = hashFunction(key);

for (int item : table[index]) {

if (item == key) {

return true; // Key found

}

}

return false; // Key not found

}

  void remove(int key) {

int index = hashFunction(key);

table[index].remove(key); // Remove from the list at the index

}

  void display() {

for (int i = 0; i < tableSize; ++i) {

std::cout << "Bucket " << i << ": ";

for (auto item : table[i]) {

std::cout << item << " -> ";

}

}

}

};

 int main() {

HashTable ht(10);

ht.insert(5);

ht.insert(15);

ht.insert(25);

ht.display();

  std::cout << "Searching for 15: " << (ht.search(15) ? "Found" : "Not Found") << std::endl;

ht.remove(15);

std::cout << "After removing 15:" << std::endl;

ht.display();

  return 0;

}

2. Open Addressing

Open addressing is a method where all elements are stored directly in the hash table itself. If a collision occurs, the algorithm checks other buckets (using a probing sequence) until an empty bucket is found.

Common Probing Techniques

1. Linear Probing: Checks the next bucket sequentially.
2. Quadratic Probing: Checks buckets at increasing intervals (1, 4, 9, ...).
3. Double Hashing: Uses a second hash function to determine the step size.

 Advantages of Open Addressing

• More memory-efficient since no pointers are used.
• Better cache performance due to locality of reference.

Disadvantages of Open Addressing

• Clustering can occur, leading to longer search times.
• The table must have sufficient size to ensure performance.

Implementation of Open Addressing

#include <iostream>

#include <vector>

class OpenAddressingHashTable {

private:

int tableSize;

std::vector<int> table; // Holds the data

std::vector<bool> occupied; // Tracks occupied slots

public:

OpenAddressingHashTable(int size) : tableSize(size), table(size, -1), occupied(size, false) {}

int hashFunction(int key) {

return key % tableSize;

}

void insert(int key) {

int index = hashFunction(key);

while (occupied[index]) {

index = (index + 1) % tableSize; // Linear probing

}

table[index] = key;

occupied[index] = true;

}

bool search(int key) {

int index = hashFunction(key);

while (occupied[index]) {

if (table[index] == key) {

return true; // Key found

}

​

index = (index + 1) % tableSize; // Continue probing

}

return false; // Key not found

}

void remove(int key) {

int index = hashFunction(key);

while (occupied[index]) {

if (table[index] == key) {

occupied[index] = false; // Mark as deleted

return;

}

index = (index + 1) % tableSize; // Continue probing

}

}

void display() {

for (int i = 0; i < tableSize; ++i) {

if (occupied[i]) {

std::cout << "Index " << i << ": " << table[i] << std::endl;

} else {

std::cout << "Index " << i << ": nullptr" << std::endl;

}

}

}

};

int main() {

OpenAddressingHashTable ht(10);

ht.insert(5);

ht.insert(15);

ht.insert(25); // Triggers collision

std::cout << "Open Addressing Hash Table: " << std::endl;

ht.display();

std::cout << "Searching for 15: " << (ht.search(15) ? "Found" : "Not Found") << std::endl;

ht.remove(15);

std::cout << "After removing 15:" << std::endl;

ht.display();

return 0;

}

Thank You