해시 테이블

해시 테이블은 해시 함수를 사용하여 키를 배열 위치에 매핑함으로써 딕셔너리를 구현하며, 충돌이 잘 관리될 때 예상되는 상수 시간 삽입, 삭제 및 조회를 지원합니다.

Definition

해시 테이블은 키-값 쌍을 배열에 저장하는 데이터 구조로, 해시 함수를 사용하여 각 키로부터 배열의 인덱스를 계산하고, 동일한 인덱스로 해시되는 서로 다른 키를 처리하기 위한 충돌 해결 방식을 사용합니다.

Scope

이 주제는 해싱 기반 딕셔너리를 다룹니다: 해시 함수와 그 바람직한 속성, 충돌 해결 전략(분리 연결법 및 개방 주소법), 적재율 및 크기 조정, 증명 가능한 보장을 제공하는 유니버설 및 완전 해싱 프레임워크, 그리고 블룸 필터와 같은 관련 확률적 구조를 포함합니다. 검색 트리에서 다루는 정렬된 딕셔너리 구조는 제외합니다.

Core questions

• 좋은 해시 함수란 무엇이며, 키를 균일하게 분산시키기 위해 어떻게 선택됩니까?
• 연결법 또는 개방 주소법으로 충돌은 어떻게 해결되며, 비용에 어떤 영향을 미칩니까?
• 적재율은 예상 작업 시간을 어떻게 제어하고 크기 조정을 유발합니까?
• 유니버설 해싱과 완전 해싱은 어떻게 증명 가능한 성능 보장을 제공합니까?
• 블룸 필터와 같은 공간 효율적인 확률적 구조가 정확한 테이블보다 선호되는 경우는 언제입니까?

Key concepts

• 해시 함수
• 분리 연결법
• 개방 주소법
• 적재율
• 재해싱 및 크기 조정
• 유니버설 해싱
• 완전 해싱
• 블룸 필터

Key theories

유니버설 해싱

신중하게 설계된 (유니버설) 패밀리에서 해시 함수를 무작위로 선택함으로써, 고정된 키 집합에 대해 낮은 예상 충돌 수를 보장할 수 있으며, 최악의 경우 적대적 입력이 발생할 가능성을 낮춥니다.

충돌 해결 및 적재율

분리 연결법은 충돌하는 키를 슬롯당 리스트에 저장하는 반면, 개방 주소법은 대체 슬롯을 탐색합니다. 예상 작업 시간은 적재율(슬롯당 항목 수)에 의해 결정되며, 테이블은 적재율을 제한된 상태로 유지하기 위해 크기가 조정됩니다.

Clinical relevance

해시 테이블은 컴퓨팅에서 가장 많이 사용되는 데이터 구조 중 하나입니다. 표준 라이브러리에서 딕셔너리와 집합을 구현하고, 데이터베이스 인덱싱 및 인메모리 캐시를 구동하며, 컴파일러의 심볼 테이블을 지원하고, 중복 제거 및 멤버십 테스트의 기반이 됩니다. 블룸 필터는 정확한 저장이 불가능한 데이터베이스 및 네트워킹에서 멤버십 쿼리의 규모를 확장합니다.

History

해싱은 1950년대 IBM의 한스 피터 룬(Hans Peter Luhn)의 연구에서 시작되었습니다. 버튼 블룸(Burton Bloom)은 1970년에 공간 효율적인 블룸 필터를 소개했습니다. 카터(Carter)와 웨그먼(Wegman)은 1970년대 후반과 1980년대 초반에 유니버설 해싱과 이후 강력한 유니버설 해싱을 공식화하여 해싱에 엄격한 이론적 기반을 제공했습니다.

Key figures

• Hans Peter Luhn
• J. Lawrence Carter
• Mark Wegman
• Burton H. Bloom

Seminal works

• bloom1970
• carter1981
• cormen2009

Frequently asked questions

해시 테이블 연산이 보장된 O(1)이 아닌 예상 O(1)로 설명되는 이유는 무엇입니까?

많은 키가 충돌하면 연산이 O(n)으로 저하될 수 있습니다. 좋은 해시 함수와 제한된 적재율 하에서는 상수 시간이 예상됩니다. 유니버설 해싱은 나쁜 경우의 발생 가능성을 낮추지만, 최악의 경우 보장을 위해서는 완전 해싱 또는 다른 기술이 필요합니다.

블룸 필터는 무엇이며 해시 테이블과 어떻게 다릅니까?

블룸 필터는 비트 배열에 여러 해시 함수를 사용하여 집합 멤버십을 테스트하는 압축된 확률적 구조입니다. 이는 오탐(false positive)을 발생시킬 수 있지만 위음(false negative)은 발생시키지 않으며, 키를 저장하지 않아 해시 테이블에 비해 정확성을 희생하는 대신 큰 공간 절약을 제공합니다.