선형 프로빙

선형 프로빙은 해시 테이블의 충돌을 해결하기 위한 컴퓨터 프로그래밍, 키-값 쌍의 컬렉션을 유지하기 위한 데이터 구조, 주어진 키와 관련된 값을 찾기 위한 체계다.1954년 진 암달, 일레인 맥그로우, 아서 사무엘이 발명했으며 1963년 도널드 크누스가 처음 분석했다.

2차 프로빙 및 이중 해싱과 함께 선형 프로빙은 오픈 어드레싱의 한 형태다.이러한 체계에서 해시 테이블의 각 셀은 단일 키-값 쌍을 저장한다.해시함수가 이미 다른 키가 차지하고 있는 해시 테이블의 셀에 새 키를 매핑하여 충돌을 일으키면, 선형 프로빙은 테이블에서 가장 가까운 다음의 자유 위치를 검색하여 그 곳에 새 키를 삽입한다.검색은 해시함수가 부여한 위치에서 시작하여 일치하는 키나 빈 셀이 있는 셀을 찾을 때까지 순차적으로 테이블을 검색하는 방식으로 진행된다.

Thorup & Zhang(2012년)은 "해시 테이블은 가장 일반적으로 사용되는 비교 데이터 구조로, 표준 하드웨어에서 가장 많이 사용되는 구현은 빠르고 간단하다"^[1]고 썼다.선형 탐침은 참조의 지역성이 좋아 고성능을 제공할 수 있지만, 해시함수의 품질에 대해 다른 충돌해결방식보다 민감하다.무작위 해시함수, 5개 독립 해시함수 또는 표 해싱을 사용하여 구현하면 검색, 삽입 또는 삭제당 일정한 예상 시간이 소요된다.또한 DumorHash와 같은 다른 해시함수와 함께 실제로 좋은 결과를 얻을 수 있다.^[2]

운영

선형 프로빙은 해시 테이블을 사용하여 사전 문제를 해결하기 위한 오픈 어드레싱 방식의 구성요소다.사전 문제에서 데이터 구조는 수집에서 쌍을 삽입하거나 삭제하거나 특정 키와 관련된 값을 검색하는 작업의 대상이 되는 키 값 쌍의 컬렉션을 유지해야 한다.이 문제에 대한 오픈 어드레싱 솔루션에서 데이터 구조는 배열 T(해시 테이블)로, 셀 T[i](비어 있지 않을 때) 각각 하나의 키-값 쌍을 저장한다.해시함수는 키를 저장해야 하는 T의 셀에 각 키를 매핑하는 데 사용되며, 일반적으로 유사한 값을 가진 키가 테이블에서 서로 가까이 배치되지 않도록 키를 앞다퉈 배치한다.해시함수가 키를 다른 키가 이미 점유하고 있는 셀에 매핑할 때 해시 충돌이 발생한다.선형 프로빙은 새 키를 다음 빈 셀에 가장 가깝게 배치하여 충돌을 해결하는 전략이다.^[3][4]

검색

지정된 키 x를 검색하기 위해, 인덱스 h(x)의 셀(여기서 h는 해시함수)에서 시작하여 인접한 셀 h(x) + 1, h(x) + 2 ...까지 계속하여 빈 셀이나 저장된 키가 x인 셀을 찾는다. 키가 들어 있는 셀이 발견되면, 검색은 해당 셀로부터 값을 반환한다.그렇지 않으면 키가 빈 셀이 발견되면 아직 검색되지 않은 어떤 이후의 셀보다 우선하여 해당 셀에 배치되었을 것이므로 테이블에는 키가 있을 수 없다.이 경우 사전에는 키가 없다는 결과로 검색이 반환된다.^[3][4]

삽입

키-값 쌍(x,v)을 표에 삽입하기 위해(아마도 기존 쌍을 동일한 키로 대체하기 위해), 삽입 알고리즘은 빈 셀이나 저장된 키가 x인 셀을 찾을 때까지 검색 시 따라오는 동일한 셀 순서를 따른다.그런 다음 새로운 키-값 쌍이 해당 셀에 배치된다.^[3][4]

삽입으로 인해 테이블의 부하 계수(점유된 셀의 일부분)가 사전 설정된 임계값을 초과하게 될 경우, 동적 배열에서와 같이 새로운 해시 함수로 테이블 전체를 상수 계수에 의해 더 큰 새 테이블로 대체할 수 있다.이 임계값을 0에 가깝게 설정하고 테이블 크기에 대해 높은 증가율을 사용하면 해시 테이블 작업이 빨라지지만 메모리 사용량이 임계값보다 증가하며 증가율이 낮다.일반적인 선택은 부하 계수가 1/2을 초과하여 부하 계수가 1/4에서 1/2 사이로 유지될 때 표 크기를 두 배로 하는 것이다.^[5]

삭제

사전에서 키-값 쌍을 제거할 수도 있다.그러나 단순히 셀을 비우는 것으로는 충분치 않다.이것은 비어있는 셀보다 이전 해시 값을 가지지만 비어있는 셀보다 늦은 위치에 저장되는 다른 키 검색에 영향을 줄 것이다.빈 셀은 이러한 검색이 키가 없다고 잘못 보고하게 할 수 있다.

그 대신, 셀 i가 비었을 때, 다른 빈 셀이나 셀 i로 이동할 수 있는 키(즉, 해시 값이 i와 같거나 이전인 키)를 찾을 때까지 표의 다음 셀을 통해 정방향으로 검색할 필요가 있다.빈 셀이 발견되면 셀을 비우는 것은 안전하며 삭제 과정이 종료된다.그러나 검색에서 cell i로 이동할 수 있는 키를 찾으면 이 이동을 수행한다.이는 이동된 키를 나중에 검색하는 속도를 높이는 효과가 있지만, 나중에 점유된 동일한 셀 블록에서 다른 셀을 비우는 효과도 있다.이동 가능한 키를 찾기 위한 검색은, 같은 방법으로, 이미 비어 있던 셀에 도달하여 종료될 때까지 계속된다.키를 이전 셀로 이동하는 이 과정에서는 각 키를 한 번만 검사한다.따라서 전체 공정을 완료하는 시간은 삭제된 키를 포함하는 점유된 셀 블록의 길이에 비례하여 다른 해시 테이블 작업의 실행 시간과 일치한다.^[3]

또는 삭제된 키를 나타내는 특수 플래그 값으로 값을 대체하여 키-값 쌍을 제거하는 게으른 삭제 전략을 사용할 수 있다.그러나 이러한 플래그 값은 해시 테이블의 부하율에 기여한다.이 전략을 사용하면 어레이에서 플래그 값을 지우고 어레이의 일부분이 삭제된 키에 의해 점유되면 나머지 키-값 쌍을 모두 재해시해야 할 수 있다.^[3][4]

특성.

선형 프로빙은 참조의 좋은 위치를 제공하므로 작업당 캐시되지 않은 메모리 액세스가 거의 필요하지 않다.이 때문에 저부하 계수에서 중저부하 계수의 경우 매우 높은 성능을 제공할 수 있다.그러나, 일부 다른 오픈 어드레싱 전략에 비해, 1차 클러스터링으로 인해 높은 부하 요소에서 성능이 더 빨리 저하되며, 이는 한 번의 충돌이 더 많은 인근 충돌을 유발하는 경향이다.^[3]또한 이 방법으로 좋은 성능을 얻으려면 다른 충돌해결방식보다 고품질 해시함수가 필요하다.^[6]입력분포에서 불균일성을 제거하지 못하는 저품질 해시함수와 함께 사용할 경우, 선형 프로빙은 2차 해시함수에 의해 분리가 결정되는 셀의 시퀀스를 프로빙하는 이중 해싱이나 각 단계의 크기가 변화하는 2차 프로빙과 같은 다른 오픈 애드레스 전략보다 느릴 수 있다.프로브 시퀀스 내의 위치에 대기 중.^[7]

분석

선형 탐색을 사용하면 사전 연산을 일정한 예상 시간에 구현할 수 있다.즉, 해시 테이블의 부하계수가 1보다 절대적으로 적은 상수인 한, O(1)에서 삽입, 제거, 검색 연산을 실시할 수 있다.^[8]

좀 더 자세히 설명하면, 특정 작업(검색, 삽입 또는 삭제)에 대한 시간은 작업이 시작되는 점유 셀의 연속 블록의 길이에 비례한다.모든 시작 셀이 동일하게 될 가능성이 있는 경우, N 셀과 해시 테이블에서 k 점유 셀의 최대 블록은 검색의 시작 위치를 포함하는 확률 k/N을 가지며, 시작 위치일 때마다 O(k)가 소요된다.따라서 수술에 대한 예상 시간은 표에 있는 연속 셀의 모든 최대 블록을 합한 O(k²/N)라는 두 용어의 산물로 계산할 수 있다.블록 길이의 제곱의 비슷한 합은 (해시 테이블의 특정 상태로 무작위 시작 위치가 아닌) 존재할 수 있는 모든 블록을 합산하고 각 잠재적 b에 대한 항을 곱함으로써 (해시 테이블의 특정 상태로의 무작위 시작 위치가 아닌) 무작위 해시 함수에 대한 기대 시간을 제공한다.블록이 실제로 점유되었을 확률을 기준으로 잠근다.즉, 블록(i,k)을 지수 i에서 시작하는 길이 k의 점유된 셀의 최대 연속 블록이 있는 이벤트로 정의하며, 작동당 예상 시간은 다음과 같다.

${\displaystyle E[T]=O(1)+\sum _{i=1}^{N}\sum _{k=1}^{k=1}O(k^{2}/N)\operatorname {Pr} [\opername {Block}(i,k)]}$

이 공식은 블록(i,k)을 보다 단순하게 필요한 조건인 Full(k)으로 대체하여 단순화할 수 있는데, 적어도 k 요소가 k 길이의 셀 블록 안에 있는 해시 값을 갖는 사건이다.이 대체 후, 합 내의 값은 더 이상 i에 의존하지 않으며, 1/N 인자는 외부 합계의 N 항을 취소한다.이러한 단순화는 바운드로 이어진다.

${\displaystyle E[T]\leq O(1)+\sum _{k=1}^{n(k^{2})\operatorname {Pr}[\operatorname {Full}(k)].}$

그러나 Chernoff 바운드의 승법형태에 의해 하중계수가 1로부터 떨어져 있을 때 길이 k의 블록이 적어도 khash 값을 포함할 확률은 k의 함수로서 기하급수적으로 작아져 이 합이 n에 대해 일정한 독립성을 가지도록 한다.^[3]또한 블록이 정확히 k 해시 값을 포함할 확률을 추정하기 위해 결합된 Chernoff 대신 Stirling의 근사치를 사용하여 동일한 분석을 수행할 수도 있다.^[4][9]

하중 계수 α의 관점에서, 성공적인 검색의 예상 시간은 O(1 + 1/(1 - α)이고, 실패한 검색(또는 새 키 삽입)의 예상 시간은 O(1 + 1/(1 - α)^2[10]이다.높은 확률로 일정 부하 인자의 경우, 가장 긴 프로브 시퀀스(테이블에 저장된 모든 키에 대한 프로브 시퀀스 중)는 로그 길이를 가진다.^[11]

해시함수의 선택

선형 프로빙은 특히 불균등하게 분포된 해시 값에 민감하기 때문에 이러한 불규칙성을 발생시키지 않는 고품질 해시함수와 결합하는 것이 중요하다.^[7]

위의 분석에서는 각 키의 해시가 다른 모든 키의 해시와 독립된 난수라고 가정한다.이러한 가정은 해싱의 대부분의 적용에 비현실적이다.그러나 임의의 해시 값이나 가성 해시 값은 객체의 값이 아닌 자신의 정체성으로 객체를 해시할 때 사용할 수 있다.예를 들어, 이것은 Java 컬렉션 프레임워크의 IdentityHashMap 클래스에 의한 선형 프로빙을 사용하여 수행된다.^[12]이 클래스가 각 개체와 연결하는 해시 값, ID해시코드(HashCode)는 객체의 수명 동안 고정된 상태를 유지하도록 보장되지만 그렇지 않으면 임의적이다.^[13]왜냐하면 정체성이해시코드는 개체당 한 번만 생성되며, 개체의 주소나 값과 관련될 필요가 없으며, 해시코드의 구성은 무작위 또는 유사수 생성기로의 호출과 같은 느린 계산을 포함할 수 있다.예를 들어, 자바 8은 Xorshift 가성수 생성기를 사용하여 이러한 값을 구성한다.^[14]

해싱의 대부분의 어플리케이션의 경우, 객체가 생성될 때 한 번이 아니라 해시될 때마다 각 값에 대한 해시함수를 계산하는 것이 필요하다.이러한 애플리케이션에서 랜덤 또는 유사성 번호는 해시 값으로 사용할 수 없다. 왜냐하면 같은 값을 가진 다른 개체들은 해시가 다르기 때문이다.그리고 암호 해시함수(정확히 랜덤함수와 구분할 수 없도록 계산적으로 설계한 것)는 보통 해시표에서 사용하기에는 너무 느리다.^[15]대신 해시함수를 구성하는 다른 방법들이 고안되었다.이 방법들은 해시함수를 빠르게 계산하며, 선형 탐침과 함께 잘 작동한다는 것을 증명할 수 있다.특히, 선형 프로빙은 작은 무작위 시드로부터 초기화되며, 구별되는 키의 어떤 k-tuple도 인덱스의 k-tuple에 매핑할 가능성이 동일한 해시함수의 종류인 k-독립 해싱의 프레임워크로부터 분석되었다.매개변수 k는 해시함수 품질의 척도로 생각할 수 있다: k가 클수록 해시함수를 계산하는 데 더 많은 시간이 걸리지만 완전히 랜덤함수와 더 비슷하게 동작한다.선형 프로빙의 경우, 5 독립성은 작동당 일정한 예상 시간을 보장하기에 충분한 반면,^[16] 일부 4 독립 해시 함수는 작동당 로그 시간까지 차지하면서 나쁜 성능을 발휘한다.^[6]

높은 품질과 실제 속도를 모두 갖춘 해시함수를 구성하는 또 다른 방법은 표 해싱이다.이 방법에서 키의 해시 값은 각 바이트를 인덱스로 사용하여 무작위 번호표(각 바이트 위치에 대해 다른 테이블 포함)로 계산한다.그런 다음 테이블 셀의 숫자는 비트 배타적 또는 연산에 의해 결합된다.이런 방식으로 구성된 해시함수는 3개 독립적일 뿐이다.그럼에도 불구하고 이러한 해시함수를 이용한 선형 탐사는 연산당 일정한 예상 시간이 소요된다.^[4][17]5개 독립 해시함수를 생성하기 위한 표 해싱과 표준 방법 모두 비트 수가 고정된 키로 제한된다.문자열이나 다른 유형의 가변 길이 키를 처리하기 위해서는 키를 중간 값에 매핑하는 간단한 범용 해싱 기법과 중간 값을 해시 테이블 인덱스에 매핑하는 고품질(5 독립 또는 표) 해시함수를 구성할 수 있다.^[1][18]

In an experimental comparison, Richter et al. found that the Multiply-Shift family of hash functions (defined as ${\displaystyle h_{z}(x)=(x\cdot z{\bmod {2}}^{w})\div 2^{w-d}}$) was "the fastest hash function when integrated with all hashing schemes, i.e., producing the highest throughp표 해싱이 "최저 처리량"^[2]을 산출한 반면, uts 및 품질도 우수하다.그들은 각 테이블 검색은 단순한 산술 연산보다 비용이 더 많이 들면서 몇 번의 사이클을 필요로 한다고 지적한다.그들은 또한 DumorHash가 표 해싱보다 우월하다는 것을 발견했다: "Mult와 Summer가 제공한 결과를 연구함으로써, 표에 의한 (...)의 트레이드오프가 실제로는 덜 매력적이라고 생각한다."

역사

데이터를 주소보다는 가치로 접근할 수 있게 하는 연관 배열의 아이디어는 콘래드 주즈와 바네바 부시의 작품에서는 1940년대 중반으로 거슬러 올라가지만 해시 테이블은 1953년에야 한스 피터 룬의 IBM 비망록에서 설명되었다.^[19]룬은 선형 탐색이 아닌 체인, 다른 충돌 분해능 방법을 사용했다.^[20]

크누스(1963년)는 선형 탐사의 초기 역사를 요약한다.그것은 첫 번째 공개 주소 지정 방법이었고, 원래 공개 주소 지정과 동의어였다.크누스에 따르면, 1954년 진 암달, 일레인 맥그로(네 보엠), 아서 사무엘이 IBM 701 컴퓨터의 조립자 프로그램에 처음 사용했다고 한다.^[8]선형 탐사에 대한 첫 번째 출판된 설명은 피터슨(1957)이 쓴 것인데,^[8] 피터슨은 또한 새뮤얼, 암달, 보엠의 학점을 인정하지만, "이 시스템은 너무나 자연스러워서, 그 이전이나 그 이후 다른 사람들에 의해 독립적으로 구상되었을 가능성이 매우 높다"고 덧붙인다.^[21]이 방법의 또 다른 초기 출판물은 1958년 소련의 연구원 안드레이 어쇼프에 의해 출판되었다.^[22]

무작위 해시함수로 연산당 일정한 예상 시간이 소요된다는 것을 보여주는 선형 프로빙의 첫 번째 이론적 분석은 Knuth가 제공했다.^[8]세지윅은 크누스의 작품을 "알고리즘 분석의 랜드마크"^[10]라고 부른다.유의미한 후기 개발에는 가동 시간의 확률 분포에 대한 보다 상세한 분석과,^[23][24] 선형 탐색이 이전 분석에 의해 가정된 이상화된 무작위 함수가 아닌 실제 사용 가능한 해시 함수로 작동당 일정한 시간 내에 실행된다는 증거가 포함된다.^[16][17]

참조