Tag Archives: 哈希表

数据结构重读 - 哈希表

无论是折半查找、二叉排序树查找还是B树,性能都依赖于查找中的比较次数。

一种理想情况是不经过任何比较,一次直接定位索要查找的记录,即:若数据结构中存在关键字和K相等,则其必定在f(K)的存储位置上,我们称这个对应关系f为哈希函数

冲突(Collision):对不同的关键字,可能得到同一哈希地址,即存在key1!=key2,但f(key1)=f(key2)。此时称为冲突或碰撞。

由于在实际应用中,哈希函数都是压缩函数,所以冲突只能尽可能的减少,很难完全避免。

哈希表:根据[......]

继续阅读