1. Registered User
Join Date
Apr 2008
Posts
1

## extendible hash ﬁle

and also example .. like how to put record in extendible hash file .

2. Registered User
Join Date
Oct 2002
Location
Posts
697
A hash table is a data structure, not a file format.

At its most basic, a hash table is defined as having N buckets, B records per bucket and each record being a predefined length in bytes. (Hash tables, by themselves, don't handle variable length records.)

Given a record R, a hash function H(R) calculates a number from 0 to N-1. That record is assigned to an empty slot within the bucket H(R).

The trick is in defining a a good hash function that avoids putting records in the same bucket.

The are plenty of things you can extend on a hash table because it's such a fundamental data structure. You probably mean extensible in terms of capacity.

The problem is that, usually, the hash function is generally based on N, so if you increase N to N' you've effectively created a new hash function H'(R), and all your current records are mishashed according to H'(R).

The solution I've generally seen is, as far as I'm concerned, a cheat: you use a trie instead of a hash table. Now, instead of H(R) returning a number from 0 to N-1, it returns a number from 0 to 2^X - 1 where X is something arbitrarily large like 16.

Now looking up a record involves getting the first, say, 8 bits of H(R). You have a root table with 256 (2^8) buckets. If one of those buckets fill up, it can create a secondary table that will be based on the next 8 bits of H(R). If, after deletion, these tables are empty, the space can be reclaimed allowing the hash table to shrink.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•