Pre*_*gha 15
本文在MSDN上对此进行了描述:使用C#2.0对数据结构进行了广泛的检查
...称为rehasing的冲突解决技术,这是.NET Framework的Hashtable类使用的技术.在最后一节中,我们将看一下Dictionary类,它使用一种冲突解析技术作为链接.....
... Rehasing的工作原理如下:有一组哈希不同的函数,H1 ... Hn,当从哈希表中插入或检索项目时,最初使用H1哈希函数.如果这会导致碰撞,则尝试使用H2,如果需要,则转到Hn.上一节仅显示了一个哈希函数,即初始哈希函数(H1).其他散列函数与此函数非常相似,仅通过乘法因子进行区分.通常,散列函数Hk定义为:
Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1)))] % hashsize
Dictionary类与Hashtable类的区别在于多种方式.除了强类型之外,Dictionary还使用与Hashtable类不同的冲突解决策略,使用称为链接的技术.回想一下,通过探测,在发生碰撞时,尝试了桶列表中的另一个槽.(通过重新散列,重新计算散列,并尝试使用新的插槽.)但是,通过链接,可以使用辅助数据结构来保存任何冲突.具体来说,Dictionary中的每个插槽都有一个映射到该存储桶的元素数组.如果发生碰撞,碰撞元素将被添加到桶的列表中.
记住只有第一句话是我自己的:-)