#009 DS&A-해시

산열

직접 주소표

우리는 많은 데이터 구조를 가지고 있지만, 그것들은 검색 방면에서 매우 느리다.
유형
시간 복잡성
정렬되지 않은 그룹
O(n)
배열 정렬
O (대수 n)
체인 미터
O(n)
두 갈래 나무
O(n)
두 갈래 검색 트리
O(n)
균형 두 갈래 검색 트리
O (대수 n)
우선 순위 (최소 및 최대)
O(n)
검색 시간을 최소화하기 위해 산열O(1)을 사용했고 Direct address Table도 수조와 동일하게 사용했다.{1,2,3,4,5,...,100} 만약 우리가 하나의 요소를 삽입해야 한다면, 우리는 그것을 하나의 키와 함께 놓고 저장할 것이다. 만약에 우리가 저장해야 하는 문자의 출현 횟수C ASCII의 수량을 가정하면 128이다arr[99] 나는 이 수조에 c의 출현 횟수를 저장할 것이다. 그중99은 c의 키이다
현재 알파벳의 수량c에 접근해야 한다면, arr[99]을 직접 사용할 수 있습니다. 즉, O(1)

해시 소개

이런 직접적인 접근 문제는 수조의 크기가 키 크기만큼 커야 한다는 것이다. 이 문제를 해결하기 위해 우리는 해시를 사용한다.
만약 우리가 m 개의 키와 n 개의 원소를 가지고 있다고 가정하자.akey를 element에 비추기 위해서는 hash function가 필요합니다. 이 시간은 상수n%m입니다.새로운 요소를 하나의 요소로 산열하고 이전 요소와 같은 위치를 가져야 할 때, 우리는 충돌 예시 O(1) 와 141%10=1 라고 부른다. 따라서 이것은 충돌이다. 왜냐하면 그들은 같은 키를 가지고 있기 때문이다.해시가 비추는 도전은 충돌이다.

  i) better hash functions
 ii) chaining (using linked list)
iii) open addressing , implemented using verious ways
  a) linear probing
  b) quadratic probing
  c) Double hashing

링크

충돌이 발생하면 해시를 계산한 후 이전 값이 새 값으로 연결됩니다.

worst case search - O(n)
worst case deletion - O(n)

average search O(1+ alpha)
average deletion O(1)

그중21%10=1은 체인 테이블에 표시된 원소수이고 n는 체인 테이블에 표시된 단원 수이다.m, 그 중에서 알파는 부하 계수이다.
오픈 주소 찾기 방안에 비해 체인식 해시표는 삭제가 쉽다는 장점이 있다.

오픈 주소 지정

개방 주소 찾기를 폐합해시라고도 부른다

만약에 우리가 alpha = n/m개의 원소를 수용할 수 있는 수조를 가지고 있다고 가정하면 이것은 내가 필요로 하는 모든 원소는 체인과 m키처럼 외부에 있는 것이 아니라 수조 내부에 있어야 한다는 것을 의미한다. 그 중에서 U는 매우 크고 U는 유한하기 때문에 그것들은 틀림없이 충돌할 것이다.
우리는 부하 계수m가 있는데, 그것은 항상 alpha와 0 사이에 있다.
우리는 해시 함수를 응용하여 충돌을 해결하고 작은 수정을 진행했는데 이를 2차 탐지라고 부른다.탐측은 단지 해시표에서 우리가 원소를 놓아야 할 위치를 찾을 뿐이다.

우리는 해시 함수를 응용한다. 만약 우리가 원소가 선택되었다는 것을 발견한다면, 우리는 1 과 유한 집합 u 사이를 조합할 것이다
원소를 검색하는 데 가장 나쁜 시간은 [0,m-1] 입니다. 모든 테이블에 접근해서 원소를 찾아야 하기 때문입니다.

가령 O(m) 은 슬롯이 비어 있지 않고 X 비어 있다고 가정합니다.

h(k)        = 0

N는 NULL이므로 1를 넣을 수 있습니다.

h(k1)       = 1
h(k1 , 1)   = 5
h(k1 , 2)   = 6

k은h(k1)이지만 1은 자유가 아니다. (충돌이다) 그래서 우리는 다시 해시 함수를 운행하여 얻는다1. 그것도 자유롭지 않다. 그래서 우리는 다시 그것을 운행한다. 얻는다5. 그것은 비어 있다.
같은 검색은 우리가 필요로 하는 요소2가 슬롯6에 있다고 가정합니다

h(k,0) = 2
h(k,1) = 6
h(k,2) = 3
...
h(k,7) = 0

그래서 제가 k1 최악의 상황에서 찾았어요.
가령 0 슬롯 O(m) 이 아니라 k1 에 있다고 가정하면 5 에 도착해서 7 을 찾으면 멈출 것입니다. 왜냐하면 이 요소가 나타나지 않았다는 것을 알고 있기 때문입니다. h(k,5) 이 아니라면 해시 함수 NULL 가 그것을 차지할 것입니다.
요소를 삭제하지 않으면 이러한 상황이 발생합니다.만약 삭제된다면, 나는 계속 검색할 것이다.그래서 삭제는 문제를 일으킬 수 있기 때문에 저는 원소를 분배할 것입니다. 이것은 여기에 원소가 있다는 것을 의미합니다. 예를 들어 NULL 그러나 원소가 삭제되었습니다. 삽입에서 만약에 제가 k1 원소를 찾으면 D 원소로 간주하기 때문에 저는 원소로 대체합니다.
최악의 경우 모든 요소를 삭제하고 그 다음에 하나의 요소가 필요하다면 이런 상황에서 링크가 가장 좋다.

선형 탐지

h : U --> {0 ... m-1}

만약 내가 D 인덱스를 NULL 로 실행하고, h(k) = a 가 비어 있지 않다면, 나는 또 다른 산열 함수 h소수 a, 즉 a 와 h'(k,i)=(h(k)+i) mod m 를 취할 것이다
이것은 선형 탐지라고 불린다. 만약h'(k,1) = ( h(k)+1) mod n = (a+1) mod m = a+1에 있는 원소가 점용된다면, 시도할 것이다h'(k,2) = ( h(k)+2) mod n = (a+2) mod m = a+2, 시도할 것이다a, 시도할 것이다a+1, 다시 a+2부터m따라서 0 에서 시작하면 a 에서 시작하여 1 에서 끝납니다. 1 에서 시작하면 0 에서 끝납니다.
prob 시퀀스의 수량은 {1,2,3 ... m-1 , 0} 입니다.만약 두 원소의 초기 프로브가 같다면 2차 집합이라고 부른다.마스터 클래스는 연속 메모리 블록 순서가 사용되면 k 부터 k-1 까지 채워지는 것을 의미하므로 요소 삽입 확률은 m최악의 검색은 a 이지만 평균치는 상수 a+k 다. 증명은 많지만 어렵고 고급 확률의 정리가 많이 포함되어 있다.

이차 탐지

k+1/m2차 탐지의 문제는 O(m) 전체 표를 검사하기 위해 O(2.5) 을 선택해야 한다는 것이다.

이중 산열

h'(k,i) = ( h(k) + c1*i + c2 i*i ) mod m만약 두 원소가 같은 c1 , c2 and m을 가지고 있다면, h'(k,i) 같지 않을 수 있다
선택 h'(k) = ( h1(k) + i * h2(k) ) mod m2차 산열 함수h1는 0의 인덱스를 생성해서는 안 된다

전체 테이블에서 순환해야 한다

계산 속도가 매우 빠를 것이다

그것은 쌍으로 독립해야 한다 h2

h2(k)의 분포 특징은 무관하다.이것은 랜덤 생성기와 유사하다. 단지 h2(k) 가 h1(k) 의'상대소수'일 뿐이다.

실제로 두 함수 모두 제파해시를 사용한다면 제수는 소수로 선택된다.