해시 테이블 (Hash Table)

상수 시간에 데이터 접근이 가능한 자료구조인 해시 테이블(hash table)에 대해서 알아보겠습니다.

해시 테이블

해시 테이블(hash table)은 키(key)와 값(value)으로 이루어진 여러 쌍의 데이터를 저장할 수 있는 자료구조인데요. 키를 알고 있으면 O(1), 즉 상수 시간에 값에 접근할 수 있어서 데이터 검색을 최적화하기 위해서 많이 사용합니다.

해시 테이블은 프로그래밍 언어마다 약간씩 다른 이름으로 불리고 있어서 햇갈릴 수 있는데요.

대표적인 예로 파이썬에서는 사전(dictionary)가 해시 테이블의 역할을 담당하고, 자바스크립트에서는 일반 객체(object) 또는 Map이 같은 역할을 합니다. 자바에서는 HashTable 또는 HashMap을 해시 테이블에 해당하는 내장 자료형이지요.

해시 테이블은 내부적으로 각 키가 값을 가리키는 구조로 되어 있는데요. 그래서 값에 접근하든 추가하든 갱신하든 삭제하든 키를 사용하지 않으면 큰 성능 손해를 볼 수 있습니다. 만약에 해시 테이블을 쓰시는데 키로 값을 접근하고 계시지 않으신다면 적합한 자료구조를 사용하고 계신지 한번 쯤 의심할 필요가 있겠습니다.

데이터 추가

우선 해시 테이블에 어떤 값을 저장할 때는 반드시 키가 있어야 하는데요.

예를 들어, 빈 테이블에 A를 키로 1을 값으로 저장하면 다음과 같은 모습이 됩니다.

A 👉 1

여기에 추가로 B를 키로 2를 값으로 저장한다면 다음과 같은 모습이 되겠지요?

A 👉 1
B 👉 2

마찬가지로 C를 키로 3을 값으로 저장하면 다음과 같은 모습이 될 것입니다.

A 👉 1
B 👉 2
C 👉 3

해시 테이블은 중복된 값을 저장하는 것을 허용합니다. 그래서 다음과 같이 D를 키로 3을 또 저장할 수 있습니다.

A 👉 1
B 👉 2
C 👉 3
D 👉 3

데이터 갱신

반면에 해시 테이블에서는 중복된 키는 허용되지 않습니다. 다시 말해서 하나의 해시 테이블 내에 모든 키는 유일해야 합니다.

대신 키가 가리키고 있는 값은 자유롭게 덮어쓸 수는 있는데요. 그래서 다음과 같이 키 D에 해당하는 값을 4로 갱신하는 것은 전혀 문제되지 않습니다.

A 👉 1
B 👉 2
C 👉 3
D 👉 4 # 3이 었음

데이터 접근

해시 테이블은 키를 사용해서 값에 접근해야 비로서 빛을 발휘하는 자료구조입니다. 값만 알고 있을 때는 해시 테이블에 저장된 값을 하나씩 확인해야하기 때문에 성능이 매우 떨어집니다.

예를 들어, 파이썬에서 다음과 같은 사전이 있다고 가정해보겠습니다.

dic = {
  "A": 1,
  "B": 2,
  "C": 3,
  "D": 4,
}

만약에 C라는 키가 해시 테이블에 있는지 알아내야 하거나 해당 키가 가리키고 있는 값을 얻고 싶다면 O(1) 시간에 수행할 수 있습니다.

"C" in dic # true
dic["C"] # 3

하지만 키가 없이 값 3를 찾아야 한다면 다음과 같이 해시 테이블에 저장된 모든 값을 일일이 확인해야하며 이 것은 O(n)의 시간이 소모되는 비효율적인 작업입니다.

for key in dic:
  if dic[key] == "3":
    print("3이 존재합니다.")

해시 테이블 (Hash Table)