当前位置 博文首页 > Jqcode:关于哈希表必须了解的一些知识
首先,本篇文章以介绍哈希表(散列表)相关名词为主要内容,不涉及具体实现过程或代码(本文部分解释为个人理解,如有疑议请评论指出或移步百度百科:哈希表,参考官方解释)
哈希表,hastable,也可以叫做散列表,名字不重要,只要明白这两者均代表同一样就对了。它是一种可以通过关键码值而可以直接快速访问的数据结构。
哈希表(散列表)是一系列关键码值通过哈希函数(散列函数)计算后映射在一个连续有限的区间上的集合,这个集合成为哈希表(散列表),这个集合保存了这一系列关键码值的散列地址。给定这一系列关键码值中的任意一个关键码值可以快速定位到对应的散列地址。
关键码值(关键字)对于哈希函数(散列函数)来说就是一个可变因子,相当于我们常说的变量,例如f(x)=ax+b,通过将x带入函数式中产生后的结果“象”映射在哈希表中,这个象也称为改关键码值的散列地址。
哈希函数(散列函数)作为关键码值与哈希表的中间介质,关系着关键码值产生的哈希地址,选取合适的哈希函数有着重要意义,良好恰当的哈希函数能够提高哈希表的访问性能,减少哈希冲突,增加数据的访问速度。
哈希冲突(散列冲突)顾名思义就是在构造哈希表时产生的冲突,假如在没有设计良好的哈希函数或没有选取恰当的解决冲突的方法的情况下,不同的关键码值可能产生相同的结果,即映射到相同的散列地址,这就是哈希冲突。(x1不等于x2,但f(x1) = f(x2))。