(Integer antihash hack) Sets and dictionaries run in O(n^2) time
A couple of days ago, there was a blog post about how to make Python dictionaries and sets run in O(n^2). Turns out it is super easy to construct it, and all versions of Python that I know of are affected (in particular PyPy2 and PyPy3).
The following is my implementation of the hack:
def anti_hash_hack(n):
"""
Input: integer n > 0
Output: List A of length n
such that 0 <= A[i] <= 2**(n.bit_length() + 2)
"""
pow2 = 2**(n.bit_length() + 2)
A = [pow2]
i = 1
while len(A) < n//2:
A.append(i)
i = (5 * i + 1) % pow2
while len(A) < n:
A.append(0)
return A
n = 123456
A = anti_hash_hack(n)
print("Creating set:")
set(A)
print("Done")
print("Creating dict:")
my_dict = {}
for i in range(n):
my_dict[A[i]] = i
print("Done")
Locally in PyPy3 creating the set (of size n = 123456
) takes 7.5 s, and creating the dictionary (of size n = 123456
) also takes 7.5 s. In CPython3 creating the set is almost instant, but creating the dictionary takes 11 s. From what I understand, sets in CPython can still be antihash hacked, but you need a slightly different hack for that.
For my usage of Python, hash tables being easily hackable is a deal breaker. I get that this is more of an issue with Python itself than with PyPy, but I still would like to hear your opinion of this. My questions are:

Should this / will this ever be fixed? For example adding some kind of random element to the integer hashing would fix this. Or will Python always have broken hash tables?

What is the best work around? The best work around I could come up with is:
import random
RANDOM = random.randrange(2**62)
...
n = 123456
A = anti_hash_hack(n)
set([a ^ RANDOM for a in A])
While this is the best work around that I could think of, it also makes the code a mess. So I really don't want to have to do this.