해시 테이블

개요

• 한정된 배열 공간에 key 를 index 로 변환하여 값들을 넣게됩니다.
• 사물함과 비슷합니다.

정의

• 키와 값을 받아 키를 해싱(Hashing) 하여 나온 index 에 값을 저장하는 선형 자료구조입니다.
• 추가는 O(1), 키를 알고 있다면 탐색과 삭제도 O(1) 으로 수행합니다.

용어

• Bucket : Table 에 해당하는 인덱스, 키와 값이 둘 다 있어야합니다.
• Hash : 고기와 감자를 잘게 다져 요리한 것, 입력받은 키를 잘게 잘라 숫자로 만듭니다.
• 해시 함수 : 입력받은 값을 특정 범위 내 숫자로 변경하는 함수 ex) "gender" -> 14535135, "name" -> 234215345, "age" -> 2343590890

구현 방법

• 특정한 구현방법이 정해져 있지 않고 맘대로 구현합니다.
• 예를들어, 문자열의 각 문자의 아스키코드를 더한 값을 해시를 정의.

문제점 (해시 충돌, Hash Collision)

• 해시 함수의 결과가 동일하여 중복되는 경우.

해시 충돌 해결

1. 선형 탐사법
   • 충돌이 발생하면 옆으로 한 칸 이동합니다.
   • 특정 영역의 데이터가 몰려서, 탐색에 선형시간이 소요될 수도 있습니다.

2. 제곱 탐사법
   • 충돌이 발생하면 충돌이 발생한 횟수의 제곱만큼 옆으로 이동합니다.

3. 이중 해싱
   • 충돌이 발생하면 다른 해시 함수르 이용합니다. (해시 함수가 2개 이상)

4. 분리 연결법
   • 버킷의 값을 ㄹ연결리스트로 사용하여 충돌이 발생하면 리스트에 값을 추가합니다.
   • 최악의 경우, 하나의 버킷이 무한정 늘어난다는 단점이 있습니다.

사용예시 : 학생정보 관리 소프트웨어

1. 연결 리스트
   • 추가, 제거는 빠르지만 학생 정보 탐색에 O(n) 시간복잡도 소요됩니다.

2. 배열
   • 인덱스를 모를 경우 탐색에 O(n)이 걸립니다.

3. 해시 테이블
   • 이름을 key 로 하여 탐색, 추가 삭제 모두에 O(1) 이 걸립니다.
   • 최악의 경우 탐색에 선형시간이 걸리지만 연결 리스트나 배열보다 안정적입니다.
   • 따라서 빠르게 값을 찾아야하는 경우 해시 테이블을 사용하는 것이 좋습니다.

JS 에서 사용법

1. 배열
   • 자바스크립트의 배열은 객체타입이라 해시타입처럼 사용가능합니다. (추천 X)
2. 객체
   • 가장 간단한 사용방법입니다.
3. Map 객체
   • 키값으로 다양한 자료형 사용가능합니다.
   • 편한 메서드, 순회에 장점이 있습니다.
4. Set 객체
   • 키와 값이 동일하게 들어갑니다.

깃허브 : https://github.com/HyeonWooGa/algorhithm-code-snippet