键字的平方值的中间几位作为散列地址。\r具体取多少位要视实际情况而定。这种方法得到的散列地址与关键字的每位都有关系,因此使得\r散列地址分布比较均匀,适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。\r13102=1,716,100\r11102=1,232,100\r13002=1,690,000\r12102=1,464,100\r12002=1,440,000\r常见的散列函数V设计目标一一让不同关键\r字的冲突尽可能地少\r平方取中法一一取关键字的平方值的中间几位作为散列地址。\r具体取多少位要视实际情况而定。这种方法得到的散列地址与关键字的每位都有关系,因此使得\r散列地址分布比较均匀,适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。\r例:要存储整个学校的学生信息,以“身份证号”作为关键字设计散列函数\r身份证号码规则:\r前1、2位数字表示:所在省份的代码;\r第3、4位数字表示:所在城市的代码;\r第5、6位数字表示:所在区县的代码;\r第7-14位数字表示:出生年、月、日;\r第15、16位数字表示:所在地的派出所的代码;\r第17位数字表示性别:奇数表示男性,偶数表示女性;\r第18位数字是校检码。\r99999假设学生不超过十万人,可\r身份证号平方取中间5位\r常见的散列函数<设计目标一一让不同关键\r字的冲突尽可能地少\r例:要存储整个学校的学生信息,以“身份证号”作为关键字设计散列函数\r999999\r999999\r999999\r若散列表的长度为1000000000000000000(别数了,有18个03)\r则可以直接用身份证号作为散列地址,且不可能有冲突,查找时间复杂度为。⑴\r散列查找是典型的“用空间换时间”的算法,只要散列函数设计的合理,则散列表越\r长,冲突的概率越低。\r知识回顾与重要考点\r下次一定\r
全文预览
