美文网首页
hash 哈希查找复杂度为什么这么低?

hash 哈希查找复杂度为什么这么低?

作者: yousa_ | 来源:发表于2020-02-16 18:00 被阅读0次

First of all,在众多搜索算法里,哈希算法时间最快,其时间复杂度为o(1)
哈希算法,又称散列算法,能大大提高搜索的效率。它的主要工作是将一个数字映射到一个表格的某个地方打一个比喻,哈希就像那些公司前台的接待人员,直接将领导的电话记住。而哈希,就是将每一个元素的位置记住,就是我们不去找某个东西,而是将它的位置算出来。

hash它为什么对于键-值查找性能高

学过数据结构的,都应该晓得,线性表和树中,记录在结构中的相对位置是随机的,记录和关键字之间不存在明确的关系,因此在查找记录的时候,需要进行一系列的关键字比较,这种查找方式建立在比较的基础之上,在.net中(Array,ArrayList,List)这些集合结构采用了上面的存储方式。
比如,现在我们有一个班同学的数据,包括姓名,性别,年龄,学号等。假如数据有

姓名 性别 年龄 学号
张三 23 1
李四 24 2
王五 24 3

假如,我们按照姓名来查找,假设查找函数FindByName(string name);

  • 查找“张三”
    只需在第一行匹配一次。
  • 查找"王五"
    在第一行匹配,失败,
    在第二行匹配,失败,
    在第三行匹配,成功
    上面两种情况,分别分析了最好的情况,和最坏的情况,那么平均查找次数应该为 (1+3)/2=2次,即平均查找次数为(记录总数+1)的1/2。
    尽管有一些优化的算法,可以使查找排序效率增高,但是复杂度会保持在log2n的范围之内。
    如何更更快的进行查找呢?我们所期望的效果是一下子就定位到要找记录的位置之上,这时候时间复杂度为1,查找最快。如果我们事先为每条记录编一个序号,然后让他们按号入位,我们又知道按照什么规则对这些记录进行编号的话,如果我们再次查找某个记录的时候,只需要先通过规则计算出该记录的编号,然后根据编号,在记录的线性队列中,就可以轻易的找到记录了 。
    注意,上述的描述包含了两个概念,一个是用于对学生进行编号的规则,在数据结构中,称之为哈希函数,另外一个是按照规则为学生排列的顺序结构,称之为哈希表。
    仍以上面的学生为例,假设学号就是规则,老师手上有一个规则表,在排座位的时候也按照这个规则来排序,查找李四,首先该教师会根据规则判断出,李四的编号为2,就是在座位中的2号位置,直接走过去,“李四,哈哈,你小子,就是在这!”
    看看大体流程:


直接取值法

直接取值法,就是直接以当前元素的值来决定它的位置。化成函数就是 H(x)=x。这种方法的好处是不可能冲突,除非两个元素一模一样。而且这样甚至能够保证在哈希表里面的元素有序,就像计数排序一样。
但是这种方法也有缺点,当x的取值太大的时候,耗费的空间同时也会很大。举个例子,如果有3个数:3,6814246421,1654654614874213,那光是这三个数,就已经耗费了巨大的内存空间了。

除法哈希

既然直接取值会耗费很大的内存空间,那我们可以模一下这个变量,一般来说,模一个数组长度,就是不错的选择。这样既可以刚刚好放下这些数据,又不会耗费太多的空间。化成函数就是H(x)=x%m。但是这样就会出现冲突。所谓冲突,就是指两个取值不一样的数,它们在哈希后得出的值相同,映射到了同一个位置。也就是说,a!=b,但H(a)==H(b)。在这里我们先不讨论冲突。那怎样尽量避免冲突呢?答案就是:模一个素数!可以证明,当H(x)定义中x%m的m的因数越多,则冲突的概率就越大。不过,其实最好的方法还是增大表格的大小,这样相应的,x%m的取值也会更为多样化。

位运算哈希

除法哈希的缺点之一,是容易冲突,而且有的时候甚至还不与整一个数相关。下面我就介绍一种位运算哈希,这种哈希主要运用乘法,而且多是位运算,速度较快。同时,除法哈希要求数组长度最好是一个素数,但在计算机中,我们更喜欢让数组长度为2的幂数,这样就不会浪费空间。确切地说,就是利用位运算,充分的混合元素。举个例子,ELFHash就是一个很好的实现。

乘法哈希(最常用到)

最后介绍一种最实用且最容易记的哈希算法。这种哈希函数叫做乘法哈希。其原理就是将原数看做一个n进制的数在转换回十进制。这种哈希算法的典型实现有BKDRHash。理解起来很容易,也是奥赛中经常用到的算法,一般来说冲突率非常小。

顺带附上BKDRHash的核心代码(已过测试):

unsigned int BKDRHash(char *key){

  unsigned int seed=131;

  unsigned int hash=0;

  while(*key)
     {
           hash = hash * seed + (*key++);
      }

   return hash%MOD;
}

相关文章

  • hash 哈希查找复杂度为什么这么低?

    First of all,在众多搜索算法里,哈希算法时间最快,其时间复杂度为o(1)哈希算法,又称散列算法,能大大...

  • mysql索引数据结构对比

    1、hash最快 复杂度1,但是hash不支持范围索引 2、链表最慢 复杂度n 不考虑 3、二叉查找树 复杂度lo...

  • 数据结构分类

    1.哈希表(Hash Table) 哈希就是键值对,哈希表就是一个或者多个键值对构成的对象 计数排序中的桶(复杂度...

  • golang 字典map

     当在哈希表中查找某个与键值对应的元素值时,我们需要先把键值作为参数传给这个哈希表。哈希表会先用哈希函数(hash...

  • python数据结构与算法--什么是Hash|哈希函数?

    目录 一,什么是哈希函数? 二,哈希表(hash table)原理 三,为什么不是所有的 hash 函数都可以被用...

  • 哈希表与HashCode

    散列表 又叫哈希表(hash table)。哈希表是种数据结构,它可以提供快速的插入操作和查找操作。通过访...

  • Ⅵ. 哈希算法

    哈希技术既是一种存储方式,也是一种查找方法 哈希算法的实现步骤: 初始化创建Hash表(散列表)给定哈希函数构建H...

  • 计算文件哈希值

    什么是哈希值? 哈希值(hash values)是使用哈希函数(hash function)计算得到的值。哈希函数...

  • 算法+数据结构+Hash

    1.最好的复杂度:只有无冲突的hash table复杂度才是O(1),这是最好的情况。一般是O(c),c为哈希关键...

  • 哈希算法

    哈希算法 什么是hash函数?常见的hash算法hashlib的用法hash算法的用途 什么是hash函数? 哈希...

网友评论

      本文标题:hash 哈希查找复杂度为什么这么低?

      本文链接:https://www.haomeiwen.com/subject/nzkmfhtx.html