Log out Go to App
Go to App

Learning Materials

Features

Discover

Chapter 13: Problem 34

Suppose that we have a hash file of fixed-length records, and suppose that overflow is handled by chaining. Outline algorithms for insertion, deletion, and modification of a file record. State any assumptions you make.

Short Answer

Expert verified
Insertion in a hash file involves computing bucket based on hash value of key and then placing record in this bucket or overflow chain. Deletion requires locating the target record through its hash value and removing it from its bucket or overflow chain, while reordering remaining records. Modification requires searching for the record, making necessary changes, and reinserting it (if key changes) or modifying it in place (if key remains unchanged).

Step by step solution

01

Algorithm for Insertion

First, calculate the hash value of the input record's key, which will provide the address of the bucket where this record should be inserted. Next, inspect the selected bucket. If it still has space, place the record in it. However, if it's full, add the record to the overflow chain associated with the bucket.
02

Algorithm for Deletion

Just like with insertion, start by finding the bucket that should contain the record that is to be deleted, by using the hash function. Browse the records in the mentioned bucket and its overflow chain until the required record is found. If the record isn't in either the bucket or the overflow chain, it means the record doesn't exist in the hash file. If the record is found, delete it and rearrange the records as needed. Consider whether the overflow chain can be shortened or even removed.
03

Algorithm for Modification

To modify a record, calculate the hash value of the record's key to specify the appropriate bucket. Search the bucket and its overflow chain for the record. If it couldn't be located, it then implies that the record does not exist. If the record is found, change the value of the record accordingly to complete the modification process. If the modification involves a key change, it may be necessary to relocate the record. In this case, delete the record first, modify it, then reinsert it back into the hash file using the insertion algorithm mentioned earlier.

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.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!

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

Load the records of Exercise 13.27 into an expandable hash file, using linear hash. ing. Start with a single disk block, using the hash function \(h_{0}=K \bmod 2^{0},\) and show how the file grows and how the hash functions change as the records are inserted. Assume that blocks are split whenever an overflow occurs, and show the value of \(n\) at each stage.

Can you think of techniques other than chaining to handle bucket overflow in external hashing?

Can you think of techniques other than an unordered overflow file that can be used to make insertions in an ordered file more efficient?

Suppose we want to create a linear hash file with a file load factor of 0.7 and a block. ing factor of 20 records per bucket, which is to contain 112,000 records initially. a. How many buckets should we allocate in the primary area? b. What should be the number of bits used for bucket addresses?

Write program code to access individual fields of records under each of the following circumstances. For each case, state the assumptions you make concerning pointers, separator characters, and so forth. Determine the type of information needed in the file header in order for your code to be general in each case. a. Fixed-length records with unspanned blocking. b. Fixed-length records with spanned blocking. c. Variable-length records with variable-length fields and spanned blocking. d. Variable-length records with repeating groups and spanned blocking. e. Variable-length records with optional fields and spanned blocking. f. Variable-length records that allow all three cases in parts \(c, d,\) and e.
See all solutions

Recommended explanations on Computer Science Textbooks

Big Data

Read Explanation

Databases

Read Explanation

Computer Network

Read Explanation

Data Structures

Read Explanation

Computer Systems

Read Explanation

Functional Programming

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.

Sign-up for free