哈希游戏- 哈希游戏平台- 哈希游戏官方网站当数据规模接近哈希表上界或者下界的时候，哈希表完全不能够体现高效的特点，甚至还不如一般算法。但是如果规模在中央，它高效的特点可以充分体现。试验表明当元素充满哈希表的 90% 的时候，效率就已经开始明显下降。这就给了我们提示：如果确定使用哈希表，应该尽量使数组开大，但对最太大的数组进行操作也比较费时间，需要找到一个平衡点。通常使它的容量至少是题目最大需求的 120% ，效果比较好（这个仅仅是经验，没有严格证明）。

　　哈希函数的设计很重要。一个不好的哈希函数，就是指造成很多冲突的情况，从前面的例子已经可以看出来，解决冲突会浪费掉大量时间，因此我们的目标 就是尽力避免冲突。前面提到，在使用“除余法”的时候，h(k)=k mod p ，p 最好是一个大素数。这就是为了尽力避免冲突。为什么呢？假设 p=1000 ，则哈希的标准实际上就变成了按照末三位数分类，这样最多1000类，冲突会很多。一般地说，如果 p 的约数越多，那么冲突的几率就越大。

　　简单的证明：假设 p 是一个有较多约数的数，同时在数据中存在 q 满足 gcd(p,q)=d 1 ，即有 p=a*d,q=b*d,则有 q mod p= q –P*[q div p] =q –P*[b div a] . ① 其中 [b div a ] 的取值范围是不会超过 [0，b] 的正整数。也就是说， [b div a] 的值只有 b+1 种可能，而 p 是一个预先确定的数。因此 ① 式的值就只有 b+1 种可能了。这样，虽然mod 运算之后的余数仍然在 [0，p-1] 内，但是它的取值仅限于 ① 可能取到的那些值。也就是说余数的分布变得不均匀了。容易看出， p 的约数越多，发生这种余数分布不均匀的情况就越频繁，冲突的几率越高。而素数的约数是最少的，因此我们选用大素数。记住“素数是我们的得力助手”。

　　另一方面，一味的追求低冲突率也不好。理论上，是可以设计出一个几乎完美，几乎没有冲突的函数的。然而，这样做显然不值得，因为这样的函数设计 很浪费时间而且编码一定很复杂，与其花费这么大的精力去设计函数，还不如用一个虽然冲突多一些但是编码简单的函数。因此，函数还需要易于编码，即易于实 现。综上所述，设计一个好的哈希函数是很关键的。而“好”的标准，就是较低的冲突率和易于实现。另外，使用哈希表并不是记住了前面的基本操作就能以不变应万变的。有的时候，需要按照题目的要求对哈希表的结构作一些改进。往往一些简单的改进就可以带来巨大的方便。

　　d-left hashing中的d是多个的意思，我们先简化这个问题，看一看2-left hashing。2-left hashing指的是将一个哈希表分成长度相等的两半，分别叫做T1和T2，给T1和T2分别配备一个哈希函数，h1和h2。在存储一个新的key时，同时用两个哈希函数进行计算，得出两个地址h1[key]和h2[key]。这时需要检查T1中的h1[key]位置和T2中的h2[key]位置，哪一个位置已经存储的（有碰撞的）key比较多，然后将新key存储在负载少的位置。如果两边一样多，比如两个位置都为空或者都存储了一个key，就把新key 存储在左边的T1子表中，2-left也由此而来。在查找一个key时，必须进行两次hash，同时查找两个位置。