[자료구조] HashTable / 해시테이블

1. HashTable이란?

• 1. Key : Value 의 형식으로 이루어진 자료구조다.
• 2. Key의 중복을 허용하지 않는다.**
• 3. 평균적으로 빠른 삽입/삭제/탐색을 제공한다.**

---

2. HashTable의 동작원리

출처: 필자

1.  Key가 주어진다
2.  Hash함수로 주어진 Key를 정수로 변환한다.
3. 변환된 정수를 HashTable의 Row갯수로 나눈 나머지를 구한다.
4. Table에 고루 분포하기위해
5.  나눈 나머지를 Index번호로 활용해 값을 저장한다.

---

3. Collision (Index중복)

Hash함수로 변환하고 나누는 과정 속에서 중복 값이 발생할 수 있다.

즉 Index(자료의 위치)가 중복되는 케이스다.

이를 방지하기 위해 각 값을 LinkList로 처리한다.

---

4. 연산속도

버킷의 값 중복이 없을 경우 값의 조회시 최소 상수시간만큼 걸린다. → O(1)

값의 중복이 있어 연결리스트로 저장되어 있을 경우 최대 N번 만큼의 시간이 걸린다. → O(n)