Entering two keys with the same hash in dict

Question

>>> one_decimal = Decimal('1') >>> one_complex = complex(1,0) >>> d = {one_decimal: '1D', one_complex: '1C'} >>> map(hash, d) [1, 1] 

Why does dict allow multiple slots to be used if these key hashes are the same?

 >>> d[1] '1D' >>> d[1+0j] '1C' 

And how does indexing solve the right value for complex literal indexing? Why are these numbers not equal equal when they are int(1) equal?

Python 2.7.12.

Answer 1

As the accepted answer mentioned by @CoryKramer states, hash equality does not mean equality of objects. Python dictionaries can contain any number of elements with equal hashes if the objects themselves are not equal.

The short answer to your question is probably that the implementation of complex bit incomplete in the Python library since version 2.7. As @wim points out, comparing int and complex using == works fine, but comparing Decimal and complex fails. Since comparing one_decimal == one_complex will always return False due to their types, they can live in the same dictionary in Python 2.7.

This problem is fixed in Python 3. I am experimenting in 3.5 where one_decimal and one_complex are equal. After starting the same fragment, the dictionary contains the value one_complex under the key one_decimal , as expected (first key, last value).

TL; DR

This is a bug in the Py2.7 complex . Fixed in Py3.

Answer 2

The problem is only when using a decimal number with a complex number. Float's, int, etc. They work fine because they are forced to compare.

In python3, the decimal library, compared to the complex number, is specially handled in _convert_for_comparison :

  # Comparisons with float and complex types. == and != comparisons # with complex numbers should succeed, returning either True or False # as appropriate. Other comparisons return NotImplemented. if equality_op and isinstance(other, _numbers.Complex) and other.imag == 0: other = other.real 

In python2 convert , a function is implemented:

 def _convert_other(other, raiseit=False, allow_float=False): """Convert other to Decimal. Verifies that it ok to use in an implicit construction. If allow_float is true, allow conversion from float; this is used in the comparison methods (__eq__ and friends). """ if isinstance(other, Decimal): return other if isinstance(other, (int, long)): return Decimal(other) if allow_float and isinstance(other, float): return Decimal.from_float(other) if raiseit: raise TypeError("Unable to convert %s to Decimal" % other) return NotImplemented 

Why len(set([1, Decimal('1'), (1+0j)])) == 2 is because Decimal is compared with int first, if you change the order, you get a different result:

 In [23]: {1, Decimal('1'), (1+0j)} Out[23]: {(1+0j), Decimal('1')} In [24]: {Decimal('1'),1, (1+0j)} Out[24]: {(1+0j), Decimal('1')} In [25]: {Decimal('1'), (1+0j), 1} Out[25]: {1} 

In addition, using a literal is better, since the order that you insert matches the documents, since the last value is saved using the literal above the set (..).

Answer 3

Why does the dict allow the use of multiple slots when these keys hash the same?

TL; DR; Since there are hash collisions

If two key hashes have the same value, the only way to determine if these keys are equal is to compare them. If the comparison evaluates to false, then the dict creates several slots for the key values; otherwise, the value for the key is overwritten with the new value

And how does indexing solve the right value for complex literal indexing? Why don't these numbers compare the same when they are int (1)?

Python uses duck printing to determine the type of value. With this in mind, since the values ​​themselves do not explicitly indicate what type they are, I believe that dict internally checks the types of objects before trying to compare them. The Python duck printing system allows us to conclude that the first is Decimal and the second is a complex type. Assuming this is taken into account before the values ​​are compared, then they will always lead to hashing in different buckets, even if they are “equal”

The reason for this is that the __eq__ method for both classes does not evaluate to true when they are both compared inside the dict object