9.1Hashing-17
- 假設(shè)我們有一個(gè)有大小m的表(哈希表)。
- 這個(gè)想法是用一個(gè)函數(shù)h: ={1接奈，…通孽，m}(哈希函數(shù))來確定記錄存儲(chǔ)的位置:一個(gè)key k的記錄應(yīng)該存儲(chǔ)在h(k)位置。地址h(k)是哈希地址背苦。
- hash支持的操作:
– find
– insert
– lookup (search and insert if not there)
– initialise
– delete
– rehash - hash面臨的挑戰(zhàn)
– Design of hash functions.
– Collision handling.
9.1.1 hash function
- 如果我們有一個(gè)大小為m的哈希表，并且鍵是整數(shù)秕噪，我們可以定義
h(n)= n mod m - 但是鍵可能是其他東西厚宰，比如字符串，hash函數(shù)應(yīng)該應(yīng)用于這些東西铲觉，而且計(jì)算起來仍然簡單(便宜)。
- 我們需要選擇有足夠大的內(nèi)存碉克，以允許高效的操作凌唬，而不占用過多的內(nèi)存。
- 哈希函數(shù)應(yīng)該沿著哈希表的單元格均勻地分配鍵况褪。
9.1.2 例：Hashing of Strings
9.1.3 Horner’s Rule
9.1.4 Hash Collision handling
不同的數(shù)被賦予了相同的hash地址值
-
Separate Chaining
load factor α = n/m n是要存儲(chǔ)的項(xiàng)目數(shù)测垛，m是hash表大小
Number of probes in successful search ≈ 1 + α/2.
Number of probes in unsuccessful search ≈ α
與順序搜索相比秧均，減少了一個(gè)因子m的比較次數(shù)号涯。
在動(dòng)態(tài)環(huán)境中很好锯七，當(dāng)(數(shù)量)鍵很難預(yù)測(cè)時(shí)。
可以對(duì)鏈進(jìn)行排序域蜗，也可以在訪問時(shí)將記錄“拉到前面”。
刪除很容易霉祸。
然而袱蜡，單獨(dú)鏈接使用額外的存儲(chǔ)空間的鏈接。 -
Open-Addressing Methods(closed hashing)
1)linear probing
17-36
2)double hashing
一個(gè)是雙重哈希半夷，使用第二個(gè)哈希函數(shù)來確定一個(gè)偏移量，用來探測(cè)一個(gè)空閑單元格巫橄。
例：26 mod 7為5茵典，h(k)=5,s(k)=5-(26 mod 5)=4,所以移動(dòng)4格到索引2位置。這里選擇mod5是因?yàn)?是小于7的第一個(gè)質(zhì)數(shù)彩倚。
9.1.5 Rabin-Karp String Search
是一種利用對(duì)比子串與pattern是否具有相同hash值，然后brute-force(對(duì)比兩個(gè)字符串的每個(gè)字母都一樣帆离，防止不字符串相同hash值的情況出現(xiàn))的方法结澄，每次后移一位
Hash 總結(jié)
1.hash表的大小m應(yīng)該是一個(gè)質(zhì)數(shù)麻献，double hashing在偏移時(shí)總能找到一個(gè)空位
2.load factor α = n/m
3.Separate Chaining：成功1 + α/2，不成功α勉吻，刪除容易，需要額外的鏈表
4.linear probing: 成功0.5+1/2(1+α)，不成功 0.5+1/2(1+α)^2,空間高效煮盼，α不能大于0.9带污，不能刪除
5.rehash是當(dāng)α>=0.9時(shí)，分配一個(gè)更大的hash表重新計(jì)算哈希地址
6.Rabin-Karp String Search是一種利用對(duì)比子串與pattern是否具有相同hash值刮刑，然后brute-force的方法
7.當(dāng)需要遍歷時(shí)，不能使用hash
8.除非使用Separate Chaining雷绢，不然不能刪除
9.數(shù)據(jù)量難預(yù)測(cè)時(shí)般卑，hash不合適因?yàn)閞ehash昂貴搂橙。
9.2 Dynamic Programming
子問題與母問題是遞歸關(guān)系
這種 bottom-up(table-filling)方法使用表數(shù)據(jù) tabulated results澎怒，而不是覆蓋上次數(shù)據(jù)复旬，因此整個(gè)表都需要保留
An optimal solution to a problem is composed of optimal solutions to its subproblems一個(gè)問題的最優(yōu)解是由它的子問題的最優(yōu)解組成的
9.2.1 例1 The Coin-Row Problem
recurrence relation：
時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：需要保留之前數(shù)據(jù)O(n)踪宠，不需要O(1)
9.2.2 例2 The Knapsack Problem
recurrence relation：
時(shí)間復(fù)雜度/空間復(fù)雜度：Θ (nW) .
