01
知识框架
02
知识点详解
1
散列表的相关概念
①什么是散列表和散列函数?
是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做
散列函数,记为 Hash(key) = Addr 这里的地址是数组下标、索引或内存地址等)。 存放记录的数组叫做
散列表。
②什么是同义词和冲突?
散列函数可能会把两个或两个以上的不同关键字映射到同一地址,称这种情况为冲突,这些发生碰撞的不同关键字称为
同义词。一方面,设计得好的散列函数应尽量减少这样的冲突;另一方面,由于这样的冲突总是不可避免的,所以还要设计好处理冲突的方法。
2
散列函数
下面介绍几种常见的散列函数:
①直接定址法
取关键词的某个线性函数值为散列地址,即H(key) = a × key + b (a、b为常数) 适用情况:它适合关键字的分布基本连续的情况,若关键字分布不连续,空位较多,则会造成存储空间的浪费。
②除留余数法
散列函数为:H(key) = key mod p(假定散列表的长度为m,取一个不大于m但是接近于m的质数p) 它是一种最简单、最常见的方法。
③数字分析法
分析数字关键字在各位上的变化情况,取比较随机的位作为散列地址。 适用情况:这种方法适合于己知的关键字集合,若更换了关键字,需要重新构造新的散列函数。
④平方取中法
这种方法取关键字的平方值的中间几位作为散列地址。具体取多少位要视实际情况而定,这种方法得到的散列地址与关键字的每位都有关系。因此使得散列地址分布比较均匀。 适用情况:适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。
3