Hashing Basics

• Hashing is a Key to address mapping process.
• Hashing is the transformation of a string of characters into a usually shorter fixed-length value or key that represents the original string.
• Hashing is used to index and retrieve items in a database because it is faster to find the item using the shorter hashed key than to find it using the original value.

Terms must be familiarized.
Synonyms: The set of keys that hash to the same location.
Collision: A collision occurs when a hashing algorithm produces an address for an insertion key and that address is already occupied.
Home address: The address produced by the hashing algorithm is known as the home address.
Prime area: The memory that contains all of the home addresses is known as the prime area.
Probe: Each calculation of an address and test for success is known as a probe.
Hash table: Tables which can be searched for an item in O(1) time using a hash function to form an address from the key.

Hash function: Function which, when applied to the key, produces a integer which can be used as an address in a hash table.