草庐IT

python - python中的快速、大宽度、非加密字符串散列

coder 2023-05-22 原文

我需要 python 中的高性能字符串散列函数，它可以生成具有至少 34 位输出的整数(64 位是有意义的，但 32 位太少了)。 Stack Overflow 上还有其他几个类似这样的问题，但在我能找到的每个接受/赞成的答案中，我都属于不适用的几个类别之一(由于给定的原因)。

  • 使用内置的 hash() 函数。 这个函数，至少在我正在开发的机器上(使用 python 2.7 和 64 位cpu) 产生一个适合 32 位的整数 - 对于我的目的来说不够大。
  • 使用 hashlib。 hashlib 提供加密哈希例程，它远慢于非加密目的所需的速度。我认为这是不言而喻的，但如果您需要基准和引用来说服您相信这一事实，那么我可以提供。
  • 使用 string.__hash__() 函数作为原型(prototype)来编写你自己的函数。我怀疑这将是正确的方法，除了这个特定函数的效率在于它使用了 c_mul 函数，该函数包含 32 位 - 再次，对我来说太小了!非常令人沮丧，它是如此接近完美!

理想的解决方案应具有以下属性，按相对松散的重要性顺序排列。

  1. 输出范围至少延长 34 位，可能是 64 位，同时在 所有 位上保留 一致 雪崩特性。 (连接 32 位哈希往往会违反雪崩属性，至少在我的愚蠢示例中是这样。)
  2. 便携。给定两台不同机器上的相同输入字符串，我两次都应该得到相同的结果。这些值将存储在一个文件中以供以后重复使用。
  3. 高性能。越快越好，因为在我正在运行的程序执行期间，这个函数将被调用大约 200 亿次(目前它是性能关键代码。)它不需要用 C 编写，它真的只需要优于 md5(在字符串的内置 hash() 领域中的某个地方)。
  4. 接受一个“扰动”(这里用什么词比较好？)整数作为输入来修改输出。我在下面放了一个例子(列表格式规则不允许我把它放在更近的地方。)我想这不是 100% 必要的，因为它可以通过手动扰动函数的输出来模拟，但是把它作为输入给了我好温暖的感觉。
  5. 完全用 Python 编写。如果它绝对，肯定需要用 C 编写，那么我想这可以做到，但我会用 python 编写的函数比 C 中更快的函数慢 20%，这只是由于项目使用两种不同语言的协调性头痛。是的，这是一种逃避，但这是一个愿望 list 。

“扰动”哈希示例，其中哈希值被一个小整数值 n 急剧改变

def perturb_hash(key,n):
    return hash((key,n))

最后，如果您对我到底在做什么感到好奇，我需要这样一个特定的哈希函数，我正在对 pybloom 模块进行完全重写，以显着提高其性能。我成功了(现在它的运行速度提高了大约 4 倍，并且使用了大约 50% 的空间)，但我注意到有时如果过滤器变得足够大，它会突然增加误报率。我意识到这是因为哈希函数没有解决足够的位。 32 位只能处理 40 亿位(请注意，过滤器针对的是位而不是字节)，而我用于基因组数据的一些过滤器会增加一倍或更多(因此最少 34 位。)

谢谢!

最佳答案

看看128-bit variant of MurmurHash3 . algorithm's page包括一些性能数字。应该可以将其移植到 Python，纯或作为 C 扩展。 (已更新作者建议使用 128 位变体并丢弃不需要的位)。

如果 MurmurHash2 64 位适合您，pyfasthash package 中有一个 Python 实现(C 扩展)。 ，其中包括一些其他非加密哈希变体，尽管其中一些仅提供 32 位输出。

更新我为 Murmur3 散列函数做了一个快速的 Python 包装器。 Github project is here您可以在 Python Package Index as well 上找到它;它只需要一个 C++ 编译器来构建；无需升压。

使用示例及时序对比:

import murmur3
import timeit

# without seed
print murmur3.murmur3_x86_64('samplebias')
# with seed value
print murmur3.murmur3_x86_64('samplebias', 123)

# timing comparison with str __hash__
t = timeit.Timer("murmur3.murmur3_x86_64('hello')", "import murmur3")
print 'murmur3:', t.timeit()

t = timeit.Timer("str.__hash__('hello')")
print 'str.__hash__:', t.timeit()

输出:

15662901497824584782
7997834649920664675
murmur3: 0.264422178268
str.__hash__: 0.219163894653

关于python - python中的快速、大宽度、非加密字符串散列，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5400275/

python中的strongmurmur3codestringhashhigh-speed-computing

有关python - python中的快速、大宽度、非加密字符串散列的更多相关文章

  1. ruby - 如何从 ruby​​ 中的字符串运行任意对象方法？ - 2

    总的来说，我对ruby​​还比较陌生，我正在为我正在创建的对象编写一些rspec测试用例。许多测试用例都非常基础，我只是想确保正确填充和返回值。我想知道是否有办法使用循环结构来执行此操作。不必为我要测试的每个方法都设置一个assertEquals。例如:describeitem,"TestingtheItem"doit"willhaveanullvaluetostart"doitem=Item.new#HereIcoulddotheitem.name.shouldbe_nil#thenIcoulddoitem.category.shouldbe_nilendend但我想要一些方法来使用

  2. Ruby 解析字符串 - 2

    我有一个字符串input="maybe(thisis|thatwas)some((nice|ugly)(day|night)|(strange(weather|time)))"Ruby中解析该字符串的最佳方法是什么？我的意思是脚本应该能够像这样构建句子:maybethisissomeuglynightmaybethatwassomenicenightmaybethiswassomestrangetime等等，你明白了......我应该一个字符一个字符地读取字符串并构建一个带有堆栈的状态机来存储括号值以供以后计算，还是有更好的方法？也许为此目的准备了一个开箱即用的库？

  3. ruby - 其他文件中的 Rake 任务 - 2

    我试图在一个项目中使用rake，如果我把所有东西都放到Rakefile中，它会很大并且很难读取/找到东西，所以我试着将每个命名空间放在lib/rake中它自己的文件中，我添加了这个到我的rake文件的顶部:Dir['#{File.dirname(__FILE__)}/lib/rake/*.rake'].map{|f|requiref}它加载文件没问题，但没有任务。我现在只有一个.rake文件作为测试，名为“servers.rake”，它看起来像这样:namespace:serverdotask:testdoputs"test"endend所以当我运行rakeserver:testid时

  4. ruby-on-rails - 在 Rails 中将文件大小字符串转换为等效千字节 - 2

    我的目标是转换表单输入，例如“100兆字节”或“1GB”，并将其转换为我可以存储在数据库中的文件大小(以千字节为单位)。目前，我有这个:defquota_convert@regex=/([0-9]+)(.*)s/@sizes=%w{kilobytemegabytegigabyte}m=self.quota.match(@regex)if@sizes.include?m[2]eval("self.quota=#{m[1]}.#{m[2]}")endend这有效，但前提是输入是倍数(“gigabytes”，而不是“gigabyte”)并且由于使用了eval看起来疯狂不安全。所以，功能正常，

  5. ruby-on-rails - Ruby net/ldap 模块中的内存泄漏 - 2

    作为我的Rails应用程序的一部分，我编写了一个小导入程序，它从我们的LDAP系统中吸取数据并将其塞入一个用户表中。不幸的是，与LDAP相关的代码在遍历我们的32K用户时泄漏了大量内存，我一直无法弄清楚如何解决这个问题。这个问题似乎在某种程度上与LDAP库有关，因为当我删除对LDAP内容的调用时，内存使用情况会很好地稳定下来。此外，不断增加的对象是Net::BER::BerIdentifiedString和Net::BER::BerIdentifiedArray，它们都是LDAP库的一部分。当我运行导入时，内存使用量最终达到超过1GB的峰值。如果问题存在，我需要找到一些方法来更正我的代

  6. ruby-on-rails - unicode 字符串的长度 - 2

    在我的Rails(2.3，Ruby1.8.7)应用程序中，我需要将字符串截断到一定长度。该字符串是unicode，在控制台中运行测试时，例如'א'.length，我意识到返回了双倍长度。我想要一个与编码无关的长度，以便对unicode字符串或latin1编码字符串进行相同的截断。我已经了解了Ruby的大部分unicode资料，但仍然有些一头雾水。应该如何解决这个问题？ 最佳答案 Rails有一个返回多字节字符的mb_chars方法。试试unicode_string.mb_chars.slice(0,50)

  7. python - 如何使用 Ruby 或 Python 创建一系列高音调和低音调的蜂鸣声？ - 2

    关闭。这个问题是opinion-based.它目前不接受答案。想要改进这个问题？更新问题，以便editingthispost可以用事实和引用来回答它.关闭4年前。Improvethisquestion我想在固定时间创建一系列低音和高音调的哔哔声。例如:在150毫秒时发出高音调的蜂鸣声在151毫秒时发出低音调的蜂鸣声200毫秒时发出低音调的蜂鸣声250毫秒的高音调蜂鸣声有没有办法在Ruby或Python中做到这一点？我真的不在乎输出编码是什么(.wav、.mp3、.ogg等等)，但我确实想创建一个输出文件。

  8. ruby-on-rails - Rails 3 中的多个路由文件 - 2

    Rails2.3可以选择随时使用RouteSet#add_configuration_file添加更多路由。是否可以在Rails3项目中做同样的事情？ 最佳答案 在config/application.rb中:config.paths.config.routes在Rails3.2(也可能是Rails3.1)中，使用:config.paths["config/routes"] 关于ruby-on-rails-Rails3中的多个路由文件，我们在StackOverflow上找到一个类似的问题

  9. ruby - 将差异补丁应用于字符串/文件 - 2

    对于具有离线功能的智能手机应用程序，我正在为Xml文件创建单向文本同步。我希望我的服务器将增量/差异(例如GNU差异补丁)发送到目标设备。这是计划:Time=0Server:hasversion_1ofXmlfile(~800kiB)Client:hasversion_1ofXmlfile(~800kiB)Time=1Server:hasversion_1andversion_2ofXmlfile(each~800kiB)computesdeltaoftheseversions(=patch)(~10kiB)sendspatchtoClient(~10kiBtransferred)Cl

  10. ruby-on-rails - Rails 常用字符串(用于通知和错误信息等) - 2

    大约一年前，我决定确保每个包含非唯一文本的Flash通知都将从模块中的方法中获取文本。我这样做的最初原因是为了避免一遍又一遍地输入相同的字符串。如果我想更改措辞，我可以在一个地方轻松完成，而且一遍又一遍地重复同一件事而出现拼写错误的可能性也会降低。我最终得到的是这样的:moduleMessagesdefformat_error_messages(errors)errors.map{|attribute,message|"Error:#{attribute.to_s.titleize}#{message}."}enddeferror_message_could_not_find(obje

随机推荐