Browse Prior Art Database

Dynamic Array Chain Hashing

IP.com Disclosure Number: IPCOM000104622D
Original Publication Date: 1993-May-01
Included in the Prior Art Database: 2005-Mar-19
Document File: 2 page(s) / 101K

Publishing Venue

IBM

Related People

Popham, JD: AUTHOR

Abstract

This algorithm describes a means of storing colliding identifiers in a hashing function within an array chain suspended from a "parent" element in the hash table.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 51% of the total text.

Dynamic Array Chain Hashing

      This algorithm describes a means of storing colliding
identifiers in a hashing function within an array chain suspended
from a "parent" element in the hash table.

      A collision will be defined as a situation within the context
of a hashing algorithm in which two identifiers have been pointed to
the same storage location within the hash table by the hashing
function.  In a standard hashing algorithm, a secondary function
would be used to find a new storage location for the colliding
identifier.  If the new location is similarly occupied, the process
is repeated until an open element is found.

      In the Separate Chaining algorithm, a hashing algorithm's
collision resolution scheme avoids the use of a secondary hash by
storing colliding records in a linked list depending from the
"parent" element (i.e. the storage location pointed to by the primary
hash function) in the hash table.

      Array Chain Hashing is a variation on the Separate Chaining
algorithm.

      In Array Chain Hashing, collisions are resolved by storing the
colliding records in an array chain rather than in a linked list.

1.  When an initial collision occurs for an element within the hash
    table, a small "base" sized array (for example, large enough to
    hold four elements) is allocated and the colliding record stored
    in it.  This array will be pointed to by the "parent" element
    within the hash table.

2.  As more collisions occur against the parent element, causing more
    records to be stored in the "child" array (or base1), the base1
    array is kept in sorted order by means of an Insertion sort or
    other simple sorting method.

3.  When base1 is filled, a second "base" size array is allocated
    (base2).  Base2 is pointed to from base1, thus building the first
    two links of an array chain.

4.  When base2 (also kept in sorted order) becomes full, a new array
    twice the size of the two base arrays is allocated (exp1).  The
    base1 and base2 arrays are merged into this new array in sorted
    order.  Exp1 is pointed to by the parent element in the hash
    table, and the storage used by the two base arrays is released.
    In this algorithm, this process, i.e. any series or chain
    reaction of merging arrays is called "array compression".  No two
    arrays of the same size larger than base size may exist within
    the same array chain without undergoing compression.  The
    behavior of the arrays in compression is very similar to the
    behavior of record strings in the Tape Sort algorithm.

5.  With exp1 allocated and filled, a new base1 array may by
    allocated and depended from exp1 for storage of additional
    collisions.  The largest child array (in this case exp1) will
    always be pointed to by the parent element.

6.  Additions may continue until base1 and a new base2 have been
    filled....