Hashing 0 U (universe of keys) h(k:) h依 (actual h民)=Nk keys) h使) m-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] time ·Index distribution E[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
间题3: 假设分配的存储区为k个单元, 插入n个键值。对于某个特定位 置,落到该位置的对象的期望值 是多少?为什么? 顺便问一下,只插入2个键值, 发生碰撞的概率是多大?
顺便问一下,只插入2个键值, 发生碰撞的概率是多大?
模型:将插入n个对象看作n个独立试验的 序列。每个试验的结果是{1,2,.…,k 中的一个值。 假设:每个实验的结果是任意一个允许值 的概率是一样的。 (uniformly distributed) In hashing n items into a hash table of size the expected number of items that hash to any one location is n/k c.loading factor(负载因子))
模型: 将插入n个对象看作n个独立试验的 序列。每个试验的结果是{1,2,…,k} 中的一个值。 假设:每个实验的结果是任意一个允许值 的概率是一样的。 (uniformly distributed) : loading factor(负载因子)
现在考虑特定单元为空的概率 同样的independent trials process,可以根据 需要指定不同的outcomes: 口k个不同的outcomes:单元1,2,..,k 2个outcomes:单元i,非单元i 问题4: 问题4: 插入n个对象后,单 插入n个对象后,空单 元仍然是空的,概 元的期望是多少?为 率是多少? 什么? -(1-1/k
现在考虑特定单元为空的概率 ◼ 同样的independent trials process,可以根据 需要指定不同的outcomes: ❑ k个不同的outcomes: 单元1,2,…,k ❑ 2个outcomes: 单元i, 非单元i
一个概率悖论 假设有n个存储单元,在插入n个对象后 ·第i个单元已放入对象数期望值是: 2 =1 换句话说,没有空的单元(?) n ·整个存储区内空单元的期望数是: 1--06m e 问题5: 你能解释这个悖论”吗?
一个概率悖论 假设有n个存储单元,在插入n个对象后 • 第i个单元已放入对象数期望值是: • 整个存储区内空单元的期望数是: = 1 n n n e n n n n 0.368 1 1 = − 换句话说,没有空的单元(?)
冲突:可能性有多大? 在k个单元的存储区内插入个对象: E(collisions)=n-E(occupied locations) =n-+E(empty locations). In hashing n items into a hash table with k locations,the expected number of collisions is n-k+k(1-1/k)". 找一点感觉: 假如在100个单元的存储区内插入100个对象, 发生的碰撞数的期望值就是大约37次
冲突: 可能性有多大? 在k个单元的存储区内插入n个对象: 找一点感觉: 假如在100个单元的存储区内插入100个对象, 发生的碰撞数的期望值就是大约37次
没有空单元:需要插入多少对象? 先考虑一个“子问题”:使得被占单元数从达到-1增加到达 到i,需要插入多少对象(期望)? E(X1)=1,E(X2)=k/(k-1),. In general,we have that Xi counts the number of trials until success in an independent trials process with probability of success(k-i+1)/k,and thus, the expected number of steps until the first success is k/(k-i+1),which is the expected value of Xi. E(X)= 2)店-2n=t之= Θ(log) 给你一点感觉: 当k=10000,这个值大约是98000
没有空单元:需要插入多少对象? 先考虑一个“子问题”:使得被占单元数从达到 i-1 增加到达 到 i, 需要插入多少对象(期望)? , , …… 给你一点感觉: 当k=10000, 这个值大约是98000