813996
Hashing
- Hash Function:Is a function
H, applied to a key k, which
generates a hash value H(k)
of range smaller than the
domain of values of k.
- Hash Value: is the value generated
by the application of the hash
function to the key. This value can be
used as the hash table index where
the key and any associated data can
be stored if this table location is free
- Hash Table: The table gets it's
name from the method used to
determine the row to use. The
hash value generated by applying
the has function to the key is the
table index where the record
should be stored if the row is
free.
- Hash Key: the key that the
hash function is applied to
- Hashing: The process of
applying a hash function to a
key to generate a hash value
- Collision: A collision
occurs when two or
more different keys hash
to the same has value.
- Open Hashing: Method in
which a collision is
resolved by storing the
record in the "next
available" location
- Closed Hashing: In a collision the
other rows of the hash table are
closed to the colliding record which
must, instead, be attached to the
table slot in a chain or linked list of
other colliding records. The table
slat uses a pointer field to point to
the linked list.
- Rehashing: The key is hashed again
because the initial hash has resulted
in a collision. One method of
rehashing is to keep trying the next
location and so on (modulo length of
table) until a free slot is found in
which to store the record.
- Linear Rehash: The original hash
value is incremented by 1 modulo N,
then 2 modulo N, then 3 modulo N
and so on until an empty slot is found
in the table of size N rows.
0 comments
Want to create your own Mind Maps for free with GoConqr? Learn more.