Code 401 Class 30 Reading Notes

Intro to Hash Tables

1. Hash - A hash is the result of some algorithm taking an incoming string and converting it into a value that could be used for either security or some other purpose. In the case of a hashtable, it is used to determine the index of the array.
2. Buckets - A bucket is what is contained in each index of the index of the array of the hashtable. Each index is a bucket. An index could potentially contain multiple ke/value pairs if a collision occurs.
3. Collisions - A collision is what happens when more than one key gets hashed to the same location of the hashtable.

Why do we use them?

1. Hold unique values
2. Dictionary
3. Library

• A Bucket is a Node which holds both a key , and a value.

• A hash is the ability to encode the key that will eventually map to a specific location in the data structure that we can look at directly to retrieve that value.

Big O

• Typically O(n) when not knowing the indext of the information, because it requires searching through each piece of data to find the one piece we want.
• When we know the index of the information we want to access that information in O(1)

Class Notes

A hashtable is traditionally created from an array.

1. Add or multiply all the ASCII values together.
2. Multiply it by a prime number such as 599
3. Use modulo to get the remainder of the result, when divided by the total size of the array.
4. Insert into the array at the index.

Hash Table Lecture

• Keep track of the key, and then you will find the value

Things I want to know more about

Using Hash tables with Docker containers

<—BACK