路径寻找问题及哈希表

这一篇Blog着重写的应该是Hash吧,路径寻找问题在应用中会稍微提到一点。

定义

  • 若关键字为k,则其值存放在f(k) 的存储位置上。由此,不需比较便可直接取得所查记录。称这个对应关系 f为散列函数,按这个思想建立的表为散列表
  • 对不同的关键字可能得到同一散列地址,即k1 ≠ k2 ,而 f(k1) = f(k2),这种现象称为冲突。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述,根据散列函数 f(k)和处理冲突的方法将一组关键字映射到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“像”作为记录在表中的存储位置,这种表便称为散列表,这一映射过程称为散列造表或散列,所得的存储位置称散列地址
  • 若对于关键字集合中的任一个关键字,经散列函数映象到地址集合中任何一个地址的概率是相等的,则称此类散列函数为均匀散列函数,这就是使关键字经过散列函数得到一个“随机的地址”,从而减少冲突。

Read More

Share