blocks|key|1096895|text|如果你知道确切的密钥，那么产生一个完美的散列函数是很容易的-|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1096896|int+hash+(int+n)+{
++switch+(n)+{
++++case+10:+++return+0;
++++case+100:++return+1;
++++case+32:+++return+2;
++++//+...
++++default:+++return+-1;
++}
}|code-block|syntax|javascript|1096897|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

if you know the exact keys then it is trivial to produce a perfect hash function - 

<pre><code>int hash (int n) {
 switch (n) {
 case 10: return 0;
 case 100: return 1;
 case 32: return 2;
 // ...
 default: return -1;
 }
}
</code></pre>

blocks|key|1096922|text|找到了一个|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1096923|我尝试了一些方法，找到了一个半手动的方法：|1096924|(n+%5E+28)+%25+13|code-block|syntax|javascript|1096925|半手动部分是下面的ruby脚本，我用它来测试带有一系列参数的候选函数：|1096926|t+=+[10,+100,+32,+45,+58,+126,+3,+29,+200,+400,+0]
(1..200).each+do+%7Ci%7C
++t2+=+t.map+{+%7Ce%7C+(e+%5E+i)+%25+13+}
++puts+i+if+t2.uniq.length+==+t.length
end|1096927|entityMap^0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|O|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|P|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|Q|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|R|8|@]|9|@]|A|$]]|$1|K|3|L|5|F|7|S|8|@]|9|@]|A|$G|H]]|$1|M|3|-4|5|6|7|T|8|@]|9|@]|A|$]]]|N|$]]

<h2>Found One</h2>

I tried a few things and found one semi-manually:

<pre><code>(n ^ 28) % 13
</code></pre>

The semi-manual part was the following ruby script that I used to test candidate functions with a range of parameters:

<pre><code>t = [10, 100, 32, 45, 58, 126, 3, 29, 200, 400, 0]
(1..200).each do |i|
 t2 = t.map { |e| (e ^ i) % 13 }
 puts i if t2.uniq.length == t.length
end
</code></pre>

blocks|key|882070|text|我做了一个快速检查，使用SHA256散列函数，然后用13除以模数，当我在Mathematica中尝试它时，它起作用了。对于c%2B%2B，这个函数应该在openssl库中。请参阅此post。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|882071|但是，如果你做了大量的哈希和查找，模除法是一个重复执行的相当昂贵的操作。还有另一种将n位哈希函数映射到i位索引的方式。请参阅Michael+Mitzenmacher的post，了解如何在C中使用位移位操作。希望对您有所帮助。|882072|entityMap|0|LINK|mutability|MUTABLE|url|https://stackoverflow.com/questions/2262386/generate-sha256-with-openssl-and-c|1|http://mybiasedcoin.blogspot.com/2009/12/text-book-algorithms-at-soda-guest-post.html^0|2E|4|0|0|2B|4|1|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@$A|Q|B|R|1|S]]|C|$]]|$1|D|3|E|5|6|7|T|8|@]|9|@$A|U|B|V|1|W]]|C|$]]|$1|F|3|-4|5|6|7|X|8|@]|9|@]|C|$]]]|G|$H|$5|I|J|K|C|$L|M]]|N|$5|I|J|K|C|$L|O]]]]

I did a quick check and using the SHA256 hash function and then doing modular division by 13 worked when I tried it in Mathematica. For c++ this function should be in the openssl library. See this <a href="https://stackoverflow.com/questions/2262386/generate-sha256-with-openssl-and-c">post</a>. 

If you were doing a lot of hashing and lookup though, modular division is a pretty expensive operation to do repeatedly. There is another way of mapping an n-bit hash function into a i-bit indices. See this <a href="http://mybiasedcoin.blogspot.com/2009/12/text-book-algorithms-at-soda-guest-post.html" rel="nofollow noreferrer">post</a> by Michael Mitzenmacher about how to do it with a bit shift operation in C. Hope that helps.

blocks|key|882115|text|Bob+Jenkins也有一个这样的程序：http://burtleburtle.net/bob/hash/perfect.html|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|882116|除非您非常幸运，否则对于给定的数据集，没有“很好”的完美哈希函数。完美的散列算法通常在密钥上使用一个简单的散列函数(使用足够的位，因此它是无冲突的)，然后使用一个表来完成它。|882117|entityMap|0|LINK|mutability|MUTABLE|url|http://burtleburtle.net/bob/hash/perfect.html^0|L|19|0|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@$A|O|B|P|1|Q]]|C|$]]|$1|D|3|E|5|6|7|R|8|@]|9|@]|C|$]]|$1|F|3|-4|5|6|7|S|8|@]|9|@]|C|$]]]|G|$H|$5|I|J|K|C|$L|M]]]]

Bob Jenkins has a program for this too: <a href="http://burtleburtle.net/bob/hash/perfect.html" rel="nofollow">http://burtleburtle.net/bob/hash/perfect.html</a>

Unless you're very lucky, there's no "nice" perfect hash function for a given dataset. Perfect hashing algorithms usually use a simple hashing function on the keys (using enough bits so it's collision-free) then use a table to finish it off.

blocks|key|1097085|text|在某些平台上(例如嵌入式)，模运算代价很高，因此最好避免使用%25+13。但是低阶位的AND运算是廉价的，并且等同于2的幂的模运算。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1097086|我尝试编写一个简单的程序(用Python语言)来搜索11个数据点的完美散列，使用简单的形式，比如((x+<<+a)+%5E+(x+<<+b))+&+0xF+(其中&+0xF等同于%25+16，例如，它给出的结果范围是0..15+)。我能够找到下面的无冲突散列，它给出了一个范围为0..15+(表示为C宏)的索引：|1097087|#define+HASH(x)++++((((x)+<<+2)+%5E+((x)+>>+2))+&+0xF)|code-block|syntax|javascript|1097088|下面是我使用的Python程序：|1097089|data+=+[+10,+100,+32,+45,+58,+126,+3,+29,+200,+400,+0+]

def+shift_right(value,+shift_value):
++++"""Shift+right+that+allows+for+negative+values,+which+shift+left
++++(Python+shift+operator+doesn't+allow+negative+shift+values)"""
++++if+shift_value+==+None:
++++++++return+0
++++if+shift_value+<+0:
++++++++return+value+<<+(-shift_value)
++++else:
++++++++return+value+>>+shift_value

def+find_hash():
++++def+hashf(val,+i,+j+=+None,+k+=+None):
++++++++return+(shift_right(val,+i)+%5E+shift_right(val,+j)+%5E+shift_right(val,+k))+&+0xF

++++for+i+in+xrange(-7,+8):
++++++++for+j+in+xrange(i,+8):
++++++++++++#for+k+in+xrange(j,+8):
++++++++++++++++#j+=+None
++++++++++++++++k+=+None
++++++++++++++++outputs+=+set()
++++++++++++++++for+val+in+data:
++++++++++++++++++++hash_val+=+hashf(val,+i,+j,+k)
++++++++++++++++++++if+hash_val+>=+13:
++++++++++++++++++++++++pass
++++++++++++++++++++++++#break
++++++++++++++++++++if+hash_val+in+outputs:
++++++++++++++++++++++++break
++++++++++++++++++++else:
++++++++++++++++++++++++outputs.add(hash_val)
++++++++++++++++else:
++++++++++++++++++++print+i,+j,+k,+outputs

if+__name__+==+'__main__':
++++find_hash()|1097090|entityMap^0|U|4|15|3|0|1C|R|27|5|2F|4|0|0|0|0^^$0|@$1|2|3|4|5|6|7|S|8|@$9|T|A|U|B|C]|$9|V|A|W|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|X|8|@$9|Y|A|Z|B|C]|$9|10|A|11|B|C]|$9|12|A|13|B|C]]|D|@]|E|$]]|$1|H|3|I|5|J|7|14|8|@]|D|@]|E|$K|L]]|$1|M|3|N|5|6|7|15|8|@]|D|@]|E|$]]|$1|O|3|P|5|J|7|16|8|@]|D|@]|E|$K|L]]|$1|Q|3|-4|5|6|7|17|8|@]|D|@]|E|$]]]|R|$]]

On some platforms (e.g. embedded), modulo operation is expensive, so <code>% 13</code> is better avoided. But <code>AND</code> operation of low-order bits is cheap, and equivalent to modulo of a power-of-2.

I tried writing a simple program (in Python) to search for a perfect hash of your 11 data points, using simple forms such as <code>((x &lt;&lt; a) ^ (x &lt;&lt; b)) &amp; 0xF</code> (where <code>&amp; 0xF</code> is equivalent to <code>% 16</code>, giving a result in the range 0..15, for example). I was able to find the following collision-free hash which gives an index in the range 0..15 (expressed as a C macro):

<pre><code>#define HASH(x) ((((x) &lt;&lt; 2) ^ ((x) &gt;&gt; 2)) &amp; 0xF)
</code></pre>

Here is the Python program I used:

<pre><code>data = [ 10, 100, 32, 45, 58, 126, 3, 29, 200, 400, 0 ]

def shift_right(value, shift_value):
 """Shift right that allows for negative values, which shift left
 (Python shift operator doesn't allow negative shift values)"""
 if shift_value == None:
 return 0
 if shift_value &lt; 0:
 return value &lt;&lt; (-shift_value)
 else:
 return value &gt;&gt; shift_value

def find_hash():
 def hashf(val, i, j = None, k = None):
 return (shift_right(val, i) ^ shift_right(val, j) ^ shift_right(val, k)) &amp; 0xF

 for i in xrange(-7, 8):
 for j in xrange(i, 8):
 #for k in xrange(j, 8):
 #j = None
 k = None
 outputs = set()
 for val in data:
 hash_val = hashf(val, i, j, k)
 if hash_val &gt;= 13:
 pass
 #break
 if hash_val in outputs:
 break
 else:
 outputs.add(hash_val)
 else:
 print i, j, k, outputs

if __name__ == '__main__':
 find_hash()
</code></pre>

blocks|key|882224|text|尝试以下将n值映射到0到12+(1369%25(n%2B1))%2513之间的唯一索引的方法|type|unstyled|depth|inlineStyleRanges|entityRanges|data|882225|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Try the following which maps your n values to unique indices between 0 and 12
(1369%(n+1))%13

I'm attempting to hash the values

<pre><code>10, 100, 32, 45, 58, 126, 3, 29, 200, 400, 0
</code></pre>

I need a function that will map them to an array that has a size of 13 without causing any collisions.

I've spent several hours thinking this over and googling and can't figure this out. I haven't come close to a viable solution.

How would I go about finding a hash function of this sort? I've played with gperf, but I don't really understand it and I couldn't get the results I was looking for.

perfect hash function

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

我正在尝试对这些值进行散列10, 100, 32, 45, 58, 126, 3, 29, 200, 400, 0我需要一个函数，它将它们映射到一个大小为13的数组中，而不会导致任何冲突。我花了几个小时反复思考和搜索，但还是想不通。我还没有接近一个可行的解决方案。我该如何找到这种散列函数呢？我用过gperf，但我并不是...

问完美散列函数
EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问完美散列函数EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问完美散列函数
EN