해시 테이블

delete_worst=O(n) 해시 테이블로 구현된 작은 전화번호부 컴퓨터 과학에서 **해시 테이블**(hash table)은 **딕셔너리**(dictionary) 또는 단순히 **맵**(map)이라고도 불리는 연관 배열을 구현하는 자료 구조이다. 연관 배열은 유일 키를 값에 매핑하는 추상 자료형이다.chapter-url=https://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/HashTables.pdf 해시 테이블은 해시 함수를 사용하여 버킷 또는 슬롯의 배열로 인덱스(해시 코드라고도 함)를 계산하고, 여기서 원하는 값을 찾을 수 있다. 조회 중에 키는 해시되고 결과 해시는 해당 값이 저장된 위치를 나타낸다. 해시 테이블로 구현된 맵을 **해시 맵**이라고 한다. 대부분의 해시 테이블 설계는 불완벽 해시 함수를 사용한다. 따라서 해시 함수가 하나 이상의 키에 대해 동일한 인덱스를 생성하는 해시 충돌은 일반적으로 어떤 방식으로든 처리되어야 한다. 해시 충돌을 처리하는 일반적인 전략에는 연결 리스트를 사용하여 동일한 슬롯에 여러 요소를 저장하는 체이닝과 프로빙 시퀀스에 따라 다음 사용 가능한 슬롯을 검색하는 개방 주소 지정이 있다.isbn=978-0-201-89685-5 잘 구성된 해시 테이블에서 각 조회의 평균 시간 복잡도는 테이블에 저장된 요소 수와 독립적이다. 많은 해시 테이블 설계는 키-값 쌍의 임의 삽입 및 삭제를 허용하며, 작업당 분할 상환 상수에 평균 비용을 가진다.url-status=livepages=513–558title-link=Introduction to Algorithms 해싱은 공간-시간 트레이드오프의 예시이다. 메모리가 무한하다면, 전체 키를 직접 인덱스로 사용하여 단일 메모리 접근으로 값을 찾을 수 있다. 반대로, 무한한 시간을 사용할 수 있다면, 값은 키에 관계없이 저장될 수 있으며, 요소를 검색하기 위해 이진 검색 또는 선형 검색이 사용될 수 있다. 많은 상황에서 해시 테이블은 탐색 트리 또는 다른 테이블 조회 구조보다 평균적으로 더 효율적인 것으로 밝혀졌다. 해시 테이블은 빠른 평균 사례 성능 때문에 데이터베이스 인덱싱, 캐싱 및 연관 배열 구현과 같은 작업에 현대 소프트웨어 시스템에서 널리 사용된다.publisher=McGraw-Hill 이러한 이유로, 특히 연관 배열, 데이터베이스 인덱싱, 캐시, 집합과 같은 다양한 종류의 소프트웨어에서 널리 사용된다. 많은 프로그래밍 언어는 프로그래머로부터 해싱의 복잡성을 추상화하는 Python의 딕셔너리, Java의 HashMap, C++의 unordered_map과 같은 내장 해시 테이블 구조를 제공한다.publisher=Wiley
# 역사
해싱의 개념은 여러 곳에서 독립적으로 발생했다. 1953년 1월, 한스 페터 룬은 체이닝을 사용하는 내부 IBM 메모랜덤을 작성했다. 개방 주소 지정의 첫 번째 예시는 룬의 메모랜덤을 기반으로 A. D. 린에 의해 제안되었다.p=547 거의 같은 시기에 진 암달, 일레인 M. 맥그로, 너새니얼 로체스터, 아서 새뮤얼은 IBM 리서치에서 IBM 701 어셈블러에 해싱을 구현했다. 선형 프로빙을 사용하는 개방 주소 지정은 암달에게 공로가 있지만, 안드레이 예르쇼프도 독립적으로 같은 아이디어를 가지고 있었다.isbn=978-0-470-34473-6pp=124–125 "개방 주소 지정"이라는 용어는 W. 웨슬리 피터슨이 대용량 파일 검색 문제에 대해 논의한 기사에서 만들어졌다.editor-first3=Sartajp=15 체이닝을 이용한 해싱에 대한 첫 번째 출판물은 프라임 모듈로 나머지를 해시 함수로 사용하는 아이디어를 논의한 아놀드 듀미에게 공로가 있다. "해싱"이라는 단어는 로버트 모리스의 기사에서 처음 출판되었다. 선형 프로빙의 이론적 분석은 원래 콘하임과 바이스가 제출했다.
# 개요
연관 배열은 (키, 값) 쌍의 집합을 저장하고 삽입, 삭제 및 조회(검색)를 허용하며, 유일 키의 제약이 있다. 연관 배열의 해시 테이블 구현에서 길이 m인 배열 A는 n개의 요소로 부분적으로 채워지며, 여기서 m \ge n이다. 키 **x**는 해시 함수 h를 사용하여 해시되어 해시 테이블 내의 인덱스 위치 A[h(x)]를 계산하며, 여기서 h(x) \ T[j]{.}\text{psl}: 항목 x를 버킷 j에 삽입하고, x와 T[j]를 교환한다—이를 x'라고 하자. (j+1)번째 버킷에서 x'를 삽입하기 위한 탐사를 계속한다. 모든 요소가 삽입될 때까지 이 절차를 반복한다.
# 동적 크기 조정
반복된 삽입은 해시 테이블의 엔트리 수를 증가시키고, 결과적으로 로드 팩터를 증가시킨다. 조회 및 삽입 작업의 분할 상환 O(1) 성능을 유지하기 위해 해시 테이블은 동적으로 크기가 조정되며, 테이블의 항목은 새 해시 테이블의 버킷으로 재해싱된다. 이는 다양한 테이블 크기가 모듈로 연산으로 인해 다른 해시 값을 초래하므로 항목을 단순히 복사할 수 없기 때문이다.pages=15–16 일부 요소를 삭제한 후 해시 테이블이 "너무 비어지면" 과도한 메모리 사용을 피하기 위해 크기 조정을 수행할 수 있다.access-date=9 November 2021
## 모든 엔트리를 이동하여 크기 조정
일반적으로 원래 해시 테이블 크기의 두 배인 새 해시 테이블이 사적으로 할당되고, 원래 해시 테이블의 모든 항목은 항목의 해시 값을 계산한 후 삽입 작업을 통해 새로 할당된 테이블로 이동된다. 재해싱은 간단하지만 계산 비용이 많이 든다.pages=464–488pp=478–479
## 일괄 재해싱의 대안
일부 해시 테이블 구현, 특히 실시간 시스템에서는 해시 테이블을 한 번에 모두 확장하는 비용을 지불할 수 없는데, 이는 시간 결정적인 작업을 방해할 수 있기 때문이다. 동적 크기 조정을 피할 수 없다면, 재해싱 중에 (일반적으로 새 테이블 크기의 50%에서) 저장 공간의 순간적인 증가를 피하고, 이전 해시 테이블의 대규모 메모리 블록 해제로 인한 메모리 단편화를 방지하여 힙 압축을 유발하는 솔루션은 점진적으로 크기 조정을 수행하는 것이다.url-status=livepp=2–3 이런 경우 재해싱 작업은 이전 해시 테이블에 할당된 메모리 블록을 확장하여 해시 테이블의 버킷이 변경되지 않도록 점진적으로 수행된다. 분할 상환 재해싱의 일반적인 접근 방식은 두 개의 해시 함수 h_\text{old}와 h_\text{new}를 유지하는 것이다. 새 해시 함수에 따라 버킷 항목을 재해싱하는 과정은 클리닝이라고 불리며, \mathrm{Add}(\mathrm{key}), \mathrm{Get}(\mathrm{key}) 및 \mathrm{Delete}(\mathrm{key})와 같은 작업을 커맨드 패턴을 통해 래퍼 \mathrm{Lookup}(\mathrm{key}, \text{command})로 캡슐화하여 각 버킷의 요소가 재해싱되고 그 절차는 다음과 같이 진행된다. * \mathrm{Table}[h_\text{old}(\mathrm{key})] 버킷을 청소한다. * \mathrm{Table}[h_\text{new}(\mathrm{key})] 버킷을 청소한다. * 명령이 실행된다.
### 선형 해싱
선형 해싱 선형 해싱은 테이블의 동적 증가 또는 감소를 한 번에 하나의 버킷씩 가능하게 하는 해시 테이블의 구현이다.access-date=10 November 2021
# 성능
해시 테이블의 성능은 해시 테이블의 엔트리에 대해 준무작위 숫자(\sigma)를 생성하는 해시 함수의 능력에 달려 있으며, 여기서 K, n 및 h(x)는 키, 버킷의 수 및 해시 함수를 나타내어 \sigma\ =\ h(K)\ \%\ n이다. 만약 해시 함수가 다른 키(K_1 \ne K_2,\ h(K_1)\ =\ h(K_2))에 대해 동일한 \sigma를 생성하면 충돌이 발생하며, 이는 다양한 방식으로 처리된다. 해시 테이블에서 연산의 상수 시간 복잡도(O(1))는 해시 함수가 충돌하는 인덱스를 생성하지 않는다는 조건에 따라 가정된다. 따라서 해시 테이블의 성능은 선택된 해시 함수가 인덱스를 분산시키는 능력에 정비례한다.year=20101 그러나 이러한 해시 함수를 구성하는 것은 실질적으로 불가능하며, 따라서 구현은 더 높은 성능을 달성하기 위해 사례별 충돌 해결 기술에 의존한다. 해시 함수가 유니버스 요소를 균일하게 분포시키고, 테이블에 저장된 요소가 유니버스에서 무작위로 추출될 때 최상의 성능을 얻을 수 있다. 이 경우 체이닝을 사용한 해싱에서 성공적인 검색의 예상 시간은 1+\frac{\alpha}{2}+\Theta\left(\frac{1}{m}\right)이고, 실패한 검색의 예상 시간은 e^{-\alpha}+\alpha+ \Theta\left(\frac{1}{m}\right)이다. isbn = 0849326494
# 응용 분야

## 연관 배열
연관 배열 해시 테이블은 많은 유형의 인메모리 테이블을 구현하는 데 일반적으로 사용된다. 이들은 연관 배열을 구현하는 데 사용된다..
## 데이터베이스 인덱싱
해시 테이블은 디스크 기반 자료 구조 및 데이터베이스 인덱스(예: dbm 등)로도 사용될 수 있지만, 이러한 응용 분야에서는 B 트리가 더 널리 사용된다.author= Lech Banachowski
## 캐시
캐시 (컴퓨팅) 해시 테이블은 캐시를 구현하는 데 사용될 수 있다. 캐시는 주로 느린 미디어에 저장된 데이터에 대한 접근 속도를 높이는 데 사용되는 보조 데이터 테이블이다. 이 응용 프로그램에서 해시 충돌은 충돌하는 두 엔트리 중 하나를 폐기함으로써 처리될 수 있다—일반적으로 테이블에 현재 저장된 오래된 항목을 지우고 새 항목으로 덮어쓰므로, 테이블의 모든 항목은 고유한 해시 값을 가진다.s2cid=212649328archive-date=4 December 2020
## 집합
집합 자료 구조 해시 테이블은 집합 자료 구조의 구현에 사용될 수 있으며, 이는 특정 순서 없이 고유한 값을 저장할 수 있다. 집합은 일반적으로 요소 검색보다는 컬렉션에 값의 멤버십을 테스트하는 데 사용된다.url-status=bot: unknown
## 전치 테이블
전치 테이블 전치 테이블은 검색된 각 섹션에 대한 정보를 저장하는 복잡한 해시 테이블이다.url-status=live
# 구현
많은 프로그래밍 언어는 내장 연관 배열 또는 표준 라이브러리 모듈 형태로 해시 테이블 기능을 제공한다. * 자바스크립트에서 "객체"는 키-값 쌍(속성이라고 함)의 변경 가능한 컬렉션으로, 각 키는 문자열이거나 보장된 고유 "심볼"이다. 다른 값은 키로 사용될 때 먼저 문자열로 강제 변환된다. 일곱 가지 "원시" 데이터 유형 외에, 자바스크립트의 모든 값은 객체이다.access-date=24 July 2022 ECMAScript 2015는 또한 임의의 값을 키로 허용하는 `Map` 자료 구조를 추가했다.language=en-US * C++11은 임의의 유형의 키와 값을 저장하기 위한 `unordered_map`을 표준 라이브러리에 포함한다.pages=812–813 * Go의 내장 `map`은 타입 형태의 맵 타입을 구현하며, 이는 종종 (항상 보장되는 것은 아니지만) 해시 테이블이다.access-date=January 1, 2023 * 자바 프로그래밍 언어에는 `HashSet`, `HashMap`, `LinkedHashSet` 및 `LinkedHashMap` 제네릭 컬렉션이 포함된다.df=mdy-all * 파이썬의 내장 `dict`는 타입 형태의 해시 테이블을 구현한다.doi-access=free * 루비의 내장 `Hash`는 루비 2.4부터 개방 주소 지정 모델을 사용한다.url-status=live * 러스트 프로그래밍 언어는 `HashMap`, `HashSet`을 러스트 표준 라이브러리의 일부로 포함한다.df=mdy-all * 닷넷.NET 표준 라이브러리에는 `HashSet` 및 `Dictionary`가 포함되어,language=en-uslanguage=en-us C# 및 VB.NET과 같은 언어에서 사용할 수 있다.website=Dot Net Perls
# 참조
; 내용주