摘要: 哈希结构

C++博客 Alex-Lee 2009-10-21

哈希结构在处理大量数据时具有很好的优势，在插入，查询，删除等操作上具有常量的时间复杂度O(1)。使用范围是数据集具有自然数上的关键字域（不是自然数也需要能够转为自然数域），通过哈希函数将关键字映射到寻址数组的槽。由于关键字域U[0...n]与寻址数组[0...m]中，总是n>m，也就是说，总有多个关键字对应一个槽。这个碰撞就需要通过一些方法改变。可以通过拉链法（链表法）和开放地址法。对于拉链法中，链表不能太长，否则影响速度，最好控制在10个元素之内，这样就要去寻址数组长度m>= n/10，这样就会多消耗些空间。为了让每个链表长度基本一致，就需要  阅读全文