可以看出,完美散列实际中并不常见,在大多数的情形下,关键码的取值是远远大于词条的个数的,设关键码的取值为 [ 0 , R ) [0, R) [0,R), 词条的个数为 N N N,则 R > > N R...设散列表的大小为 M M M,此时,从定义域 [ 0 , R ) [0, R) [0,R)到值域 [ 0 , M ) [0, M) [0,M)的映射不可能是单射,即不可避免地会出现不同的关键码映射到散列表中的同一个位置...几个散列函数的实例
除余法(division method)
除余法的整体思路非常简单,即用关键码的值对散列表的长度 M M M取余,即 h a s h ( k e y ) = k e y m...首先,除余法得到的散列地址,依然存在一定程度的连续性,即原来相邻的关键码对应的散列地址也仍然是相邻的;其次,在除余法中关键码较小的那些词条,始终被映射到散列表的起始区段,其中关键码为零的元素,其散列地址总是零...随机试探法(pseudo-random probing)
仿照散列函数中的随机数法,在发生冲突时也可以采用随机数发生器来确定试探的位置,就是随机试探法。