CS223: Data Structures - Hash Tables

Why Hashing?

• Many applications deal with large amounts of data and require efficient lookups, such as search engines and web pages.
• Typical data structures like arrays and lists may not be sufficient for handling efficient lookups.
• Hashing is used when lookups need to occur in near constant time, O(1).
• It is used in various applications, including web searches, spell checkers, databases, compilers, and password storage.

Hash Table

• A hash table is a data structure used to store key-value pairs to make lookups easy and efficient.
• It uses a hash function to compute an index into an array of slots from which the desired value can be found.
• The load factor is the number of keys stored in the hash table divided by the capacity.

Hash Functions

• A hash function maps an item to a slot in the hash table.
• A good hash function should avoid collisions, distribute keys evenly, and be simple and fast to compute.
• Different methods for choosing a good hashing function include the Division Method and Folding Methods.

Division Method

• This method uses the modulo operator (%) to map an integer to a value between 0 and m-1, where m is the table size.
• It is a popular method and the table size is often chosen as a prime number.

Folding Methods

• Folding methods involve dividing the key into equal-digit parts and then adding the parts to compute the hash value.
• There are two types of Folding Methods: Fold-Shifting and Fold-Boundary.
• Fold-Shifting adds the parts, while Fold-Boundary adds the parts after reversing the boundary parts.

Handling Collisions

• Collisions occur when two keys have the same hash value.
• There are two methods to handle collisions: Separate Chaining and Open Addressing.

Separate Chaining

• Each cell of the hash table points to a linked list of records that have the same hash function value.
• Advantages: simple to implement, hash table never fills up, and less sensitive to the hash function or load factors.
• Disadvantages: performance of chaining is not good, wastage of space, and uses extra space for links.

Open Addressing

• All elements are stored in the hash table itself, and the table size must be greater than or equal to the total number of keys.
• Open Addressing methods include Linear Probing, Quadratic Probing, and Double Probing.

Linear Probing

• In linear probing, we linearly probe for the next slot.
• If a slot is full, we try the next slot by adding 1 to the hash value.

Learn about hash tables, their importance, and applications in data structures, including search engines, spell checkers, and databases.