当前位置:首页 > 嵌入式 > 嵌入式软件
[导读]哈希表(Hashtable)又称为“散列”,Hashtable是会根据索引键的哈希程序代码组织成的索引键(Key)和值(Value)配对的集合。Hashtable 对象是由包含集合中元素的哈希桶(Bucket)所组成的。而Bucket是Hashtable内元素的虚拟子群组,可以让大部分集合中的搜寻和获取工作更容易、更快速。

哈希表(Hashtable)又称为“散列”,Hashtable是会根据索引键的哈希程序代码组织成的索引键(Key)和值(Value)配对的集合。Hashtable 对象是由包含集合中元素的哈希桶(Bucket)所组成的。而Bucket是Hashtable内元素的虚拟子群组,可以让大部分集合中的搜寻和获取工作更容易、更快速。

哈希函数(Hash Function)为根据索引键来返回数值哈希程序代码的算法。索引键(Key)是被存储对象的某些属性值(Value)。当对象加入至 Hashtable时,它存储在与对象哈希程序代码相符的哈希程序代码相关的Bucket中。当在Hashtable内搜寻值时,哈希程序代码会为该值产生,并且会搜寻与该哈希程序代码相关的Bucket。例如,student和teacher会放在不同的Bucket中,而dog和god会放在相同的 Bucket中。所以当索引键是唯一从Hashtable获取元素的性能时表现会较好。Hash的四大优点如下所示。

· 事先不需要排序。

· 搜寻速度与数据多少无关。

· 数字签名的密码技术保密性(Security)高。

· 可做数据压缩(Data Compression),以节省空间。

Linux内核里的哈希表应用非常广泛,PHP内核里大部分语言特性也是基于哈希表实现的。为什么哈希表能这么神通广大?哈希表能够实现高效的数据存储和查找,而存储和查找是编程中应用最广泛的两个操作。

Linux内核里的哈希表

读过Linux内核源码的人可能都会发现,其中并没有太多复杂的数据结构,作为基础数据结构的双向链表(list)和基于list实现的hash表占据了绝大部分数据结构。内核为什么会大量使用这两种数据结构呢?围绕这个问题(主要是hash表),我将以自己的理解揣摩一下其意图。

首先,这两种数据结构都十分简单,简单包括理解起来简单和使用起来简单两方面内容。这也意味着代码的可读性和可维护性都比其他复杂的数据结构要好,出现bug的风险也较低。从哲学上来讲,这也符合K.I.S.S.条款。

其次,内核是一个比较讲究性能的软件,为了程序设计和维护的简单性而失掉性能,这究竟是不是算得不偿失呢?我们是不是应该将天平更加偏向于性能?已经记不起是在哪里听说过,很多商业的路由软件都是基于二叉树的数据结构来存储路由项,以求得其路由查找的时间复杂度为log(n),并且他批评Linux的路由项组织为hash表,致使性能不佳,不适合商业。确实有一定道理,可仔细分析,hash表的性能真的比二叉树差么?二叉树的插入和删除某一项的时间复杂度都为log(n);hash表插入和删除的时间复杂度最好为O(1),最差为O(n),如果选取的表项(m)足够多,且hash函数足够好的话,其时间复杂度为O(n/m)(当m<=n时)。当m > n / log(n)的时候,hash表的平均表现就比二叉树要好;且当m>=n时,其时间复杂度趋近于O(1)。m的值可以做成可调整的,这也正显示了内核的可定制性。不过,不要盲目乐观,这一切都是以一个足够好的hash函数为前期的。

hash函数的优劣

如何判定一个hash函数的好坏呢?

hash的中文意思是“散列”,可解释为:分散排列。一个好的hash函数应该做到对所有元素平均分散排列,尽量避免或者降低他们之间的冲突(Collision)。有必要再次提醒大家的是,hash函数的选择必须慎重,如果不幸所有的元素之间都产生了冲突,那么hash表将退化为链表,其性能会大打折扣,时间复杂度迅速降为O(n),绝对不要存在任何侥幸心理,因为那是相当危险的。历史上就出现过利用Linux内核hash函数的漏洞,成功构造出大量使hash表发生碰撞的元素,导致系统被DoS,所以目前内核的大部分hash函数都有一个随机数作为参数进行掺杂,以使其最后的值不能或者是不易被预测。这又对 hash函数提出了第二点安全方面的要求:hash函数最好是单向的,并且要用随机数进行掺杂。提到单向,你也许会想到单向散列函数md4和md5,很不幸地告诉你,他们是不适合的,因为hash函数需要有相当好的性能。

一筹莫展了吧?谁叫你又想闭门造车了!还是看看前辈们是如何做的,充分发扬拿来主义的精神,我又称这种做法为“不战而屈人之兵”,这难道不是兵家之上上策么?Linux内核里面用的jhash是一个久经考验,并被实践证明经得起考验的hash函数,可以CPMS(Copy Paste Modify Save)之。Jhash的作者Bob Jenkins在其网站上还公布了诸如针对能预知的数据进行hash的hash函数--完美(perfect)hash函数等一系列其他hash函数,看客们可以选择之,如果有兴趣继续钻研,也可以踏在他们的肩膀上。

什么是bucket

bucket的英文解释:

Hash table lookup operations are often O(n/m) (where n is the number of objects in the table and m is the number of buckets), which is close to O(1), especially when the hash function has spread the hashed objects evenly through the hash table, and there are more hash buckets than objects to be stored.

可以这样理解:

一个HASH的结果所对应的地址可存放两个BUCKET。可解决HASH冲突。

· 要存数据时,第一次HASH到这里,在第一个BUCKET存放一个数据。

· 要存数据时,当第二次因某些原因HASH到这里时,在第二个BUCKET存放另一个数据。

一个由5个buckets组成的哈希表,里面有7个元素:

linux的hash函数hash_long等,用了golden ratio来计算。因为桶(bits)的数量需要由hash函数和对冲突的期望来决定,那么对于hash_long这样的hash函数,我们怎么确定桶的数量呢?

一般情况下都是自己根据数据特性来考虑使用的 hash 算法,不是千篇一律咬死一个不放。

比如存放 IP 地址的 hash table,用一个 65536 的桶就很好,把 IP 的后 16bit 作为 key。这种方法绝对比 hash_long、jhash 等函数的碰撞率低。

其实就是这个界和性能的折中。我可以取我问题空间的最大值。这样肯定能保证键值分散。但是这样会浪费很多空间。然而取得太小,又影响查找效率。感觉还是要在试验中进行测试。而且个人觉得,hash比其他搜索的数据结构灵活的地方就是它的可定制性。可以根据具体情况调整,以达到最优的效果。

本站声明: 本文章由作者或相关机构授权发布,目的在于传递更多信息,并不代表本站赞同其观点,本站亦不保证或承诺内容真实性等。需要转载请联系该专栏作者,如若文章内容侵犯您的权益,请及时联系本站删除。
换一批
延伸阅读

双系统将是下述内容的主要介绍对象,通过这篇文章,小编希望大家可以对双系统的相关情况以及信息有所认识和了解,详细内容如下。

关键字: 双系统 Windows Linux

安装Linux操作系统并不复杂,下面是一个大致的步骤指南,以帮助您完成安装。1. 下载Linux发行版:首先,您需要从Linux发行版官方网站下载最新的ISO镜像文件。

关键字: Linux 操作系统 ISO镜像

计算机是由一堆硬件组成的,为了有限的控制这些硬件资源,于是就有了操作系统的产生,操作系统是软件子系统的一部分,是硬件基础上的第一层软件。

关键字: Linux 操作系统 计算机

Linux操作系统是一套免费使用和自由传播的类Unix操作系统,通常被称为GNU/Linux。它是由林纳斯·托瓦兹在1991年首次发布的,并基于POSIX和UNIX的多用户、多任务、支持多线程和多CPU的操作系统。Lin...

关键字: Linux 操作系统

所谓进程间通信就是在不同进程之间传播或交换信息,它是一组编程接口,让程序员能够协调不同的进程,使之能在一个操作系统里同时运行,并相互传递、交换信息;还可以让一个程序能够在同一时间里处理许多用户的需求。

关键字: Linux 进程通信 编程接口

串口通信作为一种最传统的通信方式,在工业自动化、通讯、控制等领域得到广泛使用。

关键字: Linux 串口通信 通讯

2023年11月16日: MikroElektronika(MIKROE) ,作为一家通过提供基于成熟标准的创新式硬软件产品来大幅缩短开发时间的嵌入式解决方案公司,今天宣布推出一款基于单线设备的软硬件开源解决方案Cli...

关键字: 嵌入式 Linux 操作系统

Linux是一种免费使用和自由传播的类Unix操作系统,其内核由林纳斯·本纳第克特·托瓦兹于1991年10月5日首次发布。它主要受到Minix和Unix思想的启发,是一个基于POSIX的多用户、多任务、支持多线程和多CP...

关键字: Linux 操作系统

本文中,小编将对嵌入式予以介绍,如果你想对它的详细情况有所认识,或者想要增进对它的了解程度,不妨请看以下内容哦。

关键字: 嵌入式 Linux

在这篇文章中,小编将为大家带来嵌入式 Linux的相关报道。如果你对本文即将要讲解的内容存在一定兴趣,不妨继续往下阅读哦。

关键字: 嵌入式 Linux
关闭
关闭