해시 테이블

해시 테이블 (Hash Tables)

⚠️ 출처 URL이 /docs/hash_tables에서 /docs/hash-tables로 이전되어, 실재 페이지 기준으로 번역했어요.

OCaml 표준 라이브러리의 Hashtbl 모듈은 표준 라이브러리의 Map 모듈과 비슷한 연관 배열(associative array)을 구현해요.

이 두 모듈은 구조와 목적이 닮았지만, 둘 사이에서 선택할 때 저울질해 볼 차이점이 여럿 있어요.

해시 테이블이 맵에 비해 갖는 이점 중 하나는 시간 복잡도예요. 로그 시간 복잡도(O(log n))를 갖는 맵과 달리, 해시 테이블은 거의 즉각적인 상수 시간 복잡도(O(1))로 정보를 가져올 수 있어요.

해시 테이블 자료구조는 해시 함수를 사용해서 효율적인 읽기와 쓰기를 이루는데, 이 함수는 키/값 쌍의 키를 알고리즘적으로 고유한 "지문(fingerprint)"이라고 하는 해시로 변환해요. OCaml에는 Hashtbl 모듈 안에 각 키마다 쓸 수 있는 내장 해시 함수가 있어요. Hashtbl 모듈은 효율적이고 가변적인(mutable) 조회 테이블을 구현하죠.

출처: OCaml 공식 문서

본문

다형성 해시 테이블 만들기 (Creating a Polymorphic Hash Table)

해시 테이블을 만들려면 이렇게 쓸 수 있어요.

# let my_hash = Hashtbl.create 123456;;
val my_hash : ('_weak1, '_weak2) Hashtbl.t = <abstr>

여기서 123456은 해시 테이블의 초기 크기(요소 개수 기준)예요. 이 초기 숫자는 해시 테이블에 넣을 데이터 양에 대한 여러분의 최선의 추측이에요. 크기를 과소평가해도 해시 테이블은 커질 수 있으니 너무 걱정하지 마세요. my_hash의 타입은 다음과 같아요.

# my_hash;;
- : ('_weak1, '_weak2) Hashtbl.t = <abstr>

'_weak1과 '_weak2는 각각 키 타입과 값 타입에 해당해요. 그 자리에 구체적인 타입(예: int나 float * string)이 채워져 있지 않은 이유는, 키와 값의 타입이 아직 결정되지 않았기 때문이에요. 밑줄은 키와 데이터 타입이, 일단 선택되면 고정된다는 뜻이에요. 다시 말해, 주어진 해시 테이블을 어느 때는 int 키에 쓰고 나중에 같은 해시 테이블에 string을 키로 쓰는 건 불가능해요.

해시 테이블에 데이터 추가하기 (Adding Data to a Hash Table)

my_hash에 데이터를 추가해 볼게요. 크로스워드 풀이 프로그램을 만들고 있고, 특정 글자로 시작하는 단어를 모두 찾고 싶다고 해 보죠. 먼저 my_hash에 데이터를 넣어야 해요.

해시 테이블은 제자리 업데이트(in-place update)로 수정된다는 점을 주의하세요. 그래서 맵과 달리, 테이블을 바꿀 때마다 해시 테이블이 새로 만들어지지 않아요. 그러니 let my_hash = Hashtbl.add my_hash ... 같은 코드는 말이 안 돼요. 대신 명령형 스타일로 이렇게 써요.

# Hashtbl.add my_hash "h" "hello";
  Hashtbl.add my_hash "h" "hi";
  Hashtbl.add my_hash "h" "hug";
  Hashtbl.add my_hash "h" "hard";
  Hashtbl.add my_hash "w" "wimp";
  Hashtbl.add my_hash "w" "world";
  Hashtbl.add my_hash "w" "wine";;
- : unit = ()

반환 타입이 unit인 것에서 Hashtbl.add가 부수 효과(side effect)를 일으킨다는 걸 알 수 있어요.

이제 my_hash에 데이터를 넣었으니 그 타입을 살펴볼게요.

# my_hash;;
- : (string, string) Hashtbl.t = <abstr>

타입이 다형성인 (_weak1, _weak2)였다가, 이제는 구체적인 표현 (string, string)을 갖게 됐어요.

해시 테이블에서 데이터 찾기 (Finding Data in Hash Tables)

my_hash에서 "h"를 가진 요소 하나를 찾으려면 이렇게 써요.

# Hashtbl.find my_hash "h";;
- : string = "hard"

예상한 대로, 해시 테이블 my_hash를 키 h로 조회하면 단일 값 "hard"가 돌아와요. 이 값이 "h" 키와 함께 마지막으로 업데이트된 요소이기 때문이죠.

하지만 키 "h"와 연관된 이전 값들은 대체되지 않았어요. 우리가 원하는 것은 "h"로 시작하는 모든 요소일 수도 있어요. 그러려면 그것들을 전부 찾고 싶을 거예요. find_all보다 이 상황에 잘 어울리는 이름이 있을까요?

# Hashtbl.find_all my_hash "h";;
- : string list = ["hard"; "hug"; "hi"; "hello"]

이 결과는 ["hard"; "hug"; "hi"; "hello"]를 돌려줘요. 해시된 키가 충돌할 때 그 키와 연관된 값들의 리스트로 묶인다는 것을 보여줘요.

해시 테이블에서 데이터 제거하기 (Removing Data from Hash Tables)

키를 제거하면 그 키와 연관된 이전 값이 다시 기본값이 돼요.

# Hashtbl.remove my_hash "h";;
- : unit = ()
# Hashtbl.find my_hash "h";;
- : string = "hug"

이 동작은 위 예시처럼 유용할 때가 있고, 또 예를 들어 키들이 같은 이름의 지역 변수에 의해 일시적으로 가려질 수 있는(masked) 변수를 나타날 때도 유용해요.

해시 테이블에서 데이터 교체하기 (Replacing Data in Hash Tables)

다른 맥락에서는 새 값이 이전 값을 대체하는 걸 선호하기도 해요. 그 경우엔 Hashtbl.replace를 써요.

# Hashtbl.replace my_hash "t" "try";
  Hashtbl.replace my_hash "t" "test";
  Hashtbl.find_all my_hash "t";;
- : string list = ["test"]

# Hashtbl.remove my_hash "t";
  Hashtbl.find my_hash "t";;
Exception: Not_found.

my_hash에 어떤 글자에 대한 항목이 있는지 알아보려면 이렇게 해요.

# Hashtbl.mem my_hash "h";;
- : bool = true

더 알아보기