자료구조 더 알아보기 - 해시 테이블

자료구조 더 알아보기 - 배열 글에 이어서 이번엔 해시 테이블(hash table)에 대해서 알아보자. 해시 테이블은 여러 프로그래밍 언어에 내재되어 있고 자주 사용하는 자료구조이다. JS는 객체(object), Python은 딕셔너리(dictionary), Go는 맵(map) 등..많은 언어에서 사용된다.

사전 - https://unsplash.com/photos/ywqa9IZB-dU

해시 테이블은 키(key)와 값(value)으로 데이터를 매핑하여 자료를 정리한다. 예시로 사전을 떠올려보자. 찾는 단어는 키가 되고, 단어에 해당하는 설명은 값이 될 수 있다.

 

이런게 어떤 장점을 가져올까? 자바스크립트 코드로 배열과 해시 테이블을 비교해보자.

fruits = [
  { kind: '🥑', price: 10 },
  { kind: '🍓', price: 8 },
  { kind: '🥕', price: 12 },
];

과일 중에서 당근의 가격을 알고 싶을 경우 위의 예시는 선형검색(linear search)으로 찾아야 한다.

for (const el of fruits) {
  if (el.kind == '🥕') {
    console.log(el.price);
    break;
  }
}

즉, 하나하나 요소를 검색 해보며 찾아야하기 때문에 시간복잡도는 O(n)이다.

fruits = {
  '🥑': 10,
  '🍓': 8,
  '🥕': 12,
};

위의 예시는 어떨까? 이 경우엔 당근이 키가 되고 가격이 값이 된다.

console.log(fruits['🥕']); // 12

따라서 이런 식으로 키를 통해 값을 쉽게 찾을 수 있다. 즉, 어떤 종류의 과일을 찾더라도 소요되는 단계는 한번뿐이기 때문에 시간복잡도는 O(1)이다. 검색 뿐만 아니라 추가 및 삭제도 마찬가지로 O(1)이다.

fruits['🥝'] = 15;
console.log(fruits);
delete fruits['🥝'];
console.log(fruits);

추가 및 삭제 결과값

결국 해시 테이블은 여러개의 물건을 일렬로 세우는 것이 아닌, 각각의 바구니에 담는 것과 같다.

그림 - 각각의 바구니에 아보카도는 가격이 10이고, 딸기는 8, 당근은 12라는 것을 나타낸다

해시 테이블 활용하기

해시 테이블의 개념을 이용하면, 배열로 작업하는 것보다 더 빠른 검색이 가능하다.

animal = ['🐶', '🐱', '🐭', '🐯', '🐷', '🐵', '🦄', '🦅'];

만약 유니콘(🦄)이 해당 리스트에 있는지 체크하고 싶다면 위의 예시에선 선형 검색을 해야하고 시간은 O(n)으로 오래 걸린다.

animal = {
  '🐶': true,
  '🐱': true,
  '🐭': true,
  '🐯': true,
  '🐷': true,
  '🐵': true,
  '🦄': true,
  '🦅': true,
};

하지만 위처럼 해시 테이블을 사용하면 동물들(🐶, 🐱, 🐭 ...)이 키가 되고, 값은 true가 된다.

console.log(animal['🦄']);
console.log(animal['🦖']);

이렇게 하면 유니콘이 리스트에 있는지 찾는데 단 한번의 단계만 소요된다.

검색 결과 값

해시 테이블은 왜 빠를까?

해시 테이블에는 사실 배열 구조가 존재하며 그 안에 모든 해시 테이블 값들이 담겨져 있다.

너도..?

이제 알다시피 배열은 인덱스 번호를 알아야 요소에 접근 할 수 있다. 그렇다면 해시 테이블은 왜 빠른 것일까? 그 이유는 해시 함수(hash function) 때문이다. 해시 함수는 우리가 저장하고 싶은 키를 숫자로 바꿔준다. 그리고 그 숫자는 인덱스가 된다. 그리고 해당 인덱스에 값이 저장되는 것이다.

키를 주면 해시 함수가 인덱스로 바꿔주고, 해당 인덱스에 값이 저장된다

이런식으로 해시 함수가 알아서 데이터 매핑을 해주기 때문에 빠르게 검색하고, 추가하고 삭제 할 수 있는 것이다.

해시 충돌(Collision)

위의 그림을 다시 봐보자. 위의 그림은 해시 함수의 어떠한 작업을 통해 Key_2가 2번 인덱스에 가게 되었다. 이렇게 나름의 분류 방식으로 키마다 다른 인덱스에 넣어 주었지만, Key의 개수가 배열의 길이보다 더 많다거나 또는 다른 이유로 인해 같은 인덱스에 분류가 되면 어떻게 될까?

 

다시 말해 고정적인 공간(테이블)을 할당한 후 해시함수로 데이터를 담았는데 데이터가 넘치게 된 것이다. 이것을 해시 충돌(collision)이라고 한다. 이렇게 각기 다른 키에 대해 해시함수가 동일한 숫자를 준 경우엔 여러 대처 방법이 있다. 그 중 하나는 같은 공간에 또 다른 배열을 넣는 것이다.

 

예를 들어 2번 인덱스에 각기 다른 키가 존재할 경우 두 개의 쌍을 저장한다.

같은 공간에 두 쌍의 키가 있다

따라서 Key_8의 값을 찾으려면 Key_8을 해시함수에 넣고 인덱스 2로 이동한다. 그리고 그 곳에서 선형검색을 한다.

 

그래서 해시 테이블은 항상 O(1)의 시간을 갖진 않는다. 해시 충돌이 있을 수 있고, 그 경우엔 선형검색을 해야한다. 하지만 이런 예외적인 상황을 제외하면 전반적으로 상수 시간을 갖기 때문에 O(1)이라고 할 수 있다.

 

또한 해시 테이블은 이미 수많은 프로그래밍 언어에 내재되어 있으며, 성능이 좋은 해시 함수가 만들어져있기 때문에 스스로 해시 함수를 만들 경우는 매우 적을 것이다. 하지만 그래도 자주 쓰이는 자료구조인 만큼 작동원리에 대해 알고 그 개념을 명확하게 이해하고 있는 것이 중요하다.

참고

개발자라면 꼭 알아야할 Hash Table 의 모든 것!
JavaScript와 함께 해시테이블을 파헤쳐보자
자바스크립트의 자료구조 2 : 해쉬 테이블(Hash Table)