Data Structures and Algorithms: BRIDGES

Hashing is a method used to store and retrieve records in a database based on a search key value. It enables operations like insertion, deletion, and searching, which can be performed in constant time when properly implemented. A well-tuned hash system typically examines only one or two records for each search, insert, or delete operation, outperforming other methods like binary search on a sorted array or a binary search tree with O(logn) average costs. Despite its simple concept, proper implementation of hashing can be challenging, requiring designers to pay close attention to all the details involved.

In a hash system, records are stored in an array known as a hash table (HT). Hashing involves computing a hash function (denoted as h) on a search key K to identify the position in HT where the record with key K should be placed. As records are stored based on the address calculation, they are not ordered by value. Each position in the hash table is referred to as a slot, with the number of slots denoted by M, starting from 0 to M-1.

The primary goal of a hashing system is to ensure that for any key value K and hash function h, the resulting position i=h(K) in the table is such that 0≤i Less than M, and the key of the record stored at HT[i] is equal to K.

However, hashing may not be suitable for applications that permit multiple records with the same key value or when answering range searches. It cannot easily find all records within a specific range or determine the minimum or maximum key value or visit records in key order. Yet, hashing excels at answering exact-match queries, making it the preferred search method for such applications when implemented correctly. Despite its efficiency, there are various approaches to hashing, and inefficient implementations can be devised. Hashing is suitable for both in-memory and disk-based searching and is one of the most widely used methods for organizing large databases stored on disk, alongside the B-tree.

Here is a link to the OpenDSA textbook that has some sample hash functions: Read Me¹