Data Structures: Hash Tables

Hash Tables

In this video, Gayle Laakmann McDowell discusses hash tables as a data structure for interview questions. She explains how hash tables work and their implementation.

What is a Hash Table?

• A hash table is a key-value lookup that associates a value with a key for quick lookups.

• The key and value can be any type of data structure, but they need to have a hash function.

• A hash function takes in a string, converts it into an integer, and remaps that integer into an index in an array where the person we're looking for can be found.

Collision Resolution

• Two different strings could have the same hash code, and two things with different hash codes could wind up mapped to the same index. This is called collision.

• Chaining is one way of resolving collisions by storing them in a linked list.

• When getting the value of Alex from the linked list, you call the hash function to get the hash code back, map over to this index, then walk through and look for the thing with the key of Alex.

Implementation

• The hash table class has an array that holds data. It's not an array of actual values but rather an array of linked lists of values.

• When someone puts the value of Alex mapping to this person, we call this hash code function that gets us back the hashcode. Then we map from this hash code over to an index and put it into this linked list.

Overall, understanding how to use and implement a hash table is essential for solving many interview questions.

Hash Tables

This section provides an overview of hash tables, including how they work and their time complexity.

Understanding Hash Tables

• A hash table is a data structure that stores key-value pairs.

• The keys are hashed to generate an index where the value is stored.

• Retrieving values from a hash table is done in constant time, making it efficient for large datasets.

• In the worst-case scenario, when there's a bad hash function or collision, retrieving values can take linear time.

Time Complexity

• For interview purposes, we assume that getting and setting in a hash table is constant time.

• In reality, if something weird happens like having a bad hash function or collision, it could be linear time in the very worst case.

• However, for most problems we generally talk about constant time because in the real world we're going to make pretty sure hopefully that we have a good hash table.

Complexity Details

• There's a whole lot of complexity you can dive into here about different ways of handling collisions and exactly what happens when a hash table starts to put a ton of elements in the hash table.

• How does it grow with new elements? Can it be resized? All that sort of stuff.

Encouragement

• It's encouraged to learn more complex details of hash tables on your own time as well as practice some basics on your own problems.