Table of Contents

Vocabulary

Hashing Hash Function Keys Hash Table/Array Collisions Chaining/Linear Probbing

What Is Hashing?

<aside> đź’ˇ Hashing involves using a hash function to map keys to a certain location in a hash table. ****Hash tables are similar to dictionaries and can be thought of as implementing a dictionary using a hash function.

</aside>

Hashing Implementation

<aside> 💡 One example of a hash function is modulo where given a hash table of a certain size and a number $x$, $x$ will be modded by another number. The result will determine $x$’s placement in the hash table.

</aside>

Modulo Hash Function Example

<aside> đź’ˇ Given a hash table of size 4 and a hash function that takes in a key, $k$, and mods it by 4, draw the hash table when inserting the keys in the following order: 20, 35, 41, 62, 120.

Hashing Steps:

  1. Draw out the hash table with the appropriate before inserting the keys. In this example, the hash table is of size 4 with the locations being 0,1,2,3 as those are the possible results when modding a number by 4.
  2. Run the hash function on a key to determine where it will be inserted in the hash table. For instance, when running the hash function on 20, we get a result of 0 (20 % 4 = 0).
  3. Now insert the key based on the result of the hash function. In this case, 20 will be inserted into the 0 location of the table.
  4. Repeat Steps 2 and 3 until there are no more keys to insert.

</aside>

IMG_7115.jpg

Dealing With Collisions

<aside> 💡 When running our hash function on 120, we encounter that 120 also needs to be stored in the 0 location of the hash table. When multiple keys are stored in the same location, this is known as a collision. When encountering collisions, chaining (also known as linear probbing) is applied where a linked list is created with the keys in the same location, serving as a “bucket” of values.

</aside>

Time Complexity

Operation Hash Table (w/ chaining)
insert() $O(n)$
search() $O(n)$

<aside> 💡 Of course, the best case for hashing would be $O(1)$ for insertion and searching if there was no chaining. However, taking chaining into consideration, insertion and searching a hash table would take $O(n)$ respectively. You’ll have to iterate through each and every single key in a certain location to find a desired key. For insertion, you’d have to go through each and every single key to determine if the desired key has already been inserted beforehand.

</aside>