Hashing is a data organization technique used to store and retrieve information efficiently. Instead of checking records one after another, hashing uses a key and a hash function to determine where the required data should be stored or searched.
The main strength of hashing is fast average-case access. Hash tables are commonly used for dictionaries, symbol tables, caches, database indexes and many other systems where data must be located quickly.
To understand hashing properly, it is important to learn how hash functions generate indexes, why collisions occur, how collisions are resolved, and how factors such as table size and load factor affect performance.
Hashing is the process of converting a key into a value that identifies a position in a hash table. The conversion is performed by a hash function.
For example, if a table has 10 positions, a simple hash function may calculate the index by taking the remainder after division by 10.
H(key) = key % 10
For a key value of 47:
H(47) = 47 % 10 = 7
Therefore, index 7 becomes the initial location associated with the key 47.
Hashing is a technique that transforms a key into a table index so that data can usually be inserted, searched and deleted efficiently.
As the amount of stored data increases, searching through records one by one becomes inefficient. A hash table attempts to avoid this by calculating the probable location of a record directly from its key.
Hashing is especially useful when the goal is to find an item by its exact key rather than to maintain all items in sorted order.
A key is the value used to identify a record. Examples include a student roll number, employee ID, username or product code.
A hash function converts the key into a table index or hash value.
Hash Function(key) = index
The result generated by the hash function is called a hash value. In a basic hash table, this value determines the slot where the record should be placed initially.
A hash table is the data structure containing the slots or buckets used to store records.
A hash function maps a key to a location in a hash table. A good hash function should be fast and should distribute keys as evenly as possible across the available table positions.
H(key) = key % 10
Using this function:
H(32) = 2 H(84) = 4 H(47) = 7
The initial positions for these keys are 2, 4 and 7 respectively.
Index Data 0 - 1 - 2 32 3 - 4 84 5 - 6 - 7 47 8 - 9 -
The table stores each key according to the index produced by the hash function. This simple arrangement works efficiently until two different keys produce the same index.
The same hashing logic is used during lookup. The key is hashed again, allowing the algorithm to begin searching from the appropriate table location.
The key is hashed to find its initial location. If the location is available, the record is inserted. If it is already occupied, collision handling is required.
The hash function is applied to the search key. The table then checks the appropriate location and, if necessary, follows the collision-resolution structure to find the required record.
The record is located using its key and removed. In open addressing, deletion requires special care because simply clearing a slot can incorrectly interrupt later searches.
| Operation | Average Case | Worst Case |
|---|---|---|
| Insertion | O(1) | O(n) |
| Searching | O(1) | O(n) |
| Deletion | O(1) | O(n) |
The O(1) values describe expected or average performance when keys are distributed well and the table is maintained at a suitable load factor. In a poor collision scenario, operations can degrade toward O(n).
The quality of a hash table depends heavily on its hash function. A useful function should distribute keys across the table instead of repeatedly sending many keys to the same few positions.
No practical hash function can guarantee that different keys will always produce different positions when the number of possible keys is larger than the number of table slots.
A collision occurs when two or more different keys are mapped to the same hash table index.
H(key) = key % 10 H(25) = 5 H(35) = 5
Both keys initially map to index 5. Because both records cannot simply occupy the same single position in a basic table, the hash table must use a collision-resolution technique.
A hash table contains a limited number of storage positions, while the set of possible keys may be extremely large. Therefore, different inputs can map to the same output position.
Collision frequency can also increase because of:
The two major approaches are separate chaining and open addressing. Open addressing includes several probing methods.
In separate chaining, each table position can store a collection of records rather than only one record. A linked list is a common teaching example, although real implementations may use other structures.
Using:
H(key) = key % 10
Insert the keys:
15, 25, 35
Each key maps to index 5:
Index 5 15 → 25 → 35
The colliding records are stored together in the bucket associated with index 5.
Open addressing stores all records inside the hash table itself. When the initial position is occupied, the algorithm follows a probing sequence to locate another available position.
The three common forms are linear probing, quadratic probing and double hashing.
Linear probing checks consecutive positions until an appropriate slot is found.
New Index = (Hash Value + i) % Table Size
Here, i represents the probe number.
Table Size = 10 H(key) = key % 10 25 → Index 5 35 → Index 5 (collision)
If index 5 is occupied, the algorithm checks index 6. If index 6 is empty, key 35 is stored there.
Quadratic probing changes the probe distance using a quadratic pattern instead of checking every immediately adjacent slot.
New Index = (Hash Value + i²) % Table Size
Suppose the original hash value is 5:
First probe: 5 + 1² = 6 Second probe: 5 + 2² = 9 Third probe: 5 + 3² = 14 % Table Size
The exact sequence depends on the table size and the probing formula used by the implementation.
Double hashing uses a second hash function to determine the step size after a collision. Different keys can therefore follow different probe sequences.
Index = (H1(key) + i × H2(key)) % Table Size
Where:
The second function must be designed carefully so that the probe sequence can reach suitable positions in the table.
The load factor indicates how full a hash table is.
Load Factor (α) = Number of Stored Elements / Table Size
Elements = 8 Table Size = 10 α = 8 / 10 = 0.8
A load factor of 0.8 means that the table contains eight stored elements for every ten primary table positions on average. As the load factor increases, collisions and probing costs generally become more significant.
Rehashing is the process of creating a larger table and redistributing existing elements when the current table becomes too crowded.
Rehashing has an expensive individual cost because many elements may need to be moved, but when resizing is managed appropriately, hash tables can still provide efficient amortized insertion performance.
Consider a table of size 10 using:
H(key) = key % 10
Insert the keys 25, 35 and 45 using linear probing.
25 % 10 = 5 Store 25 at index 5 35 % 10 = 5 Index 5 is occupied Check index 6 Store 35 at index 6 45 % 10 = 5 Index 5 is occupied Index 6 is occupied Check index 7 Store 45 at index 7
The final section of the table becomes:
Index 5 → 25 Index 6 → 35 Index 7 → 45
This example also shows why heavy use of linear probing can create clusters of consecutive occupied positions.
Hashing is widely used whenever software needs efficient access to information using an identifying key.
Programming language dictionaries and maps commonly use hash-table concepts to associate keys with values, such as mapping a username to account information.
Hash-based structures can support efficient equality lookups, especially when a system needs to locate records using exact key values.
Compilers must repeatedly locate information about variables, functions and identifiers. Hash tables are well suited to fast identifier lookup.
Caches often use keys to identify stored results. A hash-based structure can quickly determine whether a requested item is already available.
Hash values can help organize or compare large collections when detecting repeated items, subject to the requirements and collision guarantees of the chosen hashing method.
Cryptographic hash functions are used to produce fixed-length digests for integrity-related tasks. This is a specialized use of hashing and differs from ordinary hash-table indexing.
Secure password systems should store password-verification values rather than plain-text passwords. In practice, modern systems use dedicated password-hashing algorithms with salts and work factors designed specifically for password protection.
| Hash Table | Array |
|---|---|
| Access is generally based on a key and hash function. | Access is based on a numeric index. |
| Average key lookup can be O(1). | Direct access by a known index is O(1). |
| Collisions must be handled. | Different elements already have separate indexes. |
| Data is not naturally kept in sorted order. | Elements follow index order. |
| Hash Table | Binary Search Tree |
|---|---|
| Average exact-key lookup is commonly O(1). | Balanced tree lookup is O(log n). |
| Does not naturally maintain sorted order. | Maintains an ordered structure. |
| Not suitable for ordered range traversal. | Supports ordered traversal and range operations. |
| Performance depends on hashing and collision behavior. | Performance depends on tree balance. |
Hashing is a technique that maps a key to a location or value using a hash function. It is commonly used to support efficient average-case insertion, searching and deletion.
A hash table is a data structure that stores records in slots or buckets identified using hash values. It combines a hash function with a collision-resolution method.
A collision occurs when different keys map to the same table index. Since the number of possible keys is often much larger than the number of available slots, collision handling is an essential part of hash-table design.
Separate chaining stores colliding records together in a bucket associated with the same index. Open addressing keeps records inside the table and searches for another position through a probing sequence.
Load factor is the ratio of stored elements to table size. A higher load factor generally increases the chance or cost of collisions, so it is an important measure for maintaining hash-table performance.
Primary clustering occurs mainly in linear probing when consecutive occupied positions form long groups. New collisions are more likely to extend these groups, increasing probe lengths.
Double hashing uses a second hash function to determine the probe step. This helps different keys follow different search paths and can reduce clustering compared with simpler probing strategies.
Rehashing creates a new table, usually with greater capacity, and inserts existing elements again according to the new table configuration. It is commonly performed when the load factor becomes too high.
If many keys collide or are placed into long probe sequences or chains, an operation may need to examine many elements. In that situation, performance can approach linear time.
Hashing is a strong choice for frequent exact-key lookups when sorted order and range queries are not required. A balanced tree is often more suitable when ordered traversal, minimum or maximum queries, or range operations are important.
Hashing is an important data structure technique for organizing information around keys. A hash function converts a key into an initial table position, allowing records to be located efficiently without sequentially examining every stored item.
The main topics in hashing are hash functions, hash tables, collisions, chaining, open addressing, probing, load factor and rehashing. A well-designed hash table can provide excellent average-case performance, while poor distribution or excessive collisions can significantly reduce efficiency.
Understanding these concepts helps students use hash-based structures correctly and also provides a foundation for topics such as dictionaries, caches, database indexing, compiler symbol tables and specialized cryptographic hashing.