Putting two keys with the same hash into a dict

Question

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

Above, I create a dict with a hash collision, and two slots occupied.

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

How is that getitem handled for the integer 1? And how does the indexing manage to resolve the correct value for a complex literal indexing?

Python 2.7.12 / Linux.

Python can [handle hash collisions](https://stackoverflow.com/questions/9010222/how-can-python-dict-have-multiple-keys-with-same-hash). [Further reading](http://www.shutupandship.com/2012/02/how-hash-collisions-are-resolved-in.html) — Cory Kramer, Oct 24 '16 at 18:56
What bothers me more than the hash collision is that `one_decimal == one_complex` is `True`. — Mad Physicist, Oct 24 '16 at 18:57
Interesting that this does **not** work in Py3 exactly because of that. — Mad Physicist, Oct 24 '16 at 19:04
More fun: `len(set([Decimal('1'), (1+0j)]))` is 2, but `len(set([1, Decimal('1'), (1+0j)]))` is 1. — wim, Oct 24 '16 at 19:12
I think you should take a look at: [Laurent Luce's Blog on *Python dictionary implementation*](http://www.laurentluce.com/posts/python-dictionary-implementation/) — Moinuddin Quadri, Oct 24 '16 at 19:13
@wim: that one is fit for one of those "wat!" talks at conferences — RemcoGerlich, Oct 24 '16 at 19:14
@wim. That's because equality is implemented between complex and normal datatypes correctly and the set compares against the first element that goes in. Basically, Decimal and complex are compared against a Python int, not against eachother. — Mad Physicist, Oct 24 '16 at 19:14
So, you are in fact asking why `1 == one_complex` and `1 == one_decimal`, but `one_complex != one_decimal`? Why don't you just say so then? ;) — zvone, Oct 24 '16 at 19:27
@zvone. It's called a minor bug. Most likely not much of a deeper explanation there. — Mad Physicist, Oct 24 '16 at 19:30
@zvone It's more interesting (for the reader) if we start with the consequences. — wim, Oct 24 '16 at 19:31
Regarding the 'correct' resolution of the values, this is just to do with insertion order. `one_decimal` is inserted first and lands at slot 1. `one_complex` can't go at slot one and lands in slot 6 instead. Try flipping the order: `d2 = {one_complex: '1C', one_decimal: '1D'}`. Then `d2[1]` is `'1C'` as well. — Alex Riley, Oct 24 '16 at 19:41

score 6 · Accepted Answer · edited Jun 20 '20 at 09:12

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

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

This issue has been fixed in Python 3. I am experimenting in 3.5, where one_decimal and one_complex are equal. After running the same snippet, the dictionary contains the value for one_complex under the key one_decimal, as expected (first key, last value).

TL;DR

It's a bug in Py2.7's complex type. Fixed in Py3.

score 3 · Answer 2 · edited May 23 '17 at 12:07

The problem is only when using a Decimal with a complex number. Float's, int's etc. work fine as they are coerced for comparison.

In python3's decimal lib comparing to a complex number is handled specifically 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 the convert function implementation is:

def _convert_other(other, raiseit=False, allow_float=False):
    """Convert other to Decimal.

    Verifies that it's 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 the Decimal is compared to the int first, if you change the ordering you get different output:

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}

Also using a literal is better as the order you insert matches the docs, as in the last value is preserved using a literal over the set(..).

Putting two keys with the same hash into a dict

2 Answers2

TL;DR

Linked