Hashing

Hashing is a technique used in database management systems (DBMS) to quickly locate a data record given its search key. This method transforms a search key into an address in the hash table using a hash function. Hashing is highly efficient for queries that involve exact matches and is widely used in applications such as indexing, cache retrieval, and hash joins in databases.The hashing technique utilizes an auxiliary hash table to store the data records using a hash function.

1. Hash Function

A hash function is a mathematical algorithm that converts an input (or 'key') into a fixed-size string of bytes. The output, typically called a hash code, is used as an index into an array (hash table) where the actual data is stored.

2. Hash Table

A hash table is an array-like data structure where data is stored. Each slot in the hash table is called a "bucket" or "slot," and it can store one or more records.

3. Buckets

Buckets are the individual storage locations within a hash table where records are stored.

Methods of Hashing

1. Direct Hashing

Direct hashing assigns a unique hash value to each key without any computation. This method is feasible when the key space is small and manageable.

Example:

If keys are in the range 0 to 99, each key directly maps to an array index.

2. Modulo Division Hashing

Modulo division hashing uses the remainder of the key divided by the table size as the hash value.

Hash Function: h(k)=kmod n where k is the key and n is the number of buckets.

Example:

Key = 123, Table size = 10
Hash value = 123 % 10 = 3

3. Mid-Square Hashing

Mid-square hashing involves squaring the key and extracting the middle part of the result as the hash value.

Steps:

Square the key.
Extract the middle part of the squared value.

Example:

Key = 56
Squared value = 3136
Extract middle digits (13) as the hash value.

4. Folding Hashing

Folding hashing divides the key into equal parts, adds these parts together, and uses the result modulo the table size as the hash value.

Steps:

Divide the key into equal parts.
Add the parts together.
Apply modulo operation with the table size.

Example:

Key = 987654
Divide into parts: 98, 76, 54
Sum = 98 + 76 + 54 = 228
Hash value = 228 % 10 = 8

Types of Hashing

Static Hashing

Static hashing is a database management technique in which a fixed-size hash table is used to map keys to data records using a hash function. The hash table size and structure remain constant, irrespective of the number of records stored. This means that the number of buckets or slots available for data storage does not change dynamically, even if the database grows or shrinks over time.

Hash Function: A hash function h is used to map a key (e.g., a database record identifier) to a bucket index. The function should distribute keys uniformly across the buckets to minimize collisions (i.e., multiple keys hashing to the same bucket).

Buckets: These are the storage units that hold the records. In static hashing, the number of buckets is fixed at the time of creation and does not change dynamically.

Collisions: When two keys hash to the same bucket, a collision occurs. Static hashing must handle collisions using techniques like chaining (linked lists) or open addressing (probing).

Working of Static Hashing

Initialization: Determine the number of buckets (let’s say N). Choose a hash function that maps keys to an index between 0 and N-1.
Insertion:
- Apply the hash function to the key to get a bucket index.
- Place the record in the corresponding bucket. If the bucket already contains records, handle the collision using the chosen method (e.g., chaining).
Search:
- Apply the hash function to the key to get the bucket index.
- Search within the bucket for the desired record. This search can be linear or use more sophisticated structures like binary search if the bucket is kept sorted.
Deletion:
- Apply the hash function to find the bucket.
- Search for the record within the bucket and remove it. Adjust any linked list or probing structures accordingly.

Advantages of Static Hashing

Simplicity: Easy to implement and understand.
Performance: Provides O(1) average time complexity for search, insertion, and deletion operations in ideal conditions.
Predictability: Since the number of buckets is fixed, memory allocation can be planned and managed efficiently.

Disadvantages of Static Hashing

Fixed Size: The number of buckets is fixed, which can lead to inefficiencies. If the number of records grows significantly, many records will end up in the same bucket, leading to increased search times (collisions).
Memory Waste: If the number of records is much smaller than the number of buckets, a lot of space may be wasted.
Rehashing Complexity: If the hash table becomes too full, rehashing (creating a new, larger hash table and re-inserting all records) can be complex and time-consuming.

Collision Resolution Techniques in Hashing

Collision resolution is a critical aspect of hashing because even with a good hash function, collisions (where different keys hash to the same index) are inevitable.

1. Open Hashing (Chaining)

In Open Hashing, there is a method called Chaining. Chaining makes use of the link list data structure to store the newly added key to the index where the collision occurs.

How It Works:

When a collision occurs, the new entry is added to the linked list at that index.
During lookup, the hash index is found, and the linked list is traversed to find the entry.

Advantages:

Simple to implement.
The hash table can accommodate more entries than there are buckets.

Disadvantages:

Requires additional memory for pointers.
Performance degrades if many entries hash to the same bucket, leading to long chains.

2. Open Addressing

In open addressing, all entries are stored within the hash table itself. When a collision occurs, the algorithm probes for the next available slot according to a probing sequence.

a. Linear Probing

In Linear probing the key is added to the next available(empty) index. First the key is stored in h(k)+1 slot . If collision occurs, the key is stored in h'(k) slot, where,

h’(K)=(h(k)+i) mod size

h(k)=k%size

i=1,2,3.....

Example

Let us consider a hash function h(k)=k mod 10 , with keys 33, 55, 22, 43,79,19,42. Insert in bucket using Linear Probing.

Solution:

The table size will be of 0-(n-1)=0-9

33 mod 10=3—---------33 will go in bucket 3

55 mod 10=5

22 mod 10=2

43 mod 10=3—------here as bucket 3 is already occupied, so collision occur . this can be resolved using Linear Probing.

We apply, h’(K)=(h(k)+i) mod 10

=(3+1) mod 10=4

43 will go in bucket 4

0 19
1
2 22
3 33
4 43
5 55
6 42
7
8
9 79

b. Quadratic Probing

Quadratic probing is an open-addressing scheme where we look for the i2'th slot in the i'th iteration if the given hash value x collides in the hash table.

If a collision occurs at index i, the algorithm checks slots (h(k) + i^2) % table_size, where i=1,2,3.....

Example

Let us consider a hash function h(k)=k mod 10 , with keys 42,16,91,33,18,27,36,69. Insert in bucket using Quadratic Probing.

Solution:

The table size will be of 0-(n-1)=0-9

42 mod 10=2—---------42 will go in bucket 2

16 mod 10=6

91 mod 10=1

33 mod 10=3

18 mod 10=8

27 mod 10=7

36 mod 10=6—------here as bucket 6 is already occupied, so collision occur . this can be resolved using Quadratic Probing.

We apply, h’(K,i)=(h(k)+i^2) mod 10

=(6+1) mod 10=7—----here bucket 7 is already occupied , so we increase the value of i to 2

=(6+4) mod 10=0

Hence 36 goes to bucket 0

43 will go in bucket 4

0 36
1 91
2 42
3 33
4
5
6 16
7 27
8 18
9 69

c. Double Hashing

Double hashing is a collision resolution technique used in hash tables. It works by using two hash functions to compute two different hash values for a given key. The first hash function is used to compute the initial hash value, and the second hash function is used to compute the step size for the probing sequence.

In Double Hashing there are two hash functions, Let us consider h1(k) = k mod 11 where n should be prime and h2(k) = 8-(k mod 8) where n should be less than n and result is stored in (h1(k) + ih2(k)) mod 11.

Example

For example, if keys are 20, 34, 45, 70, and 76.

20 mod 11=9

34 mod 11=1

45 mod 11=1 —--------here collision occur so calculate h2(k)

h2(k)=8-(45 mod 8)=8-5=3

(h1(k)+ih2(k))mod 11=(1+1*3)mod 11=4

70 mod 11=4 —----so next slot will be 6(calculate yourself)

56 mod 11=1—-----so next slot will be 3 (calculate yourself)

0
1 34
2
3 56
4 45
5
6 70
7
8
9 20
10

2. Dynamic Hashing

Dynamic hashing is an advanced hashing technique used in Database Management Systems (DBMS) to overcome the limitations of static hashing. It allows the hash table to expand and contract dynamically as the number of records grows or shrinks. This adaptability ensures better performance and efficient use of memory.

Static Vs Dynamic Hashing in DBMS

Static Hashing	Dynamic Hashing
In static hashing, hash tables have a fixed size. When a table is filled up, an overflow page is allocated to take in the brimming data.	Dynamic hashing employs an alternative methodology. Instead of being fixed, dynamic hash tables grow to hold more data.
Because static hashing only requires two input/output operations—read and write—it is a quick way to perform insert and delete operations.	If a dynamic hash table is empty, it can be resized to save memory usage.
The overflow chain can grow rather lengthy if the hash table isn’t optimized, which will lower performance and complicate scaling.	The advantage of dynamic hashing lies in its flexibility: you don’t have to plan its size in advance