12- Hash Tables

Jun 21, 2026 10:38 · 3:44 · English · Whisper Turbo · 2 Выступающие

Этот протокол истекает сегодня. Модернизация для постоянного хранения →

Указатель лекций

0:03

S… Speaker 1 (12- Hash Tables)

In this video we're going to take a short break from Java and talk about one of the essential

0:07

S… Speaker 1 (12- Hash Tables)

data structures in computer science,

0:09

S… Speaker 1 (12- Hash Tables)

a hash table.

0:10

S… Speaker 1 (12- Hash Tables)

So let's say we have a list of customers,

0:14

S… Speaker 1 (12- Hash Tables)

let's import this,

0:17

S… Speaker 2 (12- Hash Tables)

and we set

0:21

S… Speaker 1 (12- Hash Tables)

this to a new array list.

0:22

S… Speaker 1 (12- Hash Tables)

Now in this list we could have hundreds or thousands of customers that

0:26

S… Speaker 1 (12- Hash Tables)

you read from a database.

0:27

S… Speaker 1 (12- Hash Tables)

Now let's say we want to look for a customer with a particular email.

0:30

S… Speaker 1 (12- Hash Tables)

To do that we have to write code like this.

0:33

S… Speaker 1 (12- Hash Tables)

You have to use a for each loop

0:36

S… Speaker 1 (12- Hash Tables)

For each customer in customers,

0:38

S… Speaker 1 (12- Hash Tables)

if customer .getEmail equals

0:42

S… Speaker 1 (12- Hash Tables)

let's say E1,

0:44

S… Speaker 1 (12- Hash Tables)

then perhaps we're going to return that customer or print a message

0:48

S… Speaker 2 (12- Hash Tables)

like found.

0:50

S… Speaker 1 (12- Hash Tables)

Now, this algorithm you see here for finding an object in a list is not

0:54

S… Speaker 1 (12- Hash Tables)

scalable.

0:55

S… Speaker 1 (12- Hash Tables)

Because the more objects we have in this list,

0:57

S… Speaker 1 (12- Hash Tables)

the longer this loop is going to take.

0:59

S… Speaker 1 (12- Hash Tables)

We're going to need more comparisons.

1:01

S… Speaker 1 (12- Hash Tables)

In the worst case scenario,

1:03

S… Speaker 1 (12- Hash Tables)

if this object,

1:04

S… Speaker 1 (12- Hash Tables)

if this customer we're looking for is at the end of the list,

1:07

S… Speaker 1 (12- Hash Tables)

we have to iterate the entire list to find that customer.

1:10

S… Speaker 1 (12- Hash Tables)

So in computer science,

1:12

S… Speaker 1 (12- Hash Tables)

we represent the cost of this algorithm using a special notation called

1:16

S… Speaker 1 (12- Hash Tables)

the big O notation.

1:18

S… Speaker 1 (12- Hash Tables)

It looks like this.

1:19

S… Speaker 1 (12- Hash Tables)

Big O of n,

1:22

S… Speaker 1 (12- Hash Tables)

where n is the number of items in our list.

1:25

S… Speaker 1 (12- Hash Tables)

So if you have,

1:26

S… Speaker 1 (12- Hash Tables)

let's say,

1:27

S… Speaker 1 (12- Hash Tables)

10 items in this list,

1:29

S… Speaker 1 (12- Hash Tables)

the cost of this algorithm is going to be O of 10,

1:32

S… Speaker 1 (12- Hash Tables)

because in the worst case scenario,

1:33

S… Speaker 1 (12- Hash Tables)

this customer we are looking for is at the end of the list,

1:36

S… Speaker 1 (12- Hash Tables)

so we need 10 comparisons to find that customer.

1:40

S… Speaker 2 (12- Hash Tables)

Now,

1:41

S… Speaker 1 (12- Hash Tables)

what if our list has 1 million customers?

1:43

S… Speaker 1 (12- Hash Tables)

Then the cost of this algorithm is going to be O of 1 million.

1:48

S… Speaker 1 (12- Hash Tables)

So the cost of this algorithm increases linearly and in direct

1:52

S… Speaker 1 (12- Hash Tables)

proportion with the size of the input.

1:54

S… Speaker 1 (12- Hash Tables)

That is why we're presented using big O of

1:58

S… Speaker 1 (12- Hash Tables)

N. Now this is where hash tables come to the rescue.

2:02

S… Speaker 1 (12- Hash Tables)

A hash table is a special data structure so we can use it to store data

2:06

S… Speaker 1 (12- Hash Tables)

like a bunch of customers.

2:07

S… Speaker 1 (12- Hash Tables)

But the way a hash table stores data is different from how a list or

2:11

S… Speaker 1 (12- Hash Tables)

an array stores data.

2:12

S… Speaker 1 (12- Hash Tables)

And for this very reason,

2:14

S… Speaker 1 (12- Hash Tables)

with a hash table,

2:15

S… Speaker 1 (12- Hash Tables)

we can quickly look up an object no matter how many objects we have stored in

2:19

S… Speaker 1 (12- Hash Tables)

the hash table.

2:20

S… Speaker 1 (12- Hash Tables)

So whether we have 10 customers or 1 million customers,

2:23

S… Speaker 1 (12- Hash Tables)

we can find a customer using only one comparison and we

2:28

S… Speaker 1 (12- Hash Tables)

represent it using the big O of one.

2:31

S… Speaker 1 (12- Hash Tables)

Now, technically there is no comparison involved when we look up an object using a

2:35

S… Speaker 1 (12- Hash Tables)

hash table, but you can think of it as a small computation step.

2:38

S… Speaker 2 (12- Hash Tables)

Now,

2:39

S… Speaker 1 (12- Hash Tables)

if you want to learn more about hash tables and how they work,

2:42

S… Speaker 1 (12- Hash Tables)

take my data structures and algorithms course.

2:44

S… Speaker 1 (12- Hash Tables)

I've covered this topic in so much depth there.

2:47

S… Speaker 1 (12- Hash Tables)

This is one of the subjects that is taught to computer science students.

2:50

S… Speaker 1 (12- Hash Tables)

So if you're a self -taught developer,

2:52

S… Speaker 1 (12- Hash Tables)

if you didn't attend a college or university,

2:54

S… Speaker 1 (12- Hash Tables)

I highly encourage you to take this course because it comes up in coding interviews

2:58

S… Speaker 1 (12- Hash Tables)

all the time.

2:59

S… Speaker 1 (12- Hash Tables)

So this is all about hash tables.

3:01

S… Speaker 1 (12- Hash Tables)

Now in Java,

3:02

S… Speaker 1 (12- Hash Tables)

we have an interface called map,

3:05

S… Speaker 1 (12- Hash Tables)

which represents a hash table.

3:07

S… Speaker 1 (12- Hash Tables)

So in Java,

3:09

S… Speaker 1 (12- Hash Tables)

we call them maps or hash maps.

3:11

S… Speaker 1 (12- Hash Tables)

In C sharp,

3:12

S… Speaker 1 (12- Hash Tables)

we call them dictionaries.

3:13

S… Speaker 1 (12- Hash Tables)

In Python,

3:14

S… Speaker 1 (12- Hash Tables)

we also call them dictionaries.

3:16

S… Speaker 1 (12- Hash Tables)

In JavaScript,

3:17

S… Speaker 1 (12- Hash Tables)

we call them objects.

3:19

S… Speaker 1 (12- Hash Tables)

So the objects that we create in JavaScript,

3:22

S… Speaker 1 (12- Hash Tables)

they're actually hash tables.

3:23

S… Speaker 1 (12- Hash Tables)

For example,

3:24

S… Speaker 1 (12- Hash Tables)

if you create a person object like this and give it a name,

3:29

S… Speaker 1 (12- Hash Tables)

This is represented using a hash table under the hood.

3:32

S… Speaker 1 (12- Hash Tables)

So different languages call it different things but essentially it's the same thing,

3:36

S… Speaker 1 (12- Hash Tables)

it's a hash table.

3:37

S… Speaker 1 (12- Hash Tables)

In the next video I'm going to show you how to use the map interface in Java.

Эта запись была составлена АИ (автоматическое распознавание речи). Политика МА

❤️ Любите STT.ai? Расскажите друзьям!

Резюме

Нажмите Нажмите Обобщение для составления резюме этой стенограммы.

Спросите AI об этом писце

Спросите что - нибудь об этой стенограмме — МА найдет соответствующие разделы и ответ.

Переписать другое