哈希表

哈希表又叫散列表


散列函数:一个把查找表中的关键字映射成该关键字对应的地址的函数。

散列表:根据关键字而直接进行访问的数据结构。他建立了关键字与存储地址之间的一种直接映射关系。

冲突:散列函数可能会把多个不同的关键字映射到同一地址下的情况。

散列函数

直接定址法

直接取关键字的某个线性函数值为散列地址。

Hash(key)=a*key +b,其中a,b为常数

方法简单,不会产生冲突,若关键字分布不连续,则会浪费空间

除留取余法

Hash(key)=key % p

假定散列表表长为m,取一个不大于m但最接近或等于m的质数p

平方取中法

这种方法取关键字的平方值的中间几位作为散列地址

适用于关键字的每位取值不均匀或均小于散列地址所需要的位数。

折叠法

将关键字分割成位数相同的几部分,然后取这几部分的叠加和作为散列地址

例如:5211252==》521+125+2=648

适用于关键字的位数多,而且关键字中的每位上数字分布大致均匀

处理冲突

开放定址法

是指可存放新表项的空闲地址既向它的同义词表项开放,又向它的非同义词表项开放。

  • 线性探测法即d=0,1,2,3,m-1,会产生堆积现象
  • 平方探测法即平方查找,缺点是不能探测到散列表上的所有单元*(至少可以探测到一般单元)
  • 再散列法即d=i*Hash2(key)
  • 伪随机法即d=伪随机序列

拉链法

把所有同义词存放在一个线性链表中,这个线性链表由地址唯一标识,即散列表中每个单元存放该链表头指针。拉链法适用于经常进行插入和删除的情况

散列表查找

查找效率取决于:散列函数、处理冲突的方法和填装因子
填装因子=表中记录数/散列表长度

本作品采用《CC 协议》,转载必须注明作者和本文链接
当它本可进取时,却故作谦卑; 在困难和容易之间,它选择了容易; 自由软弱,却把它认为是生命的坚韧; 侧身于生活的污泥中,虽不甘心,却又畏首畏尾。
《L05 电商实战》
从零开发一个电商项目,功能包括电商后台、商品 & SKU 管理、购物车、订单管理、支付宝支付、微信支付、订单退款流程、优惠券等
《L04 微信小程序从零到发布》
从小程序个人账户申请开始,带你一步步进行开发一个微信小程序,直到提交微信控制台上线发布。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!