Lecture 8: Hashing with Chaining

TL;DR

Hashing is a widely used and important data structure in computer science that allows for efficient searching, inserting, and deleting items. Chaining is a technique used to address collisions that can occur in hashing.

Transcript

The following content is provided under a Creative Commons license. Your support will help MIT OpenCourseWare continue to offer high quality educational resources for free. To make a donation or view additional materials from hundreds of MIT courses, visit MIT OpenCourseWare at ocw.mit.edu. PROFESSOR: All right. Let's get started. Today we start a ... Read More

Key Insights

• 👻 Hashing is a commonly used data structure in computer science that allows for efficient searching, inserting, and deleting operations.
• #️⃣ Chaining is a technique used to address collisions that can occur in hashing when multiple items hash to the same position in the hash table.
• 👂 The Division Method and Multiplication Method are common hashing methods used in practice, while Universal Hashing is more theoretically sound.
• #️⃣ The choice of hashing method and hash function can greatly impact the performance of a hash table.

Questions & Answers

Q: What is hashing and why is it important in computer science?

Hashing is a technique used to store and retrieve items based on their keys. It allows for efficient searching, inserting, and deleting operations, making it a fundamental component of many algorithms and data structures.

Q: What is chaining and how does it address collisions in hashing?

Chaining is a technique used to handle collisions that can occur when multiple items hash to the same position in the hash table. Instead of overwriting the items, chaining stores them in a linked list, allowing for multiple items to be stored at the same position.

Q: What are some common methods of hashing in Python?

The Division Method and Multiplication Method are commonly used hashing methods in Python. The Division Method uses modular arithmetic to map keys to positions in the hash table, while the Multiplication Method involves multiplying the key by a random number and using a bitwise operation to select a subset of bits for the index.

Q: What is Universal Hashing and why is it considered more theoretically sound?

Universal Hashing is a hashing technique that uses a randomly chosen hash function from a family of hash functions. It guarantees a low probability of collisions for any two distinct keys. While Universal Hashing is more theoretically sound, it may be less practical for everyday use due to the computational complexity of obtaining a large prime number and the need for random number generation.

Summary & Key Takeaways

• Hashing is an important data structure used in computer science that allows for efficient searching, inserting, and deleting items.

• Chaining is a technique used to handle collisions that can occur when multiple items hash to the same position in the hash table.

• The Division Method and Multiplication Method are common hashing methods used in practice, while Universal Hashing is a more theoretically sound approach.