/*! This file is auto-generated */ .wp-block-button__link{color:#fff;background-color:#32373c;border-radius:9999px;box-shadow:none;text-decoration:none;padding:calc(.667em + 2px) calc(1.333em + 2px);font-size:1.125em}.wp-block-file__button{background:#32373c;color:#fff;text-decoration:none} Problem 36 Write pseudocode for the inserti... [FREE SOLUTION] | 91影视

91影视

Log out

Learning Materials

Features

Discover

Chapter 13: Problem 36

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

Short Answer

Expert verified
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

01

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.
02

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.

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Over 30 million students worldwide already upgrade their learning with 91影视!

Key Concepts

These are the key concepts you need to understand to accurately answer the question.

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鈥攚hich could cause inefficiency and clutter鈥攁 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.

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

Define the following terms: disk, disk pack, track, block, cylinder, sector, interblock gap, read/write head.

What are mixed files used for? What are other types of primary file organizations?

What are the components of a disk block address?

Discuss the mechanism used to read data from or write data to the disk.

Suppose that we have an ordered file of fixed-length records and an unordered overflow file to handle insertion. Both files use unspanned records. Outline algorithms for insertion, deletion, and modification of a file record and for reorganizing the file. State any assumptions you make.
See all solutions

Recommended explanations on Computer Science Textbooks

Cybersecurity in Computer Science

Read Explanation

Computer Organisation and Architecture

Read Explanation

Issues in Computer Science

Read Explanation

Theory of Computation

Read Explanation

Algorithms in Computer Science

Read Explanation

Cloud Services

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.