Question

Write pseudocode for the insertion algorithms for linear hashing and for extendible hashing.

Short answer

The pseudocode for linear hashing involves calculating the hash index, checking if it falls within the table's range, and handling situations where splitting is required. Extendible hashing involves initializing a directory with one bucket, checking if inserted keys can fit or if the bucket can be split, handling instances where the directory cannot contain additional pointers, and adjusting if the hash function distributes keys unevenly.

Step-by-step solution

Linear Hashing Pseudocode

1. Start with an initial array of fixed size, usually of size M.\n2. For a new entry, calculate the hash index using a predetermined hash function.\n3. If the hash index is within the current range of the table and the bucket at the hash index is not full, insert the item there.\n4. If the bucket at the hash index is full, split the next bucket that hasn't been split yet and redistribute the items between the old and new buckets.\n5. If all buckets up to the current boundary have been split, double the size of the hash table and start splitting the buckets again from the beginning.

Extendible Hashing Pseudocode

1. Initialize directory with one bucket, holding all the keys.\n2. When a key is to be inserted and the bucket is full, see if the bucket can split.\n3. If bucket can split, create a new bucket and redistribute keys.\n4. If bucket cannot split because the directory referencing it cannot contain additional pointers, double the directory size. Hence, all buckets can now split using the additional least-significant bit.\n5. If any bucket, even after splitting, cannot fit the key, it means the hash function is distributing keys unevenly. A different hash function or mechanism may be needed.

Key concepts

linear hashing

Linear hashing is a dynamic hashing algorithm that grows in a linear manner, adapting its structure as the data changes. It is especially useful for handling data additions in database systems without requiring the entire structure to be rebuilt. Here's how it works:

• The algorithm starts with a fixed-size hash table.
• Entries are added using a hash function to determine their initial position within the table.
• When a bucket becomes full, rather than compressing the data or causing overflow errors, linear hashing introduces a bucket splitting process. Splitting involves spilling into new buckets, allowing the table's size to remain manageable and efficient.
• Over time, as more splits occur, the table can eventually be doubled in size to accommodate growing content without significant performance loss.

This approach allows the hash table to grow naturally and incrementally, distributing data more evenly across the structure.

extendible hashing

Extendible hashing provides a solution for dynamically handling bucket overflows. It uses a directory to manage how records are stored and accessed. This directory is flexible and expands as needed, unlike a traditional static array in fixed hashing.

• Keys are stored in a series of buckets. However, if a bucket becomes full, the solution isn't to merely add another bucket; instead, the system checks if the current bucket can be split.
• When splitting is possible, a new bucket is formed, and keys are reallocated based on new hash evaluations.
• If further division isn't feasible due to a directory's limitations (i.e., running out of pointers for bucket management), the directory itself is doubled. This growth allows for the division of additional buckets using further significant bits.

By doing so, extendible hashing scales efficiently while maintaining quick access and minimal disruptions in data retrieval processes.

directory

In extendible hashing, the directory plays a vital role in managing how buckets interact and are referenced. It's somewhat similar to an index in a book, pointing towards where data segments reside.

• The directory contains pointers that reference the data buckets.
• When a key is to be inserted and the corresponding bucket becomes full, it's the directory's duty to guide the hash operation toward either splitting the bucket or expanding itself.
• Growth of the directory occurs in a controlled manner, typically by doubling its size, which allows it to handle more keys efficiently without a total restructuring of the data view.
• The directory's dynamic nature ensures that even as data volume increases significantly, performance remains optimized by maintaining this pointer-guidance system.

In other words, the directory avoids the limitations of fixed-size array systems, providing a flexible framework that grows as complexity and data expand.

bucket splitting

Bucket splitting is an important mechanism in both linear and extendible hashing to handle overflow conditions where more space is required to store new data.

• When a bucket in the hash table is full, rather than forcing all new data into it—which could cause inefficiency and clutter—a bucket split occurs.
• In a split, the contents of the overflowing bucket are divided between it and a new bucket. The decision on where each piece of data goes is typically influenced by an adjusted hash function or additional bit considerations.
• This strategy not only eases current load pressures but also optimizes longer-term data distribution.
• As more data is added, more splits may occur, allowing the hash table to remain efficient, organized, and evenly balanced with respect to data access and storage loads.

Bucket splitting is therefore a key feature in maintaining balance and performance as datasets grow.