• #### 科普

SCIENCE

#### 英语

ENGLISH

#### 科技

TECHNOLOGY

MOVIE

FOOD

#### 励志

INSPIRATIONS

#### 社会

SOCIETY

TRAVEL

#### 动物

ANIMALS

KIDS

#### 卡通

CARTOON

#### 计算机

COMPUTER

#### 心理

PSYCHOLOGY

#### 教育

EDUCATION

#### 手工

HANDCRAFTS

#### 趣闻

MYSTERIES

CAREER

GEEKS

#### 时尚

FASHION

• 精品课
• 公开课
• 欢迎下载我们在各应用市场备受好评的APP

点击下载Android最新版本

点击下载iOS最新版本

扫码下载译学馆APP

#### 数据结构：哈希表

Data Structures: Hash Tables

Hi, I’m Gayle Laakmann McDowell, author of Cracking the Coding Interview.

Today’s topic is one that you really don’t want to miss – hash tables.

A hash table is possibly the most useful data structure for interview questions.

It comes up all the time both in interviews and in real life.

In fact one technique I often tell people is just,

for any problem, have hash tables at the top of your mind as a possible technique to solve the problem.

So let’s talk a bit about what a hash table is.

At a high level a hash table is a key value lookup

So it gives you a way of, given a key, associating a value with it for very very quick lookups.

So suppose you had some situation where you needed to associate somebody’s name with some set of information about them.

A hash table would be the perfect solution for this problem because

you can just put this into the hash table and then you can say,

okay give me the data associated with Mary and then boom we can get that information immediately.

So in a hash table the key as well as the value can be basically any type of data structure.

A string is often used but it could be a circle, a square, a person,

pretty much anything, as long as you have a hash function.

So what does that mean? Well let’s turn to the implementation to talk about that.

So at a high-level we do want to store the objects in an array.So let’s picture that.

But how do we actually jump from a string to a particular index in the array?

Well that’s what a hash function does.

So a hash function takes in a string, converts into some sort of integer,

and then remaps that integer into an index into that array.

And then that’s where we can find the person we’re looking for.

So it’s important to understand that the hash code is not actually the index in this array.

We map actually from the key to the hashcode and then over to the index.

And one of the reasons for this is that the array that actually stores the data from the hash table

might be much much smaller than all the available potential hash codes.

And so we don’t want to have an array of three billion just because there’s three billion potential hash codes.

We actually remap it into something smaller.

Now note here that two different strings could actually have the same hash code

and that’s because there are an infinite number of strings out there but a finite number of hash codes.

So it’s theoretically possible for Alex and Sarah to actually have the same hash code.

Additionally since we’re remapping the hashcode into an even smaller index,

two things with different hash codes could actually wind up mapped to the same index.

So what do we do when this happens, which is called the collision?

There are different ways of resolving collisions and I really do encourage you to look this up on your own time,

but I’ll just talk about one of them which is called chaining.

And chaining is possibly the most common one and it’s very simple.

But it basically means is just, hey when there is collisions just store them in a linked list.

So rather than this being an array of people it’s actually going to be an array of a linked list of people.

And so that means though that when you get a call to say hey get the value of Alex,

you actually need to walk through all the values in that linked list, and pull out the value for Alex.

Now as you’ll note here this linked list contains not just the actual person objects

but the actual original keys as well.

And the reason for that is that if you only store the person object you’d see all these people who mapped to this index

but you wouldn’t know which one they are and so you actually just store the keys with them.

So when you get a call to say get me the value for Alex, then you actually call this hash function,

you get a hash code back, you map over to this index and then you walk through and look for the thing with the key of Alex.

So that is basics of how a hash table operates. So let’s walk through this from start to end.

We’re going to have this hash table class that underneath it has a array that actually holds the data.

And the array isn’t going to be an array of the actual values it’s going to be an array of the linked list of the values.

Then when someone says put the value of Alex, put the value 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 that gets us over to this index in the array

and then we put it into this linked list. If there’s nothing else, great, then we’re just going to have a one element linked list.

But there could be multiple values in there, in which case we walk through it.

Now what if there is already a value of Alex in there?

Well then we just fix that value immediately.

So let’s talk now about the runtime of a hash table.

Well it really depends on what we’re talking about and what assumptions we make.

In many cases we assume that we have a good hash table and a good hash function that really distributes our values well

and so for the purpose of an interview, we often just summarize this and say okay,

getting and setting in a hash table is constant time.

In reality if something weird happens we have a bad hash function blah blah blah,

we could also say it is linear time in the very worst case.

But for the purpose of 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.

So this is a bit of a high level view of what a hash table is and how it works.

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,

you start to put a ton of elements in the hash table, how does it grow with new elements?

Does it can be resized? All that sort of stuff.

I really do encourage you to go look at this stuff on your own time.

It’s a fantastic thing to really understand a lot of the complexity here.

But for the purpose of a lot of interview questions

we just sort of simplify all this down and summarize things as,

let’s assume we have a good hash table and so we get this beautiful constant-time insert find and delete.

So now that you understand the basics,

go ahead and do try to learn these more complex details of hash tables,

but also go practice some of these basics on your own time on your own problems.

Good luck