加载中...

  散列表的相关概念和内容  

散列表Hash table,也叫哈希表),是根据键(Key)而直接访问在内存储存位置的数据结构。

​ 也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。

​ 这个映射函数称做散列函数,存放记录的数组称做散列表

基本概念

  • 关键字为$k$的值存储在$f(k)$的存储位置中,称映射$f$为散列函数,按照这个思想建立的表称为散列表
  • 对不同的关键字可能得到同一散列地址,即$k_1 \neq k_2$,而$f(k_1) = f(k_2)$,这种现象称为冲突(Collision)。具有相同函数值的关键字对该散列函数来说称做同义词
  • 若对于关键字集合中的任一个关键字,经散列函数映象到地址集合中任何一个地址的概率是相等的,则称此类散列函数为均匀散列函数,这就使关键字经过散列函数得到一个“随机的地址”,从而减少冲突。

构造散列函数的方法

​ 若采用求余的方法,采用质数可以在一定程度上解决冲突问题。

处理冲突的方法

  • 开放定址法
  • 避免聚集:
    • 单独链表法
    • 再散列

Reference