数据结构与算法-英文课件2016-Chap9+searching.ppt

an element a key , no synonyms * prime number（质数） * We also decide that we want to provide data space for up to 300 employees. The first prime number greater than 300 is 307. We therefore choose 307 as our list (array) size, which gives us a list with addresses that range from 0 through 306. To demonstrate, let’s hash Bryan Devaux’s employee number, 121267. * 真正意义上的随机数（或者随机事件）在某次产生过程中是按照实验过程中表现的分布概率随机产生的，其结果是不可预测的，是不可见的。而计算机中的随机函数是按照一定算法模拟产生的，其结果是确定的，是可见的。我们可以这样认为这个可预见的结果其出现的概率是100%。所以用计算机随机函数所产生的“随机数”并不随机，是伪随机数。　 随机数是由随机种子根据一定的计算方法计算出来的数值。 * There must be some empty elements in a list at all times. As a rule of thumb : * 在处理冲突过程中发生了两个第一个哈希地址不同的纪录争夺同一个哈希地址的现象叫“二次聚集”，即在处理同义词过程中又添加了非同义词的冲突。 * prime area (contains all of the home addresses ) * The new address is the modulo of the quadratic sum * the coefficient(a=3)is small to fit our example It is better to use a large prime number for a, such as 1663 * Key offset (补偿，偏移) * Table shows that three keys that collide at address 001, Next two collision probe addresses * any of the collision resolution methods may be used. * Quadratic collision resolution increments limitation If a list size is 100, only 59 of the probes will generate unique addresses, the other 41 locations in the list will not be probed The solution to this problem is to use a list size that is a prime number. If do this, at least half of the list is reachable Pseudorandom collision resolution Uses a pseudorandom number to resolve the collision Using the collision address as a factor in the random number calculation, such as: New address = 3 * collision address + 5 379452 Marry Dodd 070918 Sarah Trapp 121267 Bryan Devaux 378845 John Carver 166702 Harry eagle … … 160252 Tuan Ngo 045128 Shouli Feldman [000] [001] [002] [003] [004] [005] [006] [007] [008] [305] [306] hash 070918 166702 1 1 First insert: No collision second insert: collision Pseudorandom probe Pseudorandom Y = 3x+5 Pseudorandom collision resolution Y=(ax+c) modulo l