Hash Table
Download as pptx, pdf0 likes943 views
Introduction to Algorithms, section11 Hash Table.
Hash Table
- 1. Introduction To Algorithms.§11. Hash Tables.2010 / 06
- 2. Why Hash Tables ?探索したい @配列
- 3. 先头にあれば… 翱(1)
- 4. 末尾にあれば… 翱(狈)
- 5. いつもO(1)ぐらいだったら嬉しいHash TableHash : 细かく切る
- 6. Key と Value の 組合せ
- 7. (Key, Value) で 表に格纳する
- 8. 同じKeyだったらどうしようHash Table ( SIZE M )同じKeyが出にくい方がいい
- 9. 出来れば高速で计算して…
- 10. F : Data -> { 0, 1, 2, … , M-1 }Hash Table ( SIZE M )Hash Function はおおまかなグループ分けをするKey:2Key:0Key:M-1Key:1DATA
- 13. M = 7 : 素数
- 14. 経験的に素数を使う方がいいらしい
- 15. 数字の総和 mod 7 を 関数に使うExample.
- 17. チェイン法/クローズドハッシュ法
- 19. チェイン法Keyが同じならチェイン(鎖)にする(78/11/4, C)(01/5/12, E)O(1)(87/2/1, B)(85/10/5, A)(68/8/4, C)O(長さ)
- 21. 一つのチェイン長は平均してn / m = α : 占有率
- 24. O( 1 + α )§11.3.1 The Division Method大前提1. 同じKeyがなかなか出ない
- 25. 大前提2. 上手くばらける
- 26. Mod: 割り算だけなので高速
- 27. (再掲)経験的に素数を使う方がいいらしい§11.3.2 The Multiplication MethodHash(k) = floor( m ( k A mod 1 ) ) , 0 < A < 1
- 28. kA mod 1 … kA – floor(kA)
- 29. A ~ (√5-1) / 2 ~ 0.6180339887§11.3.3 Universal Hash要約1：乱数とハッシュ関数族
- 31. 基本的に O(1)
- 32. リストで管理
- 34. アイデア：Keyが重複したら横にずらす§11.4 Open Addressing (Figure)(68/8/4, C)Key 5(78/11/4, C)(01/5/12, E)(87/2/1, B)(85/10/5, A)もう使ってる!
- 35. §11.4 Open Addressing (Figure)(78/11/4, C)(01/5/12, E)(87/2/1, B)(85/10/5, A)ずらす(68/8/4, C)
- 39. 関数2つ:Double Hashing, ダブルハッシュ法§11.4 Linear, Quadratic ProbingパラメータI : I回目のKey生成
- 40. Hash(data, i) = ( Hash(k) + I ) mod m
- 41. H(k,i) = (H’(k) + c1 i + c2 i*I) mod m
- 42. Mod mで表の外に飛び出ない (closed)§11.4 Double hashingハッシュ関数 H1, H2
- 43. 颈回目の生成
- 44. Hash(data, i) = ( H1(data) + i * H2(data) ) mod m§11.4 Analysis.占有率α = n / m
- 46. 基本的にα = 1 になってしまうと格纳出来ない
- 47. 1 / ( 1 – α ) だけ再生成するかも(平均で)§11.4 AnalysisM = 6 の表
- 48. α = 0.5
- 49. 1 / ( 1- α ) = 2§11.4 Analysis上手くばらけていない
- 50. 0词2なら2回以上
- 51. 3词5なら1回
- 52. 平均的に 1 / ( 1 – α)
- 54. 要约：ハッシュ関数が単射
- 56. Java:HashMap
- 59. 简単なのなら直ぐ作れます