키로부터 해시 함수로 저장할 위치를 계산하여, 평균 O(1)로 탐색·삽입·삭제를 할 수 있는 자료 구조. 서로 다른 키가 같은 위치가 되는 충돌을 체이닝이나 개방 주소법으로 처리한다. 해시 표라고도 한다.
일본어 명칭: ハッシュテーブル
해시 테이블(Hash Table)은(는) 자료 구조와 알고리즘, 확률·통계와 대기행렬, 메모리 계층 구조 등 4개 분야의 연습 문제 7개에 나와요.
분야: 자료 구조와 알고리즘
해시 테이블은 키를 해시 함수로 정수로 바꾸고, 표의 크기로 나눈 나머지 등을 저장할 위치로 삼습니다. 키의 종류는 표의 크기보다 훨씬 많으므로, 서로 다른 키가 같은 위치가 되는 충돌은 피할 수 없습니다. 체이닝은 같은 위치의 원소를 연결 리스트 등으로 잇습니다. 개방 주소법은 표 안의 다른 빈 위치를 찾으며, 이웃을 차례로 조사하는 선형 탐사나 다른 해시 함수로 간격을 정하는 이중 해싱 등이 있습니다.
저장한 원소의 수를 표의 크기로 나눈 값을 적재율이라고 합니다. 체이닝에서는 리스트의 평균 길이가 적재율에 비례하고, 개방 주소법에서는 적재율이 1에 가까워지면 빈자리를 찾는 횟수가 급격히 늘어납니다. 그래서 적재율이 정해 둔 값을 넘으면 표를 2배 정도로 키워 모든 원소를 다시 넣습니다(재해싱). 1회의 재해싱에는 O(n)이 걸리지만, 키우는 간격이 배로 넓어지므로 추가 1회당 수고는 분할 상환 O(1)에 들어갑니다.
평균 O(1)은 해시 함수가 키를 표 전체에 고르게 흩뜨린다는 것이 전제입니다. 치우친 해시 함수나 의도적으로 충돌을 일으키는 입력(해시 플러딩 공격)에서는 최악 O(n)까지 느려지므로, 웹 서버 등에서는 난수 시드를 섞은 해시 함수를 사용합니다. 또한 해시 테이블은 원소를 순서대로 늘어놓아 갖지 않으므로, 범위 검색이나 순서대로의 열거에는 이진 탐색 트리나 B 트리가 더 적합합니다. 실제 속도는 캐시가 듣는 정도에도 좌우되어, 선형 탐사처럼 이웃을 조사하는 방식은 포인터를 따라가는 체이닝보다 빠른 경우가 많습니다.
정답: B. 0.45
10개의 키에서 2개를 고르는 쌍은 10C2 = 45쌍이 있고, 각각의 쌍이 같은 버킷에 들어갈 확률은 1/100입니다. 기댓값의 선형성(합의 기댓값은 기댓값의 합)에 의해, 같은 버킷에 들어가는 쌍의 수의 기댓값은 45 × 1/100 = 0.45입니다. 기댓값의 선형성은 쌍끼리 독립이 아니어도 성립하므로, 쌍마다의 확률을 더하기만 하면 구할 수 있습니다.
정답: B. 서로 다른 키에서 같은 해시값(저장할 위치)이 구해지는 것
해시 테이블은 키로부터 해시 함수로 저장할 위치를 계산하여, 평균 O(1)로 탐색·삽입·삭제를 할 수 있는 자료 구조입니다. 키의 종류는 표의 크기보다 훨씬 많으므로, 서로 다른 키가 같은 위치가 되는 것(충돌)은 피할 수 없습니다. 그래서 같은 위치의 원소를 리스트로 잇는 체이닝이나, 비어 있는 다른 위치를 찾는 개방 주소법 등으로 충돌을 처리합니다. 같은 키에서는 반드시 같은 해시값이 구해지지 않으면 탐색을 할 수 없으며, 해시값에서 원래 키를 알 수 있는지는 암호에 사용할 때의 성질로, 충돌과는 별개의 이야기입니다.
해시 함수는 키로부터 정해진 범위의 값을 계산하는 함수이고, 해시 테이블은 그것을 저장할 위치의 계산에 사용하는 자료 구조입니다. 해시 테이블용 해시 함수는 속도와 고르게 흩어지는 성질을 중시하며, 암호용 해시 함수 같은 일방향성까지는 요구하지 않는 것이 보통입니다.
프로그래밍 언어의 딕셔너리(연관 배열)나 집합(set), 컴파일러의 심볼 테이블, 데이터베이스의 해시 조인이나 해시 인덱스, 캐시 관리 등 키로 값을 빠르게 찾는 장면의 대부분에서 쓰입니다.
해시 테이블은 키로부터 해시 함수로 저장할 위치를 계산하여, 평균 O(1)로 탐색·삽입·삭제를 할 수 있는 자료 구조입니다.
해시 테이블에서 충돌(collision)에 대한 설명으로 올바른 것은?무작위 키로 해시 테이블을 참조하는 것도 주소에 규칙성이 없으므로 효과가 작습니다.
하드웨어 프리페치가 특히 효과를 발휘하기 쉬운 접근은?해시 테이블의 버킷마다 락을 나누는 것과 같은 세밀한 입도로 하면 다른 부분은 동시에 조작할 수 있습니다.
큰 자료 구조 전체를 하나의 락으로 보호하는 '굵은 입도의 락'과 부분별로 다른 락으로 보호하는 '세밀한 …연결 리스트(Linked List) 해시 함수(Hash Function) 프리페치(Prefetch) 기댓값(Expected Value) 캐시 라인(Cache Line) 포인터(Pointer) 시간 복잡도(Time Complexity) 배열(Array) 깊이 우선 탐색(Depth-First Search) 너비 우선 탐색(Breadth-First Search)