http://blog.gregwym.info/tag/hashing/ http://blog.gregwym.info/cs-240-fu-xi-zong-jie-zhi-wu--hashing.html 2011-04-07T07:11:34+08:00 Direct Addressing key和地址直接对应 与Counting Sort同理 Runtime: Θ(1), Space: Θ(n) 浪费空间, 且只能用于int HashingHash Function 将key经过function运算以后, 得到对应的hash value Hash function的好坏决定于数据的性质, 不同的数据适用不同的function 好的Hash funtion, 高效, 与数据规律无关联, 依赖于key的所有部分 冲突解决方案(Collision Resolution)Basic concept: Buckets: 多个item共存 Open Addressing: 一个item对应多个位置 Load Balance: α = n/M (n: item数量, M: hash table大小) 方案一: Chaining (Buckets) 将新的item放入对应位置, 并link到原来位置所存放的item 缺点: 大量数据会导致大量重复, 效率降低 方案二: Linear Probing 如果要insert的位置非空, 则将item放入下一个位置. 重复这一条直到insert成功/回到原位置(insert失败) 某个item被delete以后, 该位置须标记为deleted, 不能再使用 缺点: 大量数据后会有明显的效率降低, deleted以后会有空间浪费, 增加M以后rehash可以解决部分问题, 但cost很高. 方案三: Double Hashing 在Linear Probing基础上增加一个与h1独立的functions h2. 如果要insert的位置非空, hash value = [原hash value + h2(k)] % M. 重复这一条直到insert成功/回到原位置(insert失败) 缺点: 与Linear Probing相同, 只是increment由1变为了h2的结果, 所以降低了第二次insert的失败概率. 方案四: Cuckoo Hasing 有两个相互独立的hash functions, h1和h2 将item insert到h1(k)中 如果原来h1(k)的位置并不为空, 将原item重新insert到与h1(k)值不同的hash value中去 如出现loop的情况, insert失败, rehash 优点: iterm只能出现在h1(k)或者h2(k)中, search效率高.继续编辑中...谁能告诉我, 咱们学Extendible Hashing了么`? 貌似没有吧...更多CS 240总结请看: http://blog.gregwym.info/tag/cs240/