某储备粮的“学习笔记” - cuckoo http://blog.gregwym.info/tag/cuckoo/ zh-CN Thu, 07 Apr 2011 07:11:34 +0800 Thu, 07 Apr 2011 07:11:34 +0800 CS 240复习总结之五: Hashing http://blog.gregwym.info/cs-240-fu-xi-zong-jie-zhi-wu--hashing.html http://blog.gregwym.info/cs-240-fu-xi-zong-jie-zhi-wu--hashing.html Thu, 07 Apr 2011 07:11:34 +0800 咳嗽di小鱼

Direct Addressing


  • key和地址直接对应
  • 与Counting Sort同理
  • Runtime: Θ(1), Space: Θ(n)
  • 浪费空间, 且只能用于int

Hashing


Hash 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
  1. 有两个相互独立的hash functions, h1和h2
  2. 将item insert到h1(k)中
  3. 如果原来h1(k)的位置并不为空, 将原item重新insert到与h1(k)值不同的hash value中去
  4. 如出现loop的情况, insert失败, rehash

  • 优点: iterm只能出现在h1(k)或者h2(k)中, search效率高.

继续编辑中...
谁能告诉我, 咱们学Extendible Hashing了么`? 貌似没有吧...

更多CS 240总结请看: http://blog.gregwym.info/tag/cs240/

]]>
3 http://blog.gregwym.info/cs-240-fu-xi-zong-jie-zhi-wu--hashing.html#comments http://blog.gregwym.info/feed/cs-240-fu-xi-zong-jie-zhi-wu--hashing.html