선형 해싱

선형 해싱(Linear Hashing, LH)은 해시 테이블을 구현하고 버킷을 한 번에 하나씩 늘리거나 축소하는 동적 데이터 구조다.그것은 1980년에 위톨드 리트윈에 의해 발명되었다.^[1][2] 그것은 백자 예이츠와 소자 폴맨에 의해 분석되었다.^[3]그것은 라슨의 부분확장 선형 해싱, 우선순위 분할이 있는 선형^[5] 해싱, 부분확장 및 우선순위 분할이 있는 선형 해싱 또는 재귀적 선형 해싱과 같은^[4] 동적 해싱으로 알려진 여러 체계 중 첫 번째다.^[8]

동적 해싱 데이터 구조의 파일 구조는 파일 크기 변화에 적응하기 때문에 값비싼 정기적인 파일 재구성은 피할 수 있다.^[4]선형 해싱 파일은 미리 결정된 버킷을 둘로 분할하여 확장하고 미리 결정된 두 버킷을 하나로 병합하여 축소한다.재구성 트리거는 구성표의 향상에 따라 달라진다. 미리 정해진 범위 밖으로 이동하는 버킷 또는 로드 계수(버킷 수에 대한 레코드 수)에서 오버플로일 수 있다.^[1]

선형 해싱도 확장 가능한 분산 데이터 구조인 LH*로 만들어졌으며, LH*에서는 각 버킷이 다른 서버에 상주한다.^[9] LH* 자체는 장애가 발생한 버킷이 있는 상태에서 데이터 가용성을 제공하도록 확장되었다.^[10] LH 및 LH*의 키 기반 작업(삽입, 삭제, 업데이트, 읽기)은 버킷 수와 관계 없이 최대 일정 시간이 걸린다.^[1][10]

알고리즘 세부 정보

LH 또는 LH*의 레코드는 키와 콘텐츠로 구성되며, 후자는 기본적으로 레코드의 다른 모든 속성으로 구성된다.^[1][10]그것들은 양동이에 저장되어 있다.예를 들어 엘리스의 구현에서 버킷은 연결된 레코드 목록이다.^[2]이 파일은 키 기반 CRUD 작업뿐만 아니라 모든 레코드를 검색하는 검색 작업(예: 키 이외의 속성에서 데이터베이스 선택 작업)을 생성 또는 삽입, 읽기, 업데이트 및 삭제할 수 있다.^[10]레코드는 0으로 시작하는 버킷에 저장된다.^[10]

해시함수

키 $c{\displaystyle }$ ${\displaystyle$ c$}$이(가) 있는 레코드에 접근하기 위해$,$ 집합적으로 동적 해시함수라고 불리는 해시함수 패밀리를 $키{\displaystyle }$ c ${\displaystyle c}$에 적용한다$.$ 언제든지 최대 2개의 해시함수 h ${\displaystyle i_{}}$ ${\$${\displaystyle i_{}}$$}$와 h${\displaystyle {}_{}}$+ ${\displaystyle 1_{}}$ ${\$}가 사용된다$$.전형적인 예로는 디비전 modulo x 연산을 사용한다.원래 버킷 수가 $N{\displaystyle }$ ${\displaystyle N$인 경우 해시 함수 패밀리는

${\displaystyle h_{i}(c)\mapsto c{\pmod{N\cdot 2^{i}}}}}$

파일 확장

삽입을 통해 파일이 커지면 한 버킷을 두 버킷으로 분할하여 우아하게 확장된다.분할할 버킷의 순서는 미리 정해져 있다.이것은 파긴의 확장 가능한 해싱과 같은 계획의 근본적인 차이점이다.^[11] 2개의 새로운 버킷에 대해 해시함수 ${\displaystyle h_{}}$ i ${\$는 h ${\displaystyle i_{}}$+ ${\displaystyle 1_{}}$ ${\$로 대체된다$.$분할할 버킷 수는 파일 상태의 일부로서 분할 포인터 $s{\displaystyle }$ ${\displaystyle s}$라고 한다$.$^[10]

분할 제어

버킷이 넘칠 때마다 분할 작업을 수행할 수 있다.이것은 통제할 수 없는 분열이다.또는 파일이 로드 계수를 모니터링하여 로드 계수가 임계값을 초과할 때마다 분할을 수행할 수 있다.이것은 분할이 통제되었다.^[10]

주소 지정

주소 지정은 분할 $포인터{\displaystyle }$ s ${\displaystyle$ $s$$}$과 $수준{\displaystyle }$ l ${\displaystyle$ l$}$로 구성된 파일 상태를 기반으로 한다$.$ 수준이 $l{\displaystyle }$ ${\displaystyle l}$인 경우 사용되는 해시 함수는 ${\displaystyle h_{}}$ ${\$ 및$$ ${\displaystyle l_{}}$+ ${\$이다$.$

해싱 키 $c{\displaystyle }$ ${\displaystyle c}$에 대한 LH 알고리즘은$$^[10]

${\displaystyle a:=h_{l}(c)}$

: : + 1( ${\displaystyle a<s:a$:a$:$$=h_{l+1}(c)}$

쪼개기

버킷이 분할된 경우 분할 포인터 및 레벨은 다음과 같이^[10] 업데이트된다.

${\displaystyle s:=s+1}$

$s{\displaystyle }$ ${\displaystyle \ge }$ ${\displaystyle N}$ ${\displaystyle \times }$ 2 ${\displaystyle l^{}}$ ${\$ 2$^{l$ :${\displaystyle \mathrm{l}}$+ = 1$,$ = ${\displaystyle 0}${\$displaystyle l+=1$,s$=0}$

파일 축소

부하계수를 분할하여 제어하는 경우, 한계치 아래로 가라앉으면 병합 작업이 트리거된다.병합 작업은 마지막 분할을 해제하고 파일 상태도 재설정한다.^[10]

파일 상태 계산

$파일{\displaystyle }$ 상태는 분할 포인터 $s{\displaystyle }$ ${\displaystyle s}$ 및 $수준$ l ${\displaystyle l}$로 구성되며 원본 파일이$$N${\displaystyle }$= 1 ${\displaystyle$ N$=1}$ 버킷으로 시작된 경우$$ 버킷 수 n ${\$displaystyle n}과$(와)$ 파일$$ 상태는 다음을 통해 관련됨

${\displaystyle n=2^{l}+s}$

LH*

LH*의 주된 기여는 LH* 파일의 클라이언트가 파일 상태를 알 수 없더라도 레코드가 있는 버킷을 찾을 수 있도록 하는 것이다.클라이언트는 실제로 파일 상태의 버전을 저장하는데, 이것은 처음에는 버킷 0이라는 첫 번째 버킷의 지식일 뿐이다. 클라이언트는 파일 상태에 기초하여 키의 주소를 계산하고 그 버킷으로 요청을 보낸다.버킷에서 요청을 확인하고 레코드가 버킷에 없을 경우 전달한다.합리적으로 안정된 시스템, 즉 요청이 처리되는 동안 단 한 번의 분할 또는 병합만 진행 중인 경우, 최대 두 개의 포워드(proward)가 있음을 알 수 있다.전달 후 최종 버킷은 상태가 분산 파일의 상태에 더 가까운 클라이언트에 이미지 조정 메시지를 전송한다.^[10]포워드는 활동 중인 클라이언트의 경우 상당히 드물지만, 서버와 클라이언트 간의 추가 정보 교환을 통해 그 수를 더욱 줄일 수 있다.

언어 시스템의 채택

그리즈월드와 타운젠드는 아이콘 언어로 선형 해싱의 채택을 논의하였다.그들은 선형 해싱에 사용되는 동적 어레이 알고리즘의 구현 대안을 논의했고, 아이콘 벤치마크 애플리케이션 목록을 사용하여 성능 비교를 제시했다.

데이터베이스 시스템 채택

선형 해싱은 버클리 데이터베이스 시스템(BDB)에서 사용되는데, 이는 1988년 에스몬드 피트가 CACM 기사에서 파생하여 유스넷에 처음 게재한 C 구현을 사용하여 많은 소프트웨어 시스템에서 차례로 사용된다.

참조

외부 링크

• TommyDS, C 선형 해시테이블 구현
• An in Memory Go 구현(설명 포함
• 파일 시스템과 인메모리 스토리지를 모두 지원하는 선형 해시테이블의 C++ 구현

참고 항목

• 익스텐더블 해싱
• 일관된 해싱