anti-hash.py

import time
import random
from collections import UserDict


class SafeDict(UserDict):
    RAND = random.randint(0, 2 ** 31)

    def __getitem__(self, k):
        return self.data[k ^ SafeDict.RAND]

    def __setitem__(self, k, v):
        self.data[k ^ SafeDict.RAND] = v

    def __contains__(self, k):
        return k ^ SafeDict.RAND in self.data


def create_hack(lo, hi, n, unique=False, CPython=False):
    pow2 = 2 ** ((hi - lo - 1).bit_length() - 1)
    if unique:
        pow2 //= 2

    def advance(x, perturb):
        if CPython:
            perturb >>= 5
        y = (5 * x + perturb + 1) % pow2
        if not CPython:
            perturb >>= 5
        return y, perturb

    def prime_dict(n):
        A = []

        i = perturb = hash(lo)
        i %= pow2
        for _ in range(min(n, pow2 // 2 - 10)):
            A.append(i + (lo + 1 - i + pow2 - 1) // pow2 * pow2)
            i, perturb = advance(i, perturb)

        assert all(lo <= x < hi for x in A)

        return A

    def attack_dict(priming_idx, n):
        # TODO: make sure resize does not occur

        A, B = [], []
        used = set()

        for i in range(lo, hi):
            if i in used or i in priming_idx:
                continue

            path = []
            h = perturb = hash(i)
            h %= pow2
            while perturb != 0:
                path.append(h)
                h, perturb = advance(h, perturb)

            if h not in priming_idx or priming_idx[h] > len(priming_idx) // 10:  # TODO: different thresholds
                continue
            if len(A) + len(B) + len(path) + 1 > n:
                break

            for j in path:
                j = j + (lo + 1 - j + pow2 - 1) // pow2 * pow2
                if j == i:
                    j = j - pow2 if j - pow2 >= lo else j + pow2
                if j not in priming_idx and j not in used:
                    A.append(j)
                    used.add(j)

            B.append(i)
            used.add(i)

        assert all(lo <= x < hi for x in A)
        assert all(lo <= x < hi for x in B)

        return A, B

    priming = prime_dict(n // 2)  # TODO: different splits
    if not unique:
        return priming, [lo] * (n - len(priming))

    priming_idx = SafeDict((j, i) for i, j in enumerate(priming))
    extra_priming, attack = attack_dict(priming_idx, n - len(priming))

    # NOTE: reordering priming will not lose any efficiency
    # NOTE: reordering attack will slightly lose efficiency (shouldn't be noticable)
    return priming + extra_priming, attack


start = time.time()
priming, attack = create_hack(1, 10 ** 7, 2 * 10 ** 5, True, False)
priming.sort()
print("generation", time.time() - start, len(priming) + len(attack))

start = time.time()
d = {}
for i in priming:
    d[i] = 1
for i in attack:
    d[i] = 0
print("attack", time.time() - start)