DBMS - Hashing: A Beginner's Guide

Hello, future database wizards! Today, we're going to dive into the magical world of hashing in Database Management Systems (DBMS). Don't worry if you've never written a line of code before – I'll be your friendly guide through this adventure. So, grab your virtual wands (keyboards), and let's get started!

What is Hashing?

Before we jump into the nitty-gritty, let's understand what hashing is all about. Imagine you're organizing a massive library. Instead of arranging books alphabetically, you decide to give each book a unique number based on its title. That's essentially what hashing does in databases – it converts data into a fixed-size value (called a hash) for easier storage and retrieval.

A Simple Hashing Example

Let's start with a basic Python example to illustrate hashing:

def simple_hash(string):
    total = 0
    for char in string:
        total += ord(char)
    return total % 10

print(simple_hash("Hello"))  # Output: 2
print(simple_hash("World"))  # Output: 7

In this example, we're creating a very simple hash function. It adds up the ASCII values of each character in the string and then uses the modulo operator to get a number between 0 and 9. This is a very basic form of hashing, but it gives you an idea of how it works.

Hash Organization

Now that we have a basic understanding of hashing, let's look at how it's organized in databases.

Hash Tables

Hash tables are the backbone of hash organization. Think of a hash table as a fancy array where each element (often called a bucket) can store multiple items.

Here's a simple implementation of a hash table in Python:

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(self.size)]

    def hash_function(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        hash_key = self.hash_function(key)
        self.table[hash_key].append((key, value))

    def get(self, key):
        hash_key = self.hash_function(key)
        for k, v in self.table[hash_key]:
            if k == key:
                return v
        return None

# Using our hash table
ht = HashTable(10)
ht.insert("apple", 5)
ht.insert("banana", 7)
print(ht.get("apple"))  # Output: 5
print(ht.get("grape"))  # Output: None

This hash table uses Python's built-in hash() function and modulo to determine where to store each key-value pair. When we want to retrieve a value, we use the same process to find where it should be stored.

Static Hashing

Static hashing is like having a fixed number of shelves in your library. You know exactly how many books you can store, but you might run into problems if you get too many books on one topic.

Pros and Cons of Static Hashing

Pros	Cons
Simple to implement	Can lead to uneven distribution
Fast for small datasets	Not flexible for growing datasets
Predictable performance	May waste space

Bucket Overflow

Sometimes, our hash function might send too many items to the same bucket. This is called bucket overflow, and it's like trying to cram too many books onto one shelf.

Handling Overflow

There are several ways to handle overflow:

1. Chaining: Each bucket contains a linked list of entries.
2. Open Addressing: If a bucket is full, we look for the next empty bucket.

Let's implement chaining in our previous hash table:

class ChainedHashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(self.size)]

    def hash_function(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        hash_key = self.hash_function(key)
        for item in self.table[hash_key]:
            if item[0] == key:
                item[1] = value
                return
        self.table[hash_key].append([key, value])

    def get(self, key):
        hash_key = self.hash_function(key)
        for k, v in self.table[hash_key]:
            if k == key:
                return v
        return None

# Using our chained hash table
cht = ChainedHashTable(10)
cht.insert("apple", 5)
cht.insert("banana", 7)
cht.insert("cherry", 3)
print(cht.get("apple"))  # Output: 5
print(cht.get("cherry"))  # Output: 3

In this implementation, each bucket can hold multiple key-value pairs, solving the overflow problem.

Dynamic Hashing

Dynamic hashing is like having a magical library that grows new shelves as you need them. It's more flexible than static hashing and can adapt to growing datasets.

Extendible Hashing

One popular form of dynamic hashing is extendible hashing. It uses a directory structure that can grow or shrink as needed.

Here's a simplified implementation of extendible hashing:

class ExtendibleHashTable:
    def __init__(self, bucket_size=2):
        self.bucket_size = bucket_size
        self.global_depth = 1
        self.directory = [[] for _ in range(2**self.global_depth)]

    def hash_function(self, key):
        return hash(key) % (2**self.global_depth)

    def insert(self, key, value):
        hash_key = self.hash_function(key)
        if len(self.directory[hash_key]) < self.bucket_size:
            self.directory[hash_key].append((key, value))
        else:
            self._split(hash_key)
            self.insert(key, value)

    def _split(self, index):
        self.global_depth += 1
        new_directory = [[] for _ in range(2**self.global_depth)]
        for i, bucket in enumerate(self.directory):
            new_index = i if i < index else i + 2**(self.global_depth-1)
            new_directory[new_index] = bucket
        self.directory = new_directory

    def get(self, key):
        hash_key = self.hash_function(key)
        for k, v in self.directory[hash_key]:
            if k == key:
                return v
        return None

# Using our extendible hash table
eht = ExtendibleHashTable()
eht.insert("apple", 5)
eht.insert("banana", 7)
eht.insert("cherry", 3)
eht.insert("date", 9)
print(eht.get("apple"))  # Output: 5
print(eht.get("date"))   # Output: 9

This implementation allows the hash table to grow dynamically as more items are added.

Organization and Operations

Now that we've covered the basics of hashing and some implementations, let's summarize the key operations and their complexities:

Operation	Average Time Complexity	Worst Case
Insert	O(1)	O(n)
Delete	O(1)	O(n)
Search	O(1)	O(n)

The average case is usually very fast, which is why hashing is so popular. However, in the worst case (when all items hash to the same bucket), performance can degrade to that of a linked list.

Conclusion

Congratulations! You've just taken your first steps into the world of hashing in DBMS. Remember, hashing is all about finding a balance between speed and space. It's a powerful tool that, when used correctly, can significantly speed up your database operations.

As you continue your journey in computer science, you'll encounter hashing in many other contexts – from password storage to caching systems. Each time you use a dictionary in Python or an object in JavaScript, you're benefiting from the magic of hashing!

Keep practicing, stay curious, and happy coding!

Credits: Image by storyset