Hash Table 해쉬 테이블

• A hash table uses a hash function to quickly search and save data.
  - The hash function computes an index (hash code) into an array of buckets or slots
• It is an abstract data that maps keys to values (similar to a dictionary!)
  - The Python dictionary actually uses an array internally
  • It uses the hash function to map the key to the value
• Python uses the hash(value) function to output a hash.
  - Divide this by array length N hash(value)%N to get the index
• Using this method can cause a collision (충돌) where two values will be assigned to the same index. This would erase the already added value.
  - There are two ways to resolve this issue:

1. Chaining (체이닝) where two values in the same index will be chained together: [None, None, (fast, '빠른')->(slow, '느린'), ...]
   

2. Open Addressing (개방 주소법) assigns the value in an empty space. If the hash for a new value is [3] but it is already assigned, it looks to the next value [4]. If [4] is assigned and [5] is empty, it is assigned to [5].