Dynamic Array Chain Hashing
Original Publication Date: 1993-May-01
Included in the Prior Art Database: 2005-Mar-19
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.
Dynamic Array Chain Hashing
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.
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.
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.
Hashing is a variation on the Separate Chaining
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