1 of 10

Understanding and Using

Hash Tables

2 of 10

What’s a hash table?

  • Hash tables are data structures that allow you to store key-value pairs and quickly modify and access them.
    • A key is used to generate an index where your value will be stored.
      • This process is called “hashing”––hence, hash table.
  • JavaScript objects and Python dictionaries are implementations of hash tables.

​

3 of 10

Why use a hash table?

  • Unlike an array, you don’t have to search all of the way through a hash table*
    • They’re very fast!
  • They’re just as space-efficient as an array––O(n) space complexity.

​

* In the worst case, you might have to. More on this later.

​

4 of 10

What can you do with one?

Well, assume we have a JavaScript object (which is a hash table!).

let a = {}

We can...

​

​

​

​

​

Operation

Code

Insert a key-value pair

a['key'] = 'value';

Retrieve a value with a key

let value = a['key'];

Delete a key-value pair

delete a['key'];

5 of 10

Hash Tables: All O(1) Operations

All operations on hash tables are O(1)!

​

Operation

Code

Time Complexity

Insert a key-value pair

a['key'] = 'value';

O(1)

Retrieve a key at a value

let v = a['key'];

O(1)

Delete a key

delete a['key'];

O(1)

6 of 10

When are hash tables useful?

  • Hash tables are useful when the number of keys stored is small relative to the total number of key.
  • These are often helpful when dealing with large amounts of unorganized data.
    • Joe → 415-555-9874.
    • Jenna → 216-555-8481.
    • Maurice → ….

​

7 of 10

How do hash tables do it?

  • At a very high level… (this will be seen more in depth later).
    • Assume we want to store artists with their birthplace.
      • Take “Grace Hopper” and her birthplace “New York City, NY”
    • We might run a hash on “Grace Hopper” and get 2.
      • hash(‘Grace Hopper’) → 2.
    • We then store New York City, NY at the index 2.

​

  • More on this in later lessons!

​

​

0

1

2

3

4

key

Grace Hopper

val

New York City, NY

8 of 10

When might you want to use a hash table?

  • All the time!
    • Networking.
    • Databases.
    • Caching.
  • For example…
    • Data partitioning in distributed storage systems.
      • Hashing tables makes finding the correct data quicker and easier!

​

​

9 of 10

Review questions

  • Why should you use a hash table?
  • What’s the time complexity of a hash table?
  • What are some things you could use a hash table for?

​

​

10 of 10

What’s next?

  • We’ll learn how to implement a hash table!:�

https://docs.gowogle.com/presentation/d/1-zCx1fc5cUP6rklL-CrYzmO8ibcXztsOZxJUv3Fpd-s/edit?usp=sharing

​