计算机问题求解一论题2-13 ashing方法 2014年06月10日
计算机问题求解 – 论题2-13 - Hashing方法 2014年06月10日
Hashing 0 U (universe of keys) h(k1) k h(k K ka (actual h依)=k) keys) h(ka) m-1 间题1： 所谓“Hashing”方法是 用来解决什么间题的？
Hashing
Hashing:the Idea Very large,but only a In feasible size small part is used in an application at a certain E[0] ·Index distribution time 耳1] Collision handling : Hash Function Key Space E[k] H(x)=k Value of a A calculated specific key array index for E[m-1] the key
Hashing: the Idea Key Space Hash Function E[0] E[1] E[m-1] Value of a specific key A calculated array index for the key Very large, but only a small part is used in an application at a certain time In feasible size • Index distribution • Collision handling E[k] x H(x)=k
间题2： Co1 ision是什么意思？ 它是如何产生的？
间题3： 假设分配的存储区为k个单元， 插入个键值。对于某个特定位 置，落到该位置的对象的期望值 是多少？为什么？ 顺便问一下，只插入2个键值， 发生碰撞的概率是多大？
顺便问一下，只插入2个键值， 发生碰撞的概率是多大？