해시테이블 이란?

  1. 데이터로 키 값을 만들고,
  2. 키 값을 해시 함수를 통해 해시 인덱스를 만듭니다
  3. 인덱스에 해당하는 테이블(버킷)에 데이터와 키를 저장하는 자료구조입니다 Key - Value

IMG_A758EAF54786-1.jpeg

Hash Collision

  1. Different data -> Same key 다른 데이터로 같은 키값을 가지는 것

    IMG_2FC6AD544A15-1.jpeg

  2. Different key -> Same HashIndex 다른 키로 같은 인덱스를 가지는 것

    IMG_50E9B067B52A-1.jpeg

해시 테이블의 시간 복잡도

가장 이상적인 경우 : 중복되지 않은 HashIndex를 가진 HashTable 최악의 경우 : 모든 값이 중복되는 HashIndex를 가진 HashTable

가장 이상적인 경우 O(1)의 시간 복잡도를 가집니다. 하지만 Hash Collision으로 인해, 최악의 경우 O(n)의 시간 복잡도를 가지게 됩니다.

따라서 Hash Collision이 최대한 일어나지 않도록 분배해주어야 합니다.

Hash Collision resolution

  1. Open Addressing
  2. Chaining

해시 충돌 문제 해결을 위한 두 가지 방법 중, Chaining을 통해 구현해보도록 하겠습니다

해시 테이블 알고리즘

간단한 알고리즘을 사용했습니다

💡 Data To Key

→ 모든 문자열의 ASCII값을 더한 값