Hashing

Hashing

1. 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.

2. 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

3. 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.

4. Hash Key: the key that the hash function is applied to

5. Hashing: The process of applying a hash function to a key to generate a hash value

6. Collision: A collision occurs when two or more different keys hash to the same has value.

7. Open Hashing: Method in which a collision is resolved by storing the record in the "next available" location

8. 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.

9. 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.

10. 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.