动态hash 思想 本文将介绍三种动态hash 方法。 散列是一个非常有用的、非常基础的数据结构，在数据的查找方面尤其重要，应用的非常广泛。然而，任何事物都有两面性，散列也存在缺点，即数据的局部集中性会使散列的性能急剧下降，且越集中，性能越低。 数据集中，即搜索键在通过 hash 函数运算后，得到同一个结果，指向同一个桶，这时便产生了数据冲突。 通常解决数据冲突的方法有：拉链法(open hashing)和开地址法(open addressing)。拉链法我们用的非常多，即存在冲突时，简单的将元素链在当前桶的最后元素的尾部。开放地址法有线性探测再散列、二次线性探测再散列、再hash 等方法。 以上介绍的解决冲突的方法，存在一个前提：hash 表(又称散列表)的桶的数目保持不变，即 hash 表在初始化时指定一个数，以后在使用的过程中，只允许在其中添加、删除、查找元素等操作，而不允许改变桶的数目。 在实际的应用中，当 hash 表较小，元素个数不多时，采用以上方法完全可以应付。但是，一旦元素较多，或数据存在一定的偏斜性(数据集中分布在某个桶上)时，以上方法不足以解决这一问题。我们引入一种称之为动态散列的方法：在 hash 表的元素增长的同时，动态的调整 hash 桶的数目。 动态hash 不需要对 hash 表中所有元素进行再次插入操作(重组)，而是在原来基础上，进行动态的桶扩展。有多种方法可以实现：多 hash 表、可扩展的动态散列和线性散列，下面分别介绍之，方法由简单到复杂。 多 hash 表：顾名思义，即采用多个hash 表的方式扩展原 hash 表。这种方式不复杂，且理解起来也较简单，是三者中最简单的一种。 通常，当一个hash 表冲突较多时，需要考虑采用动态hash 方式，来减小后续操作继续在该桶上的冲突，减轻该桶负担，最简单且最容易想到的就是采用多hash 表的方式。如下图，有一个简单的hash 结构： 简单起见，假定(1)hash 函数采用模 5，即 hash(i)=i%5；(2)每个桶中最多只可放 4 个元素。 在以上基础上，向 hash 表中插入 5，由于桶 a 存在空闲，直接存入。接着向 0 6 1 2 7 8 13 18 23 9 4 a 桶 b 桶 d 桶 e 桶 c 桶 Hash 表个数 n 1 图：多 hash 表初始状态 hash 表插入值3，由于d 桶中已满，无空闲位置，此时在建立一个hash 表，结果如下图 通过图示，一目了然，原来的一个hash 表，变为现在的两个hash 表。如需要，该“分裂”可继续进行。 需要...
