Hashing: quick revision, 19 bites

Hashing: Direct Access for Fast Lookups

Instant data retrieval, no searching!

**Hashing** is a technique that maps data of any size to a fixed-size value (called a **hash code** or **hash value**) using a **hash function**. This hash value is used as an index to store and retrieve data in an array-like structure called a **hash table**. The goal is to achieve **O(1)** average time complexity for…

Takeaway. Hashing enables near-instant data access by mapping keys directly to storage locations.

Hash Function: The Core of Hashing

The magic that turns keys into indices.

A **hash function** $h(k)$ takes a key $k$ and returns an integer index within the range of the hash table (e.g., $0$ to $m-1$). A good hash function should be **fast to compute**, **minimize collisions**, and **distribute keys uniformly** across the table. Common examples include the **division method** (…

Takeaway. A good hash function is fast, uniform, and minimizes collisions.

O(1) Average Time Complexity

Constant time – the holy grail.

In a well-designed hash table, the **average time complexity** for search, insert, and delete operations is **O(1)**, independent of the number of elements. This is because the hash function directly computes the location, avoiding any sequential search. However, in the **worst case** (e.g., all keys collide), the time…

Takeaway. Hashing offers constant-time operations on average, but worst-case can be linear.

Collision: When Two Keys Map to Same Index

Different keys, same slot – a problem!

A **collision** occurs when two different keys $k_1$ and $k_2$ produce the same hash index ($h(k_1) = h(k_2)$). Collisions are inevitable if the number of possible keys exceeds the table size. Without handling, they cause data loss. Common mistake: ignoring collision resolution, leading to overwritten data or incorrect…

Takeaway. Collisions are unavoidable; proper resolution is essential.

Chaining: Handling Collisions with Linked Lists

Store multiple items in the same slot.

**Chaining** is a collision resolution method where each slot of the hash table contains a **linked list** (or another container). When a collision occurs, the new element is simply appended to the list at that index. To search, compute the hash index and then traverse the list to find the key.

Takeaway. Chaining uses linked lists to store multiple items per slot, making collisions manageable.

Open Addressing: Probing for Empty Slots

Find another slot when collision occurs.

**Open addressing** resolves collisions by probing (searching) for the next available slot in the hash table. Common probing techniques include **linear probing** (check next slot), **quadratic probing** (check slots at increasing offsets), and **double hashing** (use a second hash function). This avoids extra memory b…

Takeaway. Open addressing finds alternative slots within the table, avoiding extra memory but risking clustering.

Chaining vs. Open Addressing

Which collision strategy is better?

Takeaway. Chaining is simpler for deletion and handles high load factors, while open addressing saves memory.

Example: Division Method Hash Function

Simple hash function in action.

Suppose we have a hash table of size $m = 10$ and keys: 25, 34, 78. Using the division method $h(k) = k \bmod 10$:

Takeaway. The division method is straightforward: the remainder of the key divided by the table size.

Real-World Uses of Hashing

Hashing is everywhere in computing.

Takeaway. Hashing powers databases, caches, security, and compilers.

Simple Hash Table in Python (Chaining)

See hashing in code.

Takeaway. A basic hash table can be implemented with a list of lists for chaining.

Choosing a Good Table Size

Prime numbers reduce collisions.

When using the division method, choose a table size $m$ that is a **prime number** and not close to a power of 2. This reduces the chance of collisions because it avoids patterns in the keys. For example, $m = 11$ is better than $m = 10$ for many key sets.

Takeaway. Prime table sizes improve hash distribution and reduce collisions.

Remember: Hash = Index

Think of a library catalog.

Imagine a library where each book has a unique shelf number based on its title. Instead of searching the whole library, you go directly to the shelf. That's hashing: the hash function is the catalog that tells you the shelf number. **Hash → Index → Direct access**.

Takeaway. Hashing is like a library catalog: direct mapping to the storage location.

Hashing in Cryptography

Hashing secures your passwords.

Cryptographic hash functions (like SHA-256) are designed to be **one-way** and **collision-resistant**. They are used in digital signatures, blockchain, and password storage. Unlike data structure hash functions, they don't need to be fast; they need to be secure.

Takeaway. Cryptographic hashing prioritizes security over speed.

Ignoring Load Factor

Overfilling the table kills performance.

The **load factor** $\alpha = n/m$ (number of elements / table size) indicates how full the table is. As $\alpha$ approaches 1 (or exceeds 1 in chaining), collisions increase, and performance degrades. A common mistake is not resizing the table when the load factor gets too high. Best practice: resize (rehash) when…

Takeaway. Monitor load factor and resize to maintain O(1) performance.

Designing a Good Hash Function

Uniform distribution is key.

Takeaway. A good hash function is uniform, fast, and avoids clustering.

Hash Table as a Coat Check

Your ticket number is the hash.

At a coat check, you give your coat and receive a ticket with a number. When you return, you hand the ticket and get your coat instantly. The ticket number is like the hash index – it directly tells the attendant where to find your coat. No searching through all coats needed.

Takeaway. Hashing provides direct access, just like a coat check ticket.

Hash Functions are Not Reversible

You can't get the key from the hash.

A hash function is **one-way**: given a key, you can compute the hash, but given a hash, you cannot uniquely determine the original key. This is because multiple keys can map to the same hash (collision). Therefore, hashing is not encryption; it's for lookup, not security (unless it's cryptographic).

Takeaway. Hashing is one-way; don't confuse it with encryption.

Analyzing Hash Table Performance

Know your complexities for exams.

Takeaway. Remember: O(1) average, O(n) worst-case.

Rehashing: Resizing the Table

When the table gets full, rebuild.

**Rehashing** is the process of increasing the size of the hash table when the load factor exceeds a threshold. Steps: create a new table with a larger size (usually double), then re-insert all existing elements using the new hash function (since the table size changed, indices change). This is an O(n) operation but en…

Takeaway. Rehashing maintains efficiency by resizing the table when needed.