5.3 Hashing and Hash Tables
Hashing is a fundamental technique used in computing to quickly access data stored in memory. It is based on a simple but powerful concept: mapping data to a specific location in memory so that it can be retrieved quickly and efficiently. The key idea behind hashing is to use a hash function that converts the input data, also called the 'key', into a unique index that corresponds to the memory location where the data is stored. This means that once the data is hashed and stored, it can be retrieved instantly by using the same hash function to calculate its index.
A hash function is a mathematical function that takes an input, usually a string or a number, and returns a fixed-size output, which is the hash value. The hash value is then used as an index to access the data in memory. The ideal hash function should distribute data evenly across the memory to avoid collisions, which occur when two keys are assigned the same index. However, finding the...