1. Hash Table

사실 hash table은 독립적인 섹션이라 깊게 배우지는 않고 그냥 개념만 짚고 넘어가려고 한다.

What is a Hash table?

• Hash tables are used to store key-value pairs.
• They are like arrays, but the keys are not ordered.
• Unlike arrays, hash tables are fast for all of the following operations: finding values, adding new values and removing values.

Why should I care?

• Nearly every programming language has some sort of hash table data structure. Because of their speed, hash tables are very commonly used.

Real Usage

• Imagine we store color code in the array. But color code looks like this #ff69b4 . So it would be nice if instead of using indices to access the color, we could use human readable keys. So color[‘pink’] = #ff69b4 is much better than color[0] = #ff69b4

Hash function

• To implement a hash table, we’ll be using an array. In order to look up values by key, we need a way to convert keys into valid array indices. A function that performs this task is called a hash function. So when we push a string, for example, pink into the function, it should consistently give the same number. otherwise whole thing will be broken.

What makes a good Hash function?

• Fast. constant time
• Doesn’t cluster outputs at specific indices, but distributes uniformly
• Deterministic (Same input yields same output)

정리하자면, Hash Table를 이용하면 원하는 정보를 O(1)의 속도로 얻을 수 있다.