[자료구조] 해시 테이블

해시 테이블이란?

• 키(key)와 값(value)의 쌍으로 데이터를 저장하는 자료구조.
• 해시 테이블에서 삽입/삭제/탐색 시 평균적인 시간복잡도는 O(1)로, 어떤 값을 찾더라도 한 단계만 소요된다.

사용 사례

• 검색이나 저장이 빈번할 때 사용하면 좋은데, 특히 캐시를 구현할 때 해시 테이블을 사용할 수 있다.
• 캐시는 이전에 계산된 결과를 임시로 저장하는 장소로, 캐시의 접근 시간에 비해 원래 데이터를 접근하는 시간이 오래 걸리는 경우나 값을 다시 계산하는 시간을 절약하고 싶은 경우에 사용된다.

작동 원리

• 해시 테이블 내부에서는 index와 value로 이루어진 배열 구조를 사용한다.
• 키(key)를 해시 함수를 사용하여 배열의 인덱스로 변환한 후 해당 인덱스에 값(value)을 저장한다.

 

해시 함수

• 해시 테이블에서의 해시 함수는 임의의 데이터를 정수로 변환하는 함수.
• 예를 들어, 해시 함수의 input이 'abc'라면 output이 '1234'가 되는 것이다. 이때 변환된 값 '1234'가 해시이다.

출처 : 노마드코더 유튜브

 

해시 충돌과 해결 방법

• 서로 다른 키 값이 동일한 인덱스로 매핑될 경우 해시 충돌(hash collision)이 발생하여 해시 테이블의 성능을 떨어트린다.
• 이를 해결하는 방법으로 분리 연결법(seperate chaining), 개방 주소법(open addressing)이 있다.

1. 분리 연결법(seperate chaining)

• 해시 테이블 각각의 공간을 버킷(bucket)이라고 한다.
• 각 버킷에 대응하는 연결 리스트를 생성하고, 버킷이 연결 리스트의 가장 앞 노드를 바라보게끔 하여 충돌을 방지하는 방법이다.
• 해시 충돌이 발생했을 때 그저 같은 버킷 연결 리스트의 마지막 노드로 해당 값을 추가해주기만 하면 된다.

출처 : 노마드코더 유튜브

 

2. 개방 주소법(open addressing)

• 한 버킷에는 하나의 값만 저장하고, 충돌이 발생하면 다른 빈 버킷에 저장하여 충돌을 방지하는 방법이다.
• 저장할 다음 버킷을 찾는 방법으로 선형 탐사법(linear probing), 제곱 탐사법(quadratic probing), 이중 해싱(double hashing)이 있다.
• 선형 탐사법은 말그대로 순차적으로 빈 버킷을 찾는 방법이다.

 

+) JS의 Object, Map, Set은 해시 테이블일까?

• 많은 레퍼런스들을 보면 JS의 Object, Map, Set이 해시 테이블이라고 이야기하는데 엄밀히 이야기하자면 아니다.

JS Object 는 해시 테이블이 아니다

• V8 엔진을 포함한 대부분의 자바스크립트 엔진은 높은 성능을 위해 해시 테이블과 유사하지만 해시 테이블보다 나은 방법으로 Object를 구현한다.
• Object도 키-값 쌍의 데이터 집합이라는 점은 같지만, 자바스크립트 엔진이 Object를 해시 테이블의 원리로 실행하지 않기 때문에 해시 테이블이 아니다.

JS Map, Set 은 해시 테이블이 아니다

The specification requires maps to be implemented "that, on average, provide access times that are sublinear on the number of elements in the collection". Therefore, it could be represented internally as a hash table (with O(1) lookup), a search tree (with O(log(N)) lookup), or any other data structure, as long as the complexity is better than O(N).

The specification requires sets to be implemented "that, on average, provide access times that are sublinear on the number of elements in the collection". Therefore, it could be represented internally as a hash table (with O(1) lookup), a search tree (with O(log(N)) lookup), or any other data structure, as long as the complexity is better than O(N).

• Map, Set의 MDN 문서를 보면 ECMAScript 명세에서는 Map과 Set이 복잡도가 선형시간보다 빠른 자료구조로 구현될 수 있다고 나와있다.
• 즉, JS 엔진이 Map, Set을 어떻게 구현했는지에 달려있으며 반드시 해시 테이블로 동작한다고 말할 수는 없다.
• V8의 Map, Set의 데이터 접근에 대한 시간 복잡도가 O(1)이기 때문에 해시테이블과 비슷하다고 여겨지는 것일 뿐이다.

 

참고

• 노마드 코더 - 개발자라면 꼭 알아야할 Hash Table 의 모든 것! 
• 쉬운 코드 - 맵(map)과 해시 테이블(hash table) 핵심만 모아보기! 맵과 해시 테이블(a.k.a 해시 맵)을 20분간 아주아주아주 알차게 설명합니다!!
• 해시 충돌
• [DS] 해시테이블 (Hash Table)
• 자료구조 | 해시 테이블 hash table
• Data Structures: Hash Tables
• Map
• Set