본문 바로가기
CS/자료구조

[자료구조] 해시 테이블

by eess 2024. 7. 11.

해시 테이블이란?

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

사용 사례

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

 

작동 원리

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

해시 함수

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

출처 : 노마드코더 유튜브

 

해시 충돌

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

1. 분리 연결법(seperate chaining)

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

출처 : 노마드코더 유튜브

 

개방 주소법(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)이기 때문에 해시테이블과 비슷하다고 여겨지는 것일 뿐입니다.

 

참고

 

저작자표시 비영리 변경금지

티스토리툴바