[algorithm] 해시 테이블이 실제로 O (1) 일 수 있습니까?

요약 : 해시 테이블 O(1)은 범용 해시 함수 제품군에서 임의로 균일하게 해시 함수를 선택하는 경우 예상되는 최악의 경우 시간을 보장 합니다. 예상되는 최악의 경우는 평균 사례와 동일하지 않습니다.

면책 조항 : 저는 해시 테이블이라는 것을 공식적으로 증명하지 않습니다 . O(1)이는 coursera [ 1 ] 의이 비디오를 봤기 때문 입니다. 또한 해시 테이블 의 상각 된 측면에 대해서도 논의하지 않습니다 . 이는 해싱 및 충돌에 대한 논의와 직교합니다.

나는 다른 답변과 댓글 에서이 주제에 대해 놀랍도록 많은 혼란을 겪고 있으며이 긴 답변에서 일부를 수정하려고 노력할 것입니다.

최악의 경우에 대한 추론

다양한 유형의 최악의 경우 분석이 있습니다. 지금까지 대부분의 답변이 만든 분석 은 최악의 경우가 아니라 평균적인 경우입니다 [ 2 ]. 평균 사례 분석이 더 실용적인 경향이 있습니다. 알고리즘에 최악의 경우 하나의 입력이 있지만 실제로는 다른 모든 입력에 대해 잘 작동합니다. 결론은 런타임 이 실행중인 데이터 세트에 따라 달라진다 는 것 입니다.

get해시 테이블 메서드의 다음 의사 코드를 고려하십시오 . 여기서는 연결을 통해 충돌을 처리한다고 가정하므로 테이블의 각 항목은 연결된 (key,value)쌍 목록입니다 . 우리는 또한 버킷의 수를 가정 m고정되어 있지만 O(n), 여기서 n입력 요소의 수입니다.

function get(a: Table with m buckets, k: Key being looked up)
  bucket <- compute hash(k) modulo m
  for each (key,value) in a[bucket]
    return value if k == key
  return not_found

다른 답변에서 지적했듯이 이것은 평균 O(1)및 최악의 경우로 실행됩니다 O(n). 여기서 도전으로 증명의 작은 스케치를 만들 수 있습니다. 과제는 다음과 같습니다.

(1) 해시 테이블 알고리즘을 적에게 제공합니다.

(2) 적은 원하는만큼 공부하고 준비 할 수 있습니다.

(3) 마지막으로 공격자는 n테이블에 삽입 할 크기 를 입력 합니다.

문제는 적의 입력에 대한 해시 테이블이 얼마나 빠르 냐는 것입니다.

(1) 단계에서 공격자는 해시 함수를 알고 있습니다. 단계 (2) 동안 공격자는 예를 들어 여러 요소의 해시를 무작위로 계산하여 n동일한 요소 의 목록을 만들 수 있습니다 hash modulo m. 그리고 (3)에서 그들은 당신에게 그 목록을 줄 수 있습니다. 그러나 모든 n요소가 동일한 버킷으로 해시되므로 알고리즘이 O(n)해당 버킷의 연결 목록을 순회하는 데 시간 이 걸립니다 . 우리가 챌린지를 몇 번 재 시도해도 적은 항상 이기고 알고리즘이 얼마나 나쁜지 최악의 경우 O(n)입니다.

해싱은 어떻게 O (1)입니까?

이전 도전에서 우리를 좌절시킨 것은 적들이 우리의 해시 함수를 아주 잘 알고 있었고 그 지식을 사용하여 가능한 최악의 입력을 만들 수 있다는 것입니다. 항상 하나의 고정 된 해시 함수를 사용하는 대신 H알고리즘이 런타임에 임의로 선택할 수있는 해시 함수 집합이 실제로 있다면 어떨까요? 궁금한 점이 있으면 해시 함수H 의 범용 제품군 [ 3 ]이라고합니다. 좋습니다. 여기에 임의성 을 추가해 보겠습니다 .

먼저 우리의 해시 테이블도 씨앗을 포함한다고 가정 r하고, r시공시 임의의 숫자에 할당됩니다. 한 번 할당하면 해시 테이블 인스턴스에 대해 수정됩니다. 이제 의사 코드를 다시 살펴 보겠습니다.

function get(a: Table with m buckets and seed r, k: Key being looked up)
  rHash <- H[r]
  bucket <- compute rHash(k) modulo m
  for each (key,value) in a[bucket]
    return value if k == key
  return not_found

도전을 한 번 더 시도하면 (1) 단계에서 공격자는 우리가 가지고있는 모든 해시 함수를 알 수 H있지만 이제 우리가 사용하는 특정 해시 함수는에 의존합니다 r. 의 값은 r우리 구조에 비공개이며, 공격자는이를 런타임에 검사하거나 미리 예측할 수 없으므로 항상 우리에게 나쁜 목록을 만들 수 없습니다. 의 단계에서 (2) 대적 하나 개의 기능을 선택한다고 가정하자 hash에서 H무작위로, 그는 다음 목록으로 만들어줍니다 n에서 충돌 hash modulo m, 그리고 보냅니다 런타임에 있음을 손가락을 교차 단계 (3)에 대해 H[r]동일합니다 hash그들이 선택합니다.

이것은 적들에게 심각한 내기이며 그가 만든 목록은.에서 충돌 hash하지만의 다른 해시 함수 아래에서 무작위 입력이 될 것입니다 H. 그가이 내기에서 이기면 우리의 실행 시간은 O(n)이전과 같이 최악의 경우가 될 것이지만 그가지면 평균 O(1)시간 이 걸리는 임의의 입력을 받게 됩니다. 그리고 실제로 대부분의 적이지는 경우, 그는 모든 |H|도전에서 단 한 번만 이기며 우리는 |H|매우 크게 만들 수 있습니다.

이 결과를 적이 항상 도전에서이긴 이전 알고리즘과 대조하십시오. 여기에 조금 Handwaving하지만 이후 대부분의 시간 대적이 실패하고 이것이 사탄이 시도 할 수있는 모든 전략에 대한 사실, 최악의 경우가 있지만 것을 다음 O(n)의 예상되는 최악의 경우는 사실이다 O(1).

---

다시 말하지만 이것은 공식적인 증거가 아닙니다. 이 예상 최악의 경우 분석에서 얻을 수있는 보장은 런타임이 이제 특정 입력과 독립적이라는 것 입니다. 이것은 우리가 동기를 부여한 적이 나쁜 입력을 쉽게 만들 수 있음을 보여준 평균 사례 분석과는 달리 진정한 무작위 보장입니다.

---

답변