可扩充散列算法的实现(2)

菜单

2.5 算法的需求分析 12

2.6 数据查找 12

2.7 数据插入 13

2.8 数据删除 15

2.9 本章小结 16

3 结果验证 17

3.1 测试运行 17

3.2 存在的一些问题 19

3.3 改进算法 19

3.4 本章小结 21

结论 22

致谢 24

参考文献 25

1 绪论

1.1 研究背景

现今社会，时代被计算机的革新不断推向前进。人们生活的各个角落里都随处可见计算机的影子，通讯、医疗、教育、军事、航天的发展都与计算机密不可分，除了计算机的计算控制外，更多地便是数据存储和处理！人们对计算机的使用越来越广泛，需要处理的数据量呈指数级增长。世界上每人每天都会创造出大量数据如语音，文本，视频，照片等等，Internet上的的信息量也在迅速增长。在科学研究方面，随着研究手段的进步，数据量更是达到了前所未有的程度。数据量的增长得需要存储设备的支持，而硬件的发展相对软件而言毕竟要相对缓慢，从而人们转向研究可提高存储效率的算法。由于传统的拥有固定桶数的静态散列表已经无法适应需要，于是可扩充散列算法应运而生。

它是一种动态散列方法，好处在于可动态进行桶的增长，且增长的同时，用目录项的翻倍的较小的代价换取桶数翻倍的传统做法，效率得到明显提升。而采用传统静态散列表的文件结构无论采用何种解决冲突的办法，都非常需要静态分配存储空间。如果分配的存储空间过大，会就浪费空间；如果分配的存储空间过小，当需要存放大量数据，并且都超出散列表的存储大小时，就需要重新分配、组织大的存储储空间这个过程会造成很大的时间和空间的开销。而可扩充散列算法正好可以弥补这些不足，所以倍受人们的青睐。

1.2 研究内容

学习一些动态散列算法，通过编程实现可扩充散列算法，可实现查找、插入、删除等基本功能，理解散列算法的定义、散列函数的特点、散列函数的构造方法、散列算法的冲突处理方法等，以及对散列算法扩充后可扩充散列算法的提出和发展以及基本思路和实现过程，对可扩充散列算法进行分析和实现。

1.3 研究目的

通过本课题的研究来探讨散列算法理论基础以及可扩充散列算法在文件存储等结构中应用的本质含义，充分理解和掌握散列算法和可扩充散列算法的用法特点、数据结构、基本要素以及思路和实现过程，为将来散列算法的发展和改进打下坚实的基础。论文网

1.4 研究意义

散列不仅可以用于文件组织的构建，还可以用于创建索引结构。绝大多数的数据库都会随时间而扩充增大，因为有源源不断地数据的加入。数据库采用静态散列创建索引，当数据库增加的时候，索引需要重组。重组涉及到一系列诸多问题，包括重新选择散列函数、对文件中的每条记录重新计算散列地址等等，重组文件非常耗时耗存储。可扩充散列是一种动态散列方法，它扩充了传统的散列方法，使之能够动态地满足对文件存储容量的需求，以适应数据库能增大或缩小的需要而设计的，可实现对数据记录的快速随机存取，保持高效的搜索效率。