计算机问题求解一论题2-12·Hashing方法2018年05月23日
计算机问题求解 – 论题2-12 - Hashing方法 2018年05月23日
Hashing70u(universeofkeys)h(k2)h(ks)KKh(=Mk)(actmalkeys)Kh(kg)m-1问题1：所谓“Hashing"方法是用来解决什么问题的？
Hashing
Hashing: the IdeaVery large,but only aInfeasiblesizesmallpartisusedinanapplication at a certainE[0]timeIndexdistributionE[1].Collision handling......HashFunctionKeySpaceE[K]H(x)=k.......Value of aspecifickeyAcalculatedarrayindex forthe keyE[m-1]
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：Collision是什么意思？它是如何产生的？
问题3：假设分配的存储区为k个单元插入n个键值。对于某个特定位置，落到该位置的对象的期望值是多少？为什么？顺便问一下，只插入2个键值，发生碰撞的概率是多大？
顺便问一下，只插入2个键值， 发生碰撞的概率是多大？