Results 1 to 2 of 2
  1. #1
    Join Date
    Apr 2008
    Posts
    1

    extendible hash file

    if any one know about extendible hash file .. then please can u direct me where i can find more information about extendible hash file.

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

  2. #2
    Join Date
    Oct 2002
    Location
    Baghdad, Iraq
    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
  •