해싱 (Hashing)

• 해싱(Hashing)은 키를 해시 함수에 넣어 배열의 버킷 위치를 정하는 기법이다. 해시 테이블(Hash Table)은 그 버킷에 키와 값을 저장하는 자료구조다. 찾으려는 키를 다시 같은 함수에 넣으면 검색을 시작할 위치를 얻는다.
• 해시 주소는 검색의 시작점이지 항목의 유일한 주소가 아니다. 서로 다른 키가 같은 버킷으로 갈 수 있어 충돌 처리가 반드시 필요하다.

추상자료형

• 새로운 항목을 삽입(add)

• 탐색 키에 관련된 항목을 삭제(delete)

• 탐색 키에 관련된 값을 탐색(search)

• 객체 : 일련의 (key, value) 쌍의 집합

• 연산

  • add(key, value) : (key, value)를 사전에 추가
  • delete(key) : key에 해당되는 (key, value)를 찾아서 삭제하고 관련된 value는 반환한다. 탐색에 실패하면 null을 반환
  • search(key) : key에 해당되는 value를 찾아서 반환. 만약 탐색이 실패하면 null을 반환

해싱의 구조

해싱은 자료를 저장하는데 배열을 사용한다. 원하는 항목이 저장된 위치를 알고 있다면 빠르게 삽입하거나 꺼낼 수 있다.

• 해시함수(Hash Function) : 탐색 키를 입력받아 해시 주소(Hash Address) 를 생성하고 해시 주소가 배열로 구현된 해시 테이블(Hash Table) 의 인덱스가 된다.

• 해시 테이블 K를 받아서 해시 함수 h()로 연산한 결과인 해시 주소 h(k)를 인덱스로 사용하여 해시 테이블에 있는 항목에 접근한다.
• 해시테이블 ht는 M개의 버켓(bucket) 으로 이루어지는 테이블로써 ht[0], ht[1]… ht[M-1]의 원소를 가진다.

• 버켓은 s개의 슬롯(slot) 을 가질 수 있으며, 하나의 슬롯에는 하나의 항목이 저장된다. 하나의 버켓에 여러 개의 슬롯을 두는 이유는 서로 다른 두 개의 키가 해시 함수에 의해 동일한 주소로 변환될 수 있으므로 여러 개의 항목을 동일한 버켓에 저장하기 위해서이지만, 대부분의 경우 하나의 버켓에 하나의 슬롯을 가진다.

• 해시테이블에 버킷이 M개라면 해시 함수는 모든 키 k에 대해 $0 \le h(k) \le M-1$ 범위의 주소를 내야 한다. 키의 가능한 수는 보통 버킷보다 훨씬 많으므로 충돌을 완전히 피할 수 없다.

• 서로다른 두 개의 탐색 키 K1와 K2에 대하여 h(k1) = h(k2)인 경우를 충돌(Collision) 이라고 한며, 이러한 키 k1, k2를 동의어(synonym) 라 한다.

• 만약 충돌이 발생하면 같은 버켓에 있는 다른 슬롯에 항목을 저장하게 된다.

• 충돌이 자주 일어나면 버켓 내부에서 순차탐색 시간이 길어져 탐색 성능이 저하될 수 있으므로 해시 함수를 수정하거나 해시 테이블의 크기를 적절하게 조절해야한다.

• 충돌이 버켓에 할당된 슬롯 수보다 많이 발생하게 되면 버켓에 더 이상 항목을 저장할 수 없게 되는 오버플로(overflow)가 발생한다. 만약 버켓당 슬롯의 수가 하나(s==1)이면 충돌이 곧 오버플로를 의미한다.

• 오버플로가 발생하면 더 이상 항목을 저장할 수 없으므로 오버플로를 해결하기 위한 방법이 반드시 필요.

작은 테이블에 직접 넣어 보기

버킷이 7개이고 정수 키에 h(k)=k mod 7을 쓴다고 하자. 키 10은 3번 버킷, 17도 3번 버킷, 24도 3번 버킷으로 간다. get(17)은 3번 버킷에 있는 항목들의 키를 비교해야만 값을 찾을 수 있다. 주소가 같다는 사실만으로 10의 값을 돌려주면 잘못된 검색이다.

flowchart LR
  A[키 10] --> H[나머지 7]
  B[키 17] --> H
  C[키 24] --> H
  H --> D[버킷 3: 10 → 17 → 24]

그림은 체이닝을 가정한다. 한 버킷에서 충돌한 항목을 연결 리스트나 다른 내부 구조에 저장하고, 조회할 때 해당 버킷 안의 키를 비교한다. 삭제는 해당 키의 항목만 제거한다. 반대로 개방 주소법은 다른 빈 버킷을 순서대로 찾아 넣는다. 이 방식에서 삭제를 단순히 빈 칸으로 만들면 이후 항목을 찾던 탐색이 중간에서 끊어질 수 있으므로 삭제 표식 또는 재배치가 필요하다.

import java.util.HashMap;
import java.util.Map;

Map<String, Integer> counts = new HashMap<>();
counts.put("apple", 2);
counts.put("banana", 1);
counts.put("apple", counts.get("apple") + 1);

System.out.println(counts.get("apple")); // 3
System.out.println(counts.getOrDefault("pear", 0)); // 0

put은 같은 키가 이미 있으면 그 키의 값을 교체한다. 따라서 위 코드는 apple 항목을 두 개 만드는 것이 아니라 값을 2에서 3으로 갱신한다. get("pear")만 호출하면 키가 없는 경우 null이므로, 정수 0이 필요한 로직에는 getOrDefault처럼 기본값을 분명히 정한다.

왜 평균적으로 빠르고 최악에는 느릴까

키들이 여러 버킷에 고르게 퍼져 있다면 한 버킷에서 비교할 항목 수가 적어 삽입·조회·삭제가 평균적으로 O(1)에 가깝다. 모든 키가 같은 버킷으로 몰리면 한 번의 조회에 많은 키를 비교해야 하므로 최악의 시간은 구현 방식에 따라 O(n)까지 늘 수 있다. 전체 n개 항목과 버킷 M개에 대해 적재율은 α=n/M이다. 적재율이 커지면 충돌 가능성이 높아져 테이블을 키우고 다시 배치하는 재해싱이 필요하다. 한 번의 재해싱은 O(n)이지만 매 삽입마다 발생하지 않으므로 보통 평균 비용으로 설명한다.

Java HashMap은 기본 적재율 0.75를 사용하며 항목 수가 버킷 수와 적재율의 곱을 넘으면 내부 구조를 다시 만든다. 다만 이 값이나 내부 충돌 처리 방식은 자신이 직접 구현하는 해시 테이블과 구분해야 한다. HashMap을 순회한다고 키 순서가 보장되지 않는다. 저장된 순서가 필요하면 LinkedHashMap, 정렬 순서가 필요하면 TreeMap이 요구에 맞는지 검토한다.

사용자 정의 객체를 키로 쓸 때는 같은 키로 판단되는 객체의 equals와 hashCode가 일관되어야 한다. 저장한 뒤 키의 비교 대상 필드를 변경하면 이전 버킷에서 찾을 수 없게 될 수 있다. 그래서 키는 가능하면 불변 값으로 만든다. 해시 테이블은 키로 정확한 값 하나를 찾는 용도에 강하지만, 키의 대소 순서로 범위를 찾거나 최소값을 반복해서 꺼내는 용도에는 적합하지 않다.

참고: Oracle HashMap API. 구현별 보장과 평균적인 기대 성능을 구분해 읽는 것이 중요하다.