随着计算机网络技术的迅猛发展，以及计算机硬件性能的大幅度提高，新的市场需求应运而生。特别是有关网络方面的需求更是层出不穷，从事宽带接入系统开发的一家公司向我们提出需要一套宽带接入系统中IP地址快速定位的软件，因为他们自己开发的基于二分查找的IP地址定位算法已经无法满足要求。于是我们针对IP地址快速定位问题开始研究更高效的查找算法。无独有偶，另一家公司得知我们在研究高效查找算法，也向我们提出了类似的需求。这些给我们的研究提供了重要的背景和动力。这些需求，抽象起来，实际上就是要求设计一种结构，高效地支持动态ADT字典。动态ADT字典传统的实现方式，主要分两类，一类支持基于元素关键字值比较的结构，另一类支持基于散列的结构。考虑到IP地址绝大多数操作是查找，相对而言，插入和删除操作的频度十分低，第一类实现方式不适用。第二类实现方式以查找效率高见长。我们分别试用了传统的开散列、闭散列、完美散列和可扩展散列等，发现运用单一的传统散列技术还满足不了实用的需求，但它们都有支持快速查找的潜力，值得作深入的研究，有望通过对它们的改进，综合各自的优势，形成一种复合结构，满足实用的需求。在进一步研读有关Hash技术文献的基础上，我们一方面注意到Hash本身的局部化功能，即把字典元素按关键字的Hash值“平均地”划分成一些互不冲突的等价类，使冲突只在规模与全集比相对小得多的同一个等价类中发生；另一方面注意到传统可扩展Hash有可改进达到快速地对同一等价类中的元素进行再散列的潜力。照此设想，把这两方面结合起来，优势互补，将会有所突破。于是，我们对传统的可扩展Hash作了深入的研究，找到了对它进行改进的窍门，然后把改进版本与通常的Hash成功地构成一个两层Hash架构，支持动态ADT字典。实验的结果与我们的定性分析一致，效果显著。本文的创新之处在于：1.针对传统可扩展Hash存在的弊端，在分析了它的逐步扩展机制之后，发现扩展过程从初态到终态不必按部就班，可以一步到位。并且建立起了扩展过程的终态与初态的状态参数之间的直接数学关系式，使传统可扩展Hash的自适应可扩展过程大为缩短，显著地改进了算法的时间效率。2.提出两层的Hash构架，支持动态ADT字典。第一层采用通常的Hash，将字典元素的冲突局部化；第二层采用上述改进的可扩展Hash，对冲突的字典元素根据冲突的状况自适应地作进一步散列。与传统的开散列相比，这种两层的Hash构架所支持的动态ADT字典的平均时间效率提高了2倍。