admin 管理员组

文章数量: 887021

[hash]

Hash简单点讲就是把任意一段数据经过某种算法生成一段唯一的固定长度的数据

一般hash算法

最简单的hash算法是用取余的方式，根据hash地址存放数据，这需要提供键值对（Key-value）Key是地址，value是存放的数据。

算法逻辑

  • 输入存放数据，并建立（Key-value）对象
  • 通过取余数的方式 公式H=d%n （H:哈希地址，d为数据，具有唯一性，n是样本总数）
  • 把产生的哈希地址和对应数据存储到字典对象中

        hash表，把单个字符映射一个数字的方式，比如说字符串abAB01就可以映为{97,98,65,66,48,49}。希望把这串序列成[0，mod-1]中的一个数字称为字符串的hash值，转换方式和k进制转换十进制一样，就是不停的迭代运算hash=(hash*k+s[i])%mod即可，k的值也可以任意选，但是一般来说不少于128（ascill字符集的数量）,当然，求hash的方法不唯一，例如如果字符集局限于a到z的小写字母，也可以吧每个字母映射0到25，此时基数为26。

        这里的mod会取一个一个比较大的质数以便减少冲突的可能性，而且在空间允许的情况下尽可能大，例如10007,999983等，根据情况选。由于可能有多个不同的字符串对应同一个hash值，对每个hash值建立一个vector（或者链表都可以），这样就可以将这个插入的字符串和其相同的所有字符串比较，看看是否相等，就知道这个字符串是否出现过。

由(a+b)%p=(a%p+b%p)%p的原理可以将哈希函数计算化简为

    for i in s:hash = hash * base + (ord(i) - ord('A')) + 1hash %= P

本文标签： hash

版权声明：本文标题：[hash] 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1687479077h107067.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。