散列算法简介

2017-12-16 12:16

在阅读 lua 源码的过程中,知道了短字符串的内部化是用开散列实现的哈希表,而在 lua表中的哈希部分,则是使用闭散列方法。
其中开散列和闭散列都是哈希表的实现方式,
两者的特点分别是:

  • 开散列表:运用单链表存储方式,不产生堆积现象,但因为附加了指针域而增加了空间开销。
  • 闭散列表:运用顺序表存储,存储效率较高,但容易产生堆积,查找不易实现,需要用到二次再查找。
  • 溢出表:开、闭散列的结合运用,第一个顺序表存放类似指针域,第二个则存放溢出。

而关于开散列和闭散列等的具体算法表述就详见原文吧。

原文地址详见: http://blog.csdn.net/u014613043/article/details/50726630


标签:programming

点击加载Disqus评论
Creative Commons © 2013 — 2018 xiao_cang | Theme based on fzheng.me & NexT | Hosted by Netlify