模型：将插入n个对象看作n个独立试验的序列。每个试验的结果是(1,2,,k)中的一个值。假设：每个实验的结果是任意一个允许值的概率是一样的。(uniformlydistributed)Inhashing n items intoahashtableofsizektheexpectednumberofitemsthathashtoanyone location isn/kα:loadingfactor（负载因子）
模型: 将插入n个对象看作n个独立试验的 序列。每个试验的结果是{1,2,.,k} 中的一个值。 假设：每个实验的结果是任意一个允许值 的概率是一样的。 (uniformly distributed) : loading factor(负载因子)
现在考虑特定单元为空的概率同样的independent trials process，可以根据需要指定不同的outcomes:口k个不同的outcomes：单元1,2....,k口2个outcomes：单元i.非单元问题4：问题4：插入n个对象后，单插入n个对象后，空单元仍然是空的，概元的期望是多少？为率是多少？什么？-(1 - 1/ k)
现在考虑特定单元为空的概率 ◼ 同样的independent trials process，可以根据 需要指定不同的outcomes: ❑ k个不同的outcomes: 单元1,2,.,k ❑ 2个outcomes: 单元i, 非单元i
一个概率悸论假设有n个存储单元，在插入n个对象后·第i个单元已放入对象数期望值是：n1换句话说，没有空的单元（？）n·整个存储区内空单元的期望数是n==~ 0.368nne问题5：你能解释这个‘悸论”吗？
一个概率悖论 假设有n个存储单元，在插入n个对象后 • 第i个单元已放入对象数期望值是： • 整个存储区内空单元的期望数是： = 1 n n n e n n n n 0.368 1 1 = − 换句话说，没有空的单元（？）
冲突：可能性有多大？在k个单元的存储区内插入n个对象：E(collisions)=n-E(occupiedlocations)=n-k+E(emptylocations)In hashing n items into a hashtablewithk locations,the expected numberofcollisionsisn-k+k(l-1/k）找一点感觉：假如在100个单元的存储区内插入100个对象，发生的碰撞数的期望值就是大约37次
冲突: 可能性有多大？ 在k个单元的存储区内插入n个对象： 找一点感觉： 假如在100个单元的存储区内插入100个对象， 发生的碰撞数的期望值就是大约37次
没有空单元：需要插入多少对象？先考虑一个“子问题”：使得被占单元数从达到i-1增加到达到i，需要插入多少对象（期望）？E(X)=1,E(X2)=k/(k-I), .In general,wehave that X;counts the number of trials until success in anindependenttrialsprocesswithprobabilityofsuccess(k-i+D/k,andthustheexpectednumberofstepsuntilthefirstsuccessisk/(k-i+),whichisthe expectedvalueofXikkk1ZE(X)=E(X)=Z=k水L7一i+1k-j+ii+k-j+1=1=i=lj=1给你一点感觉：O(klogk)当k=10000，这个值大约是98000
没有空单元：需要插入多少对象？ 先考虑一个“子问题”：使得被占单元数从达到 i-1 增加到达 到 i, 需要插入多少对象（期望）？ , , . 给你一点感觉： 当k=10000, 这个值大约是98000