计算机等级考试知识点散列技术和桶溢出思维导图

1、 散列是一种快速查找技术，它利用定义在文件记录上的查找码，通过计算一个散列函数，以散列函数值作为记录的物理地址，实现对文件记录直接快速访问

2、 首先指定文件记录的一个域作为查找码(散列域)，然后定义一个查找码上的函数(散列函数)，函数的输入为查找码值，输出为物理地址;

3、 一般使用桶作为基本的存储单位，一个桶可存放多个文件记录，物理地址可以是记录所在的桶号，散列函数的输出可以是桶号;

散列方法依赖于好的散列函数，它应该尽可能均匀地将查找码分布到各个桶中，具体要满足如下两个条件

1、 产生桶溢出的两个原因：

　2、 设计散列函数时，应根据文件大小决定物理空间，一般应有20%余量，再设计合适的桶数目和桶大小，尽可能留有一些空闲桶，降低桶溢出的可能性;

3、 桶溢出的现象是难免的，需要DBS采用相应的桶溢出处理机制;

4、 散列方法的缺点