大普微ic算法二面

哈希表主要考虑两个问题：1）如何设计哈希函数2）如何解决冲突hash函数计算出元素在hash表中的储存位置：locate(i)=hash(keyi)hash表用于存储元素第1节 hash函数构造方法1）直接定址法：Hash（key）=a*Key+b优点:以关键码key的某个线性函数值为散列地址,不会产生冲突。缺点: 要占用连续地址空间,空间效率低。2）除留余数法：Hash(Key)=Key % p (设表长未m，取p为小于等于m的质数)优点：节约空间缺点：会产生冲突第2节 处理冲突的方法1）开放地址法：Hi=(Hash(key)+di) % m当d为1，2，3……这个线性序列时，叫做线性探测法...