Hash Tables: Structure and Collision Resolution — Topics & Learning Outcomes

Module Topics

Introduction to Hash Tables

• What Is a Hash Table? — A hash table is a data structure that stores data as key-value pairs, enabling efficient insertion, deletion, and lookup operations.
• The Concept of Hashing — Hashing is the process of converting a key into a numeric index using a function called a hash function, which determines where the key-value pair is stored in the underlying array.
• Key-Value Store as the Core Purpose — The primary purpose of a hash table is to serve as a key-value store, allowing programs to associate arbitrary keys with values and retrieve them quickly.
• Why Hash Tables Are Widely Used — Hash tables are one of the most commonly used data structures in software development because they offer average-case constant time performance for core operations.
• The Role of the Underlying Array — Internally, a hash table relies on a fixed-size array to store its data, with the hash function translating keys into valid array indices.

Internal Array-Based Design

• Arrays as the Foundation of Hash Tables — A hash table is built on top of a fixed-size array that serves as its underlying storage structure.
• The Role of Hash Functions — A hash function is the mechanism that converts a key into a numeric index, determining exactly where data is stored in the internal array.
• Mapping Keys to Indices — The process of converting a key to an array index typically involves computing a numeric value from the key and then applying the modulo operator to fit it within the array bounds.
• Storage and Retrieval Efficiency — Because the hash function computes the storage location directly, both inserting and looking up a value can ideally be done in constant time, O(1).
• Determinism and Consistency Requirements — A hash function must be deterministic, meaning it always produces the same output index for the same input key, every time it is called.

Hash Function Design and Properties

• Determinism: The Foundational Property — A hash function must be deterministic, meaning it always produces the same output for the same input.
• Uniform Distribution of Hash Values — A good hash function spreads keys as evenly as possible across all available buckets in the underlying array.
• Computational Speed — Hash functions must execute quickly because they are invoked on every insertion, lookup, and deletion operation.
• Common Hashing Techniques for Strings and Integers — Different data types require different hashing strategies to produce well-distributed integer indices.
• The Role of the Modulo Operation — After computing a raw hash value, the modulo operation maps that value into a valid array index within the table's bounds.
• Consequences of Poor Hash Function Design — A badly designed hash function can negate all the performance advantages that hash tables are meant to provide.

Collision Resolution: Chaining

• What Is Chaining? — Chaining is a collision resolution strategy where each slot in the hash table's underlying array holds a collection — typically a linked list — of all key-value pairs that hash to the same index.
• Inserting with Chaining — To insert a key-value pair, the hash function maps the key to an index, and the pair is appended to (or prepended to) the linked list stored at that bucket.
• Searching and Retrieving Values — To retrieve a value, the hash function identifies the correct bucket, and then the linked list at that bucket is traversed linearly until the matching key is found.
• Deleting Entries with Chaining — Deletion requires hashing the key to find the correct bucket, traversing the linked list to locate the target node, and then unlinking it from the chain.
• Load Factor and Its Effect on Chain Length — The load factor — the ratio of stored entries to the number of buckets — is the primary metric that governs how long chains grow and therefore how efficient chaining remains.
• Trade-offs of Chaining vs. Other Strategies — Chaining is straightforward to implement and handles high load factors more gracefully than open addressing, but it introduces memory overhead from storing list node pointers.

Collision Resolution: Open Addressing

• What Is Open Addressing? — Open addressing is a collision resolution strategy where all entries are stored directly within the hash table array itself, rather than in separate linked structures.
• Linear Probing — Linear probing resolves collisions by checking consecutive slots in the array, one at a time, until an empty slot is found.
• Quadratic Probing — Quadratic probing reduces clustering by increasing the step size quadratically rather than linearly when searching for an available slot.
• Double Hashing — Double hashing uses a second, independent hash function to determine the step size, producing a unique probe sequence for each key.
• Probe Sequences and Slot Selection — Each open addressing technique defines a probe sequence — the ordered list of slots examined until an empty one is found or the key is located.
• Handling Deletions in Open Addressing — Deleting an entry in an open addressing table requires care because simply clearing a slot can break the probe sequences of other keys.
• Load Factor and Performance in Open Addressing — The load factor — the ratio of stored entries to total table slots — has a direct and significant impact on open addressing performance.

Performance Analysis of Hash Tables

• Time Complexity of Core Operations — Hash table insertion, deletion, and lookup all have an average-case time complexity of O(1), making them highly efficient for most practical use cases.
• Understanding Load Factor — The load factor (λ) is the ratio of the number of stored elements to the total number of available buckets, and it is the primary driver of hash table performance.
• Impact of Collisions on Performance — Collisions occur when two or more keys hash to the same index, and their frequency directly determines how far actual performance diverges from the O(1) ideal.
• Average-Case Performance with Chaining — When using separate chaining for collision resolution, average-case performance is directly tied to the average length of each bucket's linked list.
• Average-Case Performance with Open Addressing — Open addressing eliminates separate chains but trades off by requiring the load factor to stay strictly below 1, since all elements must fit within the primary array.
• Worst-Case Performance and Pathological Inputs — Worst-case hash table performance is O(n) per operation and occurs when all keys hash to the same index, collapsing the structure into a linear search.
• Space Complexity and Resizing Costs — Hash tables have O(n) space complexity, but the underlying array is often allocated with extra capacity to maintain a healthy load factor, introducing a space-versus-time trade-off.

Implementing a Hash Table in JavaScript

• Setting Up the HashTable Class — The foundation of a JavaScript hash table implementation is a class that encapsulates an internal array and its size.
• Writing the Hash Function — A hash function converts a string key into a valid numeric index within the bounds of the internal array.
• Implementing the set Method with Chaining — The set method stores a key-value pair at the hashed index, using separate chaining to handle collisions.
• Implementing the get Method — The get method retrieves a value from the hash table by hashing the key and searching the appropriate bucket.
• Implementing the remove Method — The remove method deletes a key-value pair from the hash table while preserving other entries in the same bucket.
• Adding a keys Method to Iterate Entries — A keys method allows consumers to retrieve all stored keys, making the hash table iterable and more practical to use.
• Testing and Validating the Implementation — Systematic testing confirms that the hash table correctly stores, retrieves, updates, and removes key-value pairs under various conditions.

Student Learning Outcomes

By the end of this module, students will be able to:

Course Outcomes (reference)