Limit for hashing nested tuples?

Question

A few lines of code that demonstrates what I'm asking are:

>>> x = ()
>>> for i in range(1000000):
...     x = (x,)


>>> x.__hash__()

=============================== RESTART: Shell ===============================

The 1000000 may be excessive, but it demonstrates that there is some form of limit when hashing nested tuples (and I assume other objects). Just to clarify, I didn't restart the shell, it did that automatically when I attempted the hash.

What I want to know is what is this limit, why does it happen (and why did it not raise an error), and is there a way around it (so that I can put tuples like this into sets or dictionaries).

stybl, is it not allowed to have "restart shell"? I need it to show what happens, and now it's not clear. — stanley dodds, Jul 11 '17 at 10:12
in my case the result was `Segmentation fault (core dumped)` and an exit from the python shell (python 3.5 on ubuntu) — Ofer Sadan, Jul 11 '17 at 10:14
Interesting. I'm using python 3.5.2 on windows 10, and for me it just restarts the shell each time as shown — stanley dodds, Jul 11 '17 at 10:18
It is very fascinating. It seems to heavily depend on your system. On my windows PC I the largest number of nested tuples I could get to was 41882, but my linux machine had no problem going above 80000. — stelioslogothetis, Jul 11 '17 at 10:20

score 4 · Accepted Answer · answered Jul 11 '17 at 10:18

The __hash__ method of tuple calculates the hash of each item in the tuple - in your case like a recursive function. So if you have a deeply nested tuple then it ends up with a very deep recursion. At some point there is probably not enough memory on the stack to go "one level deeper". That's also why the "shell restarts" without Python exception - because the recusion is done in C (at least for CPython). You could use, i.e. gdb to get more information about the exception or debug it.

There will be no global hard limit, the limit depends on your system (e.g. how much stack) and how many function calls (internally) are involved and how much of the "stack" each function call requires.

However that could qualify as Bug in the implementation, so it would be a good idea to post that on the Python issue tracker: CPython issue tracker.

So because of this I assume that there is no way to put an object like this into a set or use it as a dictionary key? — stanley dodds, Jul 11 '17 at 10:30
@stanleydodds In the specific case you mentioned: no. As soon as Python wants to calculate the `hash` of that tuple the interpreter will segfault. Note that you also have a problem when you want to do other operations, for example: `print(x)`, which leads to a similar problem. However the `__str__` method is recursion-aware and therefore gives `RecursionError: maximum recursion depth exceeded while getting the repr of a tuple`. — MSeifert, Jul 11 '17 at 10:35

Limit for hashing nested tuples?

1 Answers1