blocks|key|3401130|text|实现__hash__()的一种简单、正确的方法是使用密钥元组。它不会像专门的散列那样快，但是如果你需要它，那么你可能应该用C实现这个类型。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|3401131|下面是一个使用键进行散列和相等的示例：|3401132|class+A:
++++def+__key(self):
++++++++return+(self.attr_a,+self.attr_b,+self.attr_c)

++++def+__hash__(self):
++++++++return+hash(self.__key())

++++def+__eq__(self,+other):
++++++++if+isinstance(other,+A):
++++++++++++return+self.__key()+==+other.__key()
++++++++return+NotImplemented|code-block|syntax|javascript|3401133|此外，documentation+of+__hash__还提供了更多信息，这些信息在某些特定情况下可能很有价值。|3401134|entityMap|0|LINK|mutability|MUTABLE|url|https://docs.python.org/3.5/reference/datamodel.html#object.__hash__^0|2|A|0|0|0|K|8|3|P|0|0^^$0|@$1|2|3|4|5|6|7|W|8|@$9|X|A|Y|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|Z|8|@]|D|@]|E|$]]|$1|H|3|I|5|J|7|10|8|@]|D|@]|E|$K|L]]|$1|M|3|N|5|6|7|11|8|@$9|12|A|13|B|C]]|D|@$9|14|A|15|1|16]]|E|$]]|$1|O|3|-4|5|6|7|17|8|@]|D|@]|E|$]]]|P|$Q|$5|R|S|T|E|$U|V]]]]

An easy, correct way to implement <code>__hash__()</code> is to use a key tuple. It won't be as fast as a specialized hash, but if you need that then you should probably implement the type in C.

Here's an example of using a key for hash and equality:

<pre><code>class A:
 def __key(self):
 return (self.attr_a, self.attr_b, self.attr_c)

 def __hash__(self):
 return hash(self.__key())

 def __eq__(self, other):
 if isinstance(other, A):
 return self.__key() == other.__key()
 return NotImplemented
</code></pre>

Also, the <a href="https://docs.python.org/3.5/reference/datamodel.html#object.__hash__" rel="noreferrer">documentation of <code>__hash__</code></a> has more information, that may be valuable in some particular circumstances.

blocks|key|514153|text|取决于您返回的哈希值的大小。这是一个简单的逻辑，如果你需要根据四个32位整数的哈希返回一个32位整数，你会得到冲突。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|514154|我更喜欢位操作。例如，下面的C伪代码：|514155|int+a;
int+b;
int+c;
int+d;
int+hash+=+(a+&+0xF000F000)+%7C+(b+&+0x0F000F00)+%7C+(c+&+0x00F000F0+%7C+(d+&+0x000F000F);|code-block|syntax|javascript|514156|这样的系统也可以用于浮点数，如果您只是将它们作为位值，而不是实际表示浮点值，可能会更好。|514157|对于字符串，我几乎不知道。|514158|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|6|7|S|8|@]|9|@]|A|$]]|$1|M|3|-4|5|6|7|T|8|@]|9|@]|A|$]]]|N|$]]

Depends on the size of the hash value you return. It's simple logic that if you need to return a 32bit int based on the hash of four 32bit ints, you're gonna get collisions.

I would favor bit operations. Like, the following C pseudo code:

<pre><code>int a;
int b;
int c;
int d;
int hash = (a &amp; 0xF000F000) | (b &amp; 0x0F000F00) | (c &amp; 0x00F000F0 | (d &amp; 0x000F000F);
</code></pre>

Such a system could work for floats too, if you simply took them as their bit value rather than actually representing a floating-point value, maybe better.

For strings, I've got little/no idea.

blocks|key|3401215|text|我可以试着回答你问题的第二部分。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3401216|冲突可能不是由散列代码本身引起的，而是由将散列代码映射到集合中的索引引起的。例如，您的哈希函数可以返回从1到10000的随机值，但是如果您的哈希表只有32个条目，则在插入时会发生冲突。|3401217|此外，我认为冲突将由集合在内部解决，并且有许多方法可以解决冲突。最简单(也是最糟糕)的方法是，给出一个要在索引i处插入的条目，将i加1，直到找到一个空点并在那里插入。然后，检索也以同样的方式工作。这会导致对某些条目的检索效率低下，因为您可能有一个条目需要遍历整个集合才能找到！|3401218|其他冲突解决方法通过在插入项以展开事物时移动哈希表中的条目来减少检索时间。这会增加插入时间，但假设您阅读的内容多于插入的内容。还有一些方法尝试将不同的冲突条目分支出来，以便条目聚集在一个特定的点上。|3401219|此外，如果您需要调整集合的大小，您将需要重新散列所有内容或使用动态散列方法。|3401220|简而言之，根据您使用的散列代码，您可能必须实现自己的冲突解决方法。如果您没有将它们存储在一个集合中，那么您可能可以使用一个散列函数，它只会在一个非常大的范围内生成散列代码。如果是这样的话，你可以确保你的容器比它需要的更大(当然越大越好)，这取决于你的内存问题。|3401221|如果你更感兴趣，这里有一些链接：|3401222|coalesced+hashing+on+wikipedia|offset|length|3401223|维基百科也有各种冲突解决方法的summary：|3401224|此外，塔普的"File+Organization+And+Processing“广泛地涵盖了许多冲突解决方法。这是哈希算法的一个很好的参考。|3401225|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Coalesced_hashing|1|http://en.wikipedia.org/wiki/Hash_table|2|https://rads.stackoverflow.com/amzn/click/com/0471617660^0|0|0|0|0|0|0|0|0|U|0|0|F|7|1|0|7|W|2|0^^$0|@$1|2|3|4|5|6|7|17|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|18|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|19|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|1A|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|1B|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|1C|8|@]|9|@]|A|$]]|$1|L|3|M|5|6|7|1D|8|@]|9|@]|A|$]]|$1|N|3|O|5|6|7|1E|8|@]|9|@$P|1F|Q|1G|1|1H]]|A|$]]|$1|R|3|S|5|6|7|1I|8|@]|9|@$P|1J|Q|1K|1|1L]]|A|$]]|$1|T|3|U|5|6|7|1M|8|@]|9|@$P|1N|Q|1O|1|1P]]|A|$]]|$1|V|3|-4|5|6|7|1Q|8|@]|9|@]|A|$]]]|W|$X|$5|Y|Z|10|A|$11|12]]|13|$5|Y|Z|10|A|$11|14]]|15|$5|Y|Z|10|A|$11|16]]]]

I can try to answer the second part of your question.

The collisions will probably result not from the hash code itself, but from mapping the hash code to an index in a collection. So for example your hash function could return random values from 1 to 10000, but if your hash table only has 32 entries you'll get collisions on insertion.

In addition, I would think that collisions would be resolved by the collection internally, and there are many methods to resolve collisions. The simplest (and worst) is, given an entry to insert at index i, add 1 to i until you find an empty spot and insert there. Retrieval then works the same way. This results in inefficient retrievals for some entries, as you could have an entry that requires traversing the entire collection to find!

Other collision resolution methods reduce the retrieval time by moving entries in the hash table when an item is inserted to spread things out. This increases the insertion time but assumes you read more than you insert. There are also methods that try and branch different colliding entries out so that entries to cluster in one particular spot. 

Also, if you need to resize the collection you will need to rehash everything or use a dynamic hashing method. 

In short, depending on what you're using the hash code for you may have to implement your own collision resolution method. If you're not storing them in a collection, you can probably get away with a hash function that just generates hash codes in a very large range. If so, you can make sure your container is bigger than it needs to be (the bigger the better of course) depending on your memory concerns. 

Here are some links if you're interested more: 

<a href="http://en.wikipedia.org/wiki/Coalesced_hashing" rel="nofollow noreferrer">coalesced hashing on wikipedia</a>

Wikipedia also has a <a href="http://en.wikipedia.org/wiki/Hash_table" rel="nofollow noreferrer">summary</a> of various collision resolution methods: 

Also, "<a href="https://rads.stackoverflow.com/amzn/click/com/0471617660" rel="nofollow noreferrer" rel="nofollow noreferrer">File Organization And Processing</a>" by Tharp covers alot of collision resolution methods extensively. IMO it's a great reference for hashing algorithms.

blocks|key|1259174|text|微软研究院的Paul+Larson研究了各种各样的散列函数。他告诉我|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1259175|for+c+in+some_string:
++++hash+=+101+*+hash++%2B++ord(c)|code-block|syntax|javascript|1259176|令人惊讶的是，它对各种各样的字符串都工作得很好。我发现类似的多项式技术可以很好地计算不同子字段的散列。|1259177|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|L|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|M|8|@]|9|@]|A|$]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

Paul Larson of Microsoft Research studied a wide variety of hash functions. He told me that 

<pre><code>for c in some_string:
 hash = 101 * hash + ord(c)
</code></pre>

worked surprisingly well for a wide variety of strings. I've found that similar polynomial techniques work well for computing a hash of disparate subfields.

blocks|key|1262910|text|关于何时以及如何在programiz+website上实现__hash__函数的很好的解释|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1262911|仅提供概述的屏幕截图：(已检索2019-12-13)|1262912|​|1262913|📷|atomic|1262914|1262915|至于该方法的个人实现，上面提到的站点提供了一个与millerdev的答案相匹配的示例。|1262916|class+Person:
def+__init__(self,+age,+name):
++++self.age+=+age
++++self.name+=+name

def+__eq__(self,+other):
++++return+self.age+==+other.age+and+self.name+==+other.name

def+__hash__(self):
++++print('The+hash+is:')
++++return+hash((self.age,+self.name))

person+=+Person(23,+'Adam')
print(hash(person))|code-block|syntax|javascript|1262917|entityMap|0|LINK|mutability|MUTABLE|url|https://www.programiz.com/python-programming/methods/built-in/hash|1|IMAGE|IMMUTABLE|imageUrl|https://i.stack.imgur.com/Ep5ZP.png|imageAlt^0|T|8|9|H|0|0|0|0|0|1|1|0|0|0|0^^$0|@$1|2|3|4|5|6|7|18|8|@$9|19|A|1A|B|C]]|D|@$9|1B|A|1C|1|1D]]|E|$]]|$1|F|3|G|5|6|7|1E|8|@]|D|@]|E|$]]|$1|H|3|I|5|6|7|1F|8|@]|D|@]|E|$]]|$1|J|3|K|5|L|7|1G|8|@]|D|@$9|1H|A|1I|1|1J]]|E|$]]|$1|M|3|I|5|6|7|1K|8|@]|D|@]|E|$]]|$1|N|3|O|5|6|7|1L|8|@]|D|@]|E|$]]|$1|P|3|Q|5|R|7|1M|8|@]|D|@]|E|$S|T]]|$1|U|3|-4|5|6|7|1N|8|@]|D|@]|E|$]]]|V|$W|$5|X|Y|Z|E|$10|11]]|12|$5|13|Y|14|E|$15|16|17|-4]]]]

A very good explanation on when and how implement the <code>__hash__</code> function is on <a href="https://www.programiz.com/python-programming/methods/built-in/hash" rel="nofollow noreferrer">programiz website</a>:

Just a screenshot to provide an overview:
(Retrieved 2019-12-13)

<a href="https://i.stack.imgur.com/Ep5ZP.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/Ep5ZP.png" alt="Screenshot of https://www.programiz.com/python-programming/methods/built-in/hash 2019-12-13"></a>

As for a personal implementation of the method, the above mentioned site provides an example that matches the answer of millerdev.

<pre><code>class Person:
def __init__(self, age, name):
 self.age = age
 self.name = name

def __eq__(self, other):
 return self.age == other.age and self.name == other.name

def __hash__(self):
 print('The hash is:')
 return hash((self.age, self.name))

person = Person(23, 'Adam')
print(hash(person))
</code></pre>

blocks|key|1993261|text|实现散列(以及列表、字典、元组)的一个好方法是通过使用__iter__使其可迭代，从而使对象具有可预测的项顺序。因此，修改上面的一个示例：|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1993262|class+A(object):

++++def+__init__(self,+a,+b,+c):
++++++++self._a+=+a
++++++++self._b+=+b
++++++++self._c+=+c

++++def+__iter__(self):
++++++++yield+"a",+self._a
++++++++yield+"b",+self._b
++++++++yield+"c",+self._c

++++def+__hash__(self):
++++++++return+hash(tuple(self))

++++def+__eq__(self,+other):
++++++++return+(isinstance(other,+type(self))
++++++++++++++++and+tuple(self)+==+tuple(other))|code-block|syntax|javascript|1993263|(这里哈希不需要__eq__，但它很容易实现)。|1993264|现在添加一些可变成员，看看它是如何工作的：|1993265|a+=+2;+b+=+2.2;+c+=+'cat'
hash(A(a,+b,+c))++#+-5279839567404192660
dict(A(a,+b,+c))++#+{'a':+2,+'b':+2.2,+'c':+'cat'}
list(A(a,+b,+c))++#+[('a',+2),+('b',+2.2),+('c',+'cat')]
tuple(A(a,+b,+c))+#+(('a',+2),+('b',+2.2),+('c',+'cat'))|1993266|只有当你试图将不可哈希的成员放到对象模型中时，事情才会崩溃：|1993267|hash(A(a,+b,+[1]))++#+TypeError:+unhashable+type:+'list'|1993268|entityMap|0|LINK|mutability|MUTABLE|url|https://docs.python.org/3/reference/datamodel.html#object.__iter__^0|R|8|R|8|0|0|0|8|6|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|12|8|@$9|13|A|14|B|C]]|D|@$9|15|A|16|1|17]]|E|$]]|$1|F|3|G|5|H|7|18|8|@]|D|@]|E|$I|J]]|$1|K|3|L|5|6|7|19|8|@$9|1A|A|1B|B|C]]|D|@]|E|$]]|$1|M|3|N|5|6|7|1C|8|@]|D|@]|E|$]]|$1|O|3|P|5|H|7|1D|8|@]|D|@]|E|$I|J]]|$1|Q|3|R|5|6|7|1E|8|@]|D|@]|E|$]]|$1|S|3|T|5|H|7|1F|8|@]|D|@]|E|$I|J]]|$1|U|3|-4|5|6|7|1G|8|@]|D|@]|E|$]]]|V|$W|$5|X|Y|Z|E|$10|11]]]]

A good way to implement hash (as well as list, dict, tuple) is to make the object have a predictable order of items by making it iterable using <a href="https://docs.python.org/3/reference/datamodel.html#object.__iter__" rel="nofollow noreferrer"><code>__iter__</code></a>. So to modify an example from above:
<pre><code>class A(object):

 def __init__(self, a, b, c):
 self._a = a
 self._b = b
 self._c = c

 def __iter__(self):
 yield &quot;a&quot;, self._a
 yield &quot;b&quot;, self._b
 yield &quot;c&quot;, self._c

 def __hash__(self):
 return hash(tuple(self))

 def __eq__(self, other):
 return (isinstance(other, type(self))
 and tuple(self) == tuple(other))
</code></pre>
(here <code>__eq__</code> is not required for hash, but it's easy to implement).
Now add some mutable members to see how it works:
<pre><code>a = 2; b = 2.2; c = 'cat'
hash(A(a, b, c)) # -5279839567404192660
dict(A(a, b, c)) # {'a': 2, 'b': 2.2, 'c': 'cat'}
list(A(a, b, c)) # [('a', 2), ('b', 2.2), ('c', 'cat')]
tuple(A(a, b, c)) # (('a', 2), ('b', 2.2), ('c', 'cat'))
</code></pre>
things only fall apart if you try to put non-hashable members in the object model:
<pre><code>hash(A(a, b, [1])) # TypeError: unhashable type: 'list'
</code></pre>

What's a correct and good way to implement <code>__hash__()</code>?

I am talking about the function that returns a hashcode that is then used to insert objects into hashtables aka dictionaries.

As <code>__hash__()</code> returns an integer and is used for "binning" objects into hashtables I assume that the values of the returned integer should be uniformly distributed for common data (to minimize collisions).
What's a good practice to get such values? Are collisions a problem?
In my case I have a small class which acts as a container class holding some ints, some floats and a string.

What's a correct and good way to implement __hash__()?

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

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

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

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

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

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

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

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

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

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

什么是实现__hash__()的正确且好的方法我说的是一个函数，它返回一个哈希码，然后用来将对象插入哈希表，也就是字典。由于__hash__()返回一个整数，并用于将对象“打包”到哈希表中，因此我假设返回的整数的值对于公共数据应该是均匀分布的(以最小化冲突)。获得这样的值的好做法是什么？碰撞是一个问题吗？在我的例子中，...

问实现hash()的正确和好的方法是什么？
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问实现__hash__()的正确和好的方法是什么？EN