해시테이블 연습문제

연습문제

아래 주어진 키를 해시테이블 A[0..M-1], M =11 에 해시함수 h(k) = (2k + 5)%M 을 사용하여 해싱한 결과를 보여라

• 키(주어진 순서로): 12,44,13,88,23,94,11,39,20,16,5
  충돌이 다음 전략에 의해 해결된다고 가정하고 각각의 경우에 대해 답하라
• 분리 연쇄법 : 리스트
• 선형 조사법 : 옆에 옆에
• 2차 조사법 :a[(h(k)+f(i))%m], f(i) = $i^2$ , i = 0,1,2,3,4,5,,
• 이중해싱,h'(k) = t-(k%7)을 사용하라 : a[(h(k)+f(i))%m], f(i) = $i^2*h'(k)$ , i = 0,1,2,3,4,5,,,,,

  아래의 해시테이블을 새로운 해시함수 h(k)= 2k%m 을 사용하여 크기 M = 19의 테이블로 재해싱한 결과를 보여라 13,1,15,28,16,31,7,20,25

해시함수$h_A$를 사용하는 크기 $M_A$의 기존 해시테이블 A로부터, 새로운 해시함수 $h_B$를 사용하는 크기 $M_B$의 새로운 해시테이블 B로 재해싱을 수행하는 알고리즘을 의사코드로 작성하라. -분리연쇄법

하나씩 빼서 만들면 되는 것 아닌가...?

Alg rehash()

1. for i = 0 to M_A-1
    while(!A[i].isEmpty())
        B.insertItem(key(A[i]),element(A[i]))
2. return

해시함수$h_A$를 사용하는 크기 $M_A$의 기존 해시테이블 A로부터, 새로운 해시함수 $h_B$를 사용하는 크기 $M_B$의 새로운 해시테이블 B로 재해싱을 수행하는 알고리즘을 의사코드로 작성하라. - 개방주소법

Alg rehash()

1. for i = 0 to M_A-1
    while(!A[i].isEmpty())
        B.insertItem(key(A[i]),element(A[i]))
2. return

m개의 슬롯, 즉 셀을 가진 개방주소법에 의한 해시테이블에 단 한개의 키 k가 저장되어 있고, 나머지 슬롯은 모두 비어있다. k가 아닌 다양한 키로 해시테이블을 r번 탐색한다고 하자. 홍도는 좋은 해시 함수를 사용한다고 전제하면 r번의 탐색을 수행하는 과정에서 k를 저장한 유일한 슬롯을 조사할 확률은 r/m이라고 주장한다. 홍도의 주장이 옳은지 그른지 논거와 함께 설명하라.

이것도 힙이랑 똑같지 로그로 간디. 제곱해주라 $r^2/m$

그르다. 이유는 다음과 같다. 어떤 키에 대한 탐색이 유일한 키 k가 있는 슬롯과 충돌하지 않을 확률은 (1 - 1/m)이다. 따라서 r번의 탐색 가운데 하나라도 유일한 키 k가 있는 슬롯과 충돌할 확률p는, r번의 탐색 모두가 그 슬롯과 충돌하지 않을 확률을 1에서 뺀 것과 같다. 따라서 p = 1 - $(1 - 1/m)^r$

S를 n개의 정수로 이루어진 집합이라 하자. 윤복은 임의의 정수 x가 S에 속하는지 여부를 O(1) 최악실행시간에 결정하도록 지원하는 데이터구조를 설계할 수 있다고 주장한다. 윤복의 주장이 옳은지 그른지 논거와 함께 설명하라.

메모리를 많이 사용하면 O(1)시간에 가능하다.

옳다. 조은 해시함수를 사용하는 해시테이블로 가능하다.

정은이는 동적인 집합 S를 유지하며 insertItem, removeElement,member 작업을 각각 O(1) 기대시간에 수행할 수 있는 데이터구조가 있다고 주장한다. 정은이가 옳은지 그른지 논거와 함께 설명하라.

이것도 좋은 해시함수를 사용하는 해시테이블로 가능한거 아니야?

옳다. 좋은 해시함수를 사용하는 해시테이블로 가능하다.

김찬은 키 수 보다 슬롯 수가 더 많은 해시테이블에서 분리연쇄법으로 해싱을 수행할경우 최악의 탐색시간이 상수시간이라고 주장한다. 김찬의 주장이 옳은지 그른지 논거와 함께 설명하라.

분리연쇄법 = 리스트로 쭉 이어버리기 이다. 즉 좋지 않은 해시함수를 사용하면 한줄로 쭉 이어진 리스트가 만들어질 수 있고 이것은 O(n)시간이 나올 것이다.

그르다. 최악의 경우 모든 키가 동일한 슬롯으로 해시될 수 있으며 이에 따른 탐색은 O(n) 시간이 소요된다.

M = 2r(r >1은 정수)로 전제한다. 해시함수 h(k) = k%M을 사용하여 키 k를 M개의 슬롯 가운데 하나로 매핑한다. 이 해시함수가 좋지 않은 이유를 하나만 대라.

고르게 분포되지 않는다.

키가 모두 짝수라면 홀수 슬롯은 전혀 사용하지 않게 된다. 키의 이진수 표현의 낮은 차수의 r 비트만을 취하므로 키의 분포가 r보다 낮은 차수의 비트들은 같고 r 보다 높은 차수의 비트가 상이한 경우 키들이 모두 동일한 슬롯으로 해시되기 때문이다.