Q. 해시테이블에 대해서 설명해주세요

해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조로, 빠른 속도로 탐색, 삽입, 삭제를 할 수 있다.

해시함수를 사용하여 특정 해시값을 알아내고 그 해시값을 인덱스로 변환하여 키 값과 데이터를 저장하는 자료구조이다.

서로 다른 키 값을 해시함수로 변환한 값이 동일한 경우를 **충돌(Collision)**이 발생했다고 한다.

해시 테이블에서는 충돌을 아래 방법으로 해결함.

1. Chaining(체이닝) : 추가 메모리 공간 사용(연결 리스트)
2. Open Addressing(개방 주소법) : 비어있는 해시 테이블의 공간 사용(다른 주소 이용)
   • Linear Probing(선형 탐사)
   • Quadratic Probing(제곱 탐사)
   • Double Hashing Probing(이중 해싱)

해시 함수

• Division Method(나눗셈법)
• Multiplication Method(곱셈법)
• Digit Folding
• Univeral Hashing

각각의 Key값은 해시함수에 의해 고유한 index를 가지게 되어 바로 접근할 수 있으므로 평균 O(1)의 시간복잡도로 데이터를 조회할 수 있다. 하지만 데이터의 충돌이 발생한 경우 Chaining에 연결된 리스트들까지 검색을 해야 하므로 O(N)까지 시간복잡도가 증가할 수 있다

해싱(Hashing)

임의의 길이의 값을 **해시함수(Hash Function)**를 사용하여 고정된 크기의 값으로 변환하는 작업