11.4.md

Exercises 11.4-1

---

Consider inserting the keys 10, 22, 31, 4, 15, 28, 17, 88, 59 into a hash table of length m = 11 using open addressing with the primary hash function h'(k) = k mod m. Illustrate the result of inserting these keys using linear probing, using quadratic probing with c1 = 1 and c2 = 3, and using double hashing with h2(k) = 1 + (k mod (m - 1)).

Answer

index	linear probing	quadratic probing	double hashing
0	22	22	22
1	88
2		88	59
3		17	17
4	4	4	4
5	15		15
6	28	28	28
7	17	59	88
8	59	15
9	31	31	31
10	10	10	10

Exercises 11.4-2

---

Write pseudocode for HASH-DELETE as outlined in the text, and modify HASH-INSERT to handle the special value DELETED.

Answer

HASH-DELETE(T, k):
	i <- 0
	repeat j <- h(k, i)
		if T[j] == k:
			T[j] = "DELETED"
			return
		else if T[j] == NIL:
			break
		else:
			i <- i + 1
	until i == m
	error "k is not in T"
	
	
HASH-INSERT(T, k):
	i <- 0
	repeat j <- h(k, i)
		if T[j] == NIL || T[j] == "DELETED":
			T[j] = k
			rteurn j
		else i <- i + 1
	until i == m
	error "hash table overflow"

Exercises 11.4-3

---

Suppose that we use double hashing to resolve collisions; that is, we use the hash function h(k, i) = (h1(k)+ih2(k)) mod m. Show that if m and h2(k) have greatest common divisor d ≥ 1 for some key k, then an unsuccessful search for key k examines (1/d)th of the hash table before returning to slot h1(k). Thus, when d = 1, so that m and h2(k) are relatively prime, the search may examine the entire hash table. (Hint: See Chapter 31.)

Answer

简单了解下，这应该算是费马定理（如果没记错）

假设我们有3和7,3作为generator可以生成阶为6的子群，在这种情况下

3*1 mod 7 = 3

3*2 mod 7 = 6

3*3 mod 7 = 2

3*4 mod 7 = 5

3*5 mod 7 = 1

3*6 mod 7 = 4

3*7 mod 7 = 0

如果两个数字互质，那么一个数字的幂的模可以遍历一圈！也就是3 * n mod 7 = 3 * (n+7) mod 7.

对这个题目来说，如果d = 1,则要检查全部的散列.因为要遍历m个位置.

如果d > 1,那么h2(k)和m同时除d后又互质.可能要遍历m/d个位置.

Exercises 11.4-4

---

Consider an open-address hash table with uniform hashing. Give upper bounds on the expected number of probes in an unsuccessful search and on the expected number of probes in a successful search when the load factor is 3/4 and when it is 7/8.

Answer

Theorem 11.6. Given an open address hash table with load factor α = n/m < 1, the expected number of probes in an unsuccessful search is at most 1/(1-α), assuming uniform hashing.

α = ¾, then the upper bound on the number of probes = 1 / (1 - ¾ ) = 4 probes

α = 7/8, then the upper bound on the number of probes = 1 / (1-7/8) = 8 probes

Theorem 11.8. Given an open address hash table with load factor α = n/m < 1, the expected number of probes in a successful search is at most (1/α) ln (1/(1-α)), assuming uniform hashing and assuming that each key in the table is equally likely to be searched for.

α = ¾. (1/ ¾) ln (1/ (1 – ¾)) = 1.85 probes α = 7/8. (1/ .875) ln (1/ (1 – .875)) = 2.38 probes

Exercises 11.4-5

---

Consider an open-address hash table with a load factor α. Find the nonzero value α for which the expected number of probes in an unsuccessful search equals twice the expected number of probes in a successful search. Use the upper bounds given by Theorems 11.6 and 11.8 for these expected numbers of probes.

Answer

1/(1-α) = ln(1/(1-α)) * 2/α

解得α ＝ 0.717

---

Follow @louis1992 on github to help finish this task.