摘要当今社会，存储设备在人们生活中越发必不可少，在日益高涨的存储需求下，拥有固定桶数的静态散列表已无法适应需要，于是产生了动态散列表。可扩充散列算法是一种基于散列函数的文件构造方法，这种文件实现了随其记录个数增减的动态变化，支持对记录的快速随机存取。64193

 本文首先分析了可扩充散列算法方面的研究背景，并阐述了传统文件存储结构所存在的主要问题，提出动态的可扩展散列方法。其次介绍了可扩充散列算法的理论基础和相关知识，重点对可扩充散列算法问题进行了探究。可扩充散列算法对溢出桶进行分裂的同时将目录项数翻倍，减少了系统开销。最后对算法进行了实现，程序测试结果表明算法正确且合理，但在算法上的可扩充性方面还需多加改进。

毕业论文关键词 可扩充散列、动态散列、哈希 

毕业设计说明书（论文）外文摘要

Title   the realization  of extendible  hashing  algorithm

Abstract In today's society, storage devices become more and more indispensable in people's lives, the static hash table with a fixed number of barrels has been unable to adapt to the needs of the growing storage, so the dynamic hash table arise. Extendible hashing algorithm, based on hash function, is a file structure method, the file realizes the dynamic changes with the number of changes of records, and to support fast random access to the records. 

This paper firstly analyzes the research background of extendible hashing algorithm, and expounds the main problems existing in the traditional file storage structure, we propose the dynamic extensible hashing method. Secondly, we introduce the theoretical basis of the extendible hash algorithm and related knowledge, mainly explore the extendible hashing algorithm. Extendible hashing algorithm split the overflow buckets and double the entries to reduce the overhead of system. Lastly the extendible hashing algorithm is implemented, the result of program tests shows that the algorithm is correct and reasonable, but in the algorithm scalability aspects still needs a lot of improvement, there still need a lot of improvement in the aspects of the algorithm's scalability .

Keywords  extendible hashing, dynamic hash, hash

目   录

1  绪论 1

1.1 研究背景 1

1.2 研究内容 1

1.3 研究目的 1

1.4 研究意义 2

1.5 开发工具简介 2

1.6 章节安排 2

1.7 本章小结 3

2 可扩充散列算法的基本知识概述 3

2.1 算法的理论基础 3

2.1.1 散列的定义 3

2.1.2 散列函数的特点 3

2.1.3 散列的构造方法 4

2.1.4 目前常见的冲突处理方法 6

2.1.5 查找及性能分析 8

2.2 算法的提出 8

2.3 算法的定义 9

2.4 算法的基本思路