|
散列文件的组织方式 散列文件是利用散列存储方式组织的文件亦称直接存取文件即根据文件中关键字的特点设计一个散列函数和处理沖突的方 法将记录散列到存储设备上 散列表与散列文件比较 基桶和溢出桶 在散列文件的存储单位叫桶(Bucket)假如一个桶能存放m个记录则当桶中已有m个同义词的记录时存放第m+个同义词会发 生溢出需要将第m+个同义词存放到另一个桶中通常称此桶为溢出桶相对地称前m个同义词存放的桶为基桶 注意 ① 溢出桶和基桶大小相同相互之间用指针相链接 ② 当在基桶中没有找到待查记录时就沿着指针到所指溢出桶中进行查找因此希望同一散列地址的溢出桶和基桶在磁盘上 的物理位置不要相距太远最好在同一柱面上 【例】某一文件有个记录其关键字分别为桶的 容量m=桶数b=用除余法作散列函数H(key)=key%由此得到的散列文件如下图所示 散列文件的查找操作 在散列文件中查找的过程 () 根据给定值求出散列桶地址 () 将基桶的记录读人内存进行顺序查找 () 若找到关键字等于给定值的记录则检索成功;否则读人溢出桶的记录继续进行查找 散列文件的删除操作 在散列文件中删去一个记录仅需对被删记录作删除标记即可 散列文件的特点 散列文件的优点 () 文件随机存放记录不需进行排序 () 插入删除方便 () 存取速度快;不需要索引区节省存储空间 散列文件的缺点 () 不能进行顺序存取只能按关键字随机存取 () 询问方式限于简单询问 () 在经过多次插入删除后可能造成文件结构不合理需要重新组织文件 |
