Maglev Hashing with Python https://research.google.com/pubs/pub44824.html see also http://yunazuno.hatenablog.com/entry/2017/02/08/001605

maglev.py

import hashlib


class MaglevHash(object):
    def __init__(self, m=65537):
        self.m = m
        self.permutation = {}
        self.entry = [None] * self.m
        self.tainted = False

    def add(self, node):
        if node in self.permutation:
            raise KeyError("Node already exist")

        permutation = self._generate_permutation(node)
        self.permutation[node] = permutation
        self.tainted = True

    def remove(self, node):
        if node not in self.permutation:
            raise KeyError("Node not found")

        del(self.permutation[node])
        self.tainted = True

    def populate(self):
        entry = self._populate_entry()
        distance = [
            a == b for a, b in zip(self.entry, entry)].count(False)
        self.entry = entry
        self.tainted = False
        return distance

    def lookup(self, key):
        if self.tainted: self.populate() # auto populate.
        index_hash = hash(key.encode('ascii') + b':lookup')
        index = index_hash % self.m

        return self.entry[index]

    def _generate_permutation(self, node):
        offset_hash = hash(node.encode('ascii') + b':offset')
        offset = offset_hash % self.m
        skip_hash = hash(node.encode('ascii') + b':skip')
        skip = (skip_hash % (self.m - 1)) + 1

        permutation = [None] * self.m
        for j in range(self.m):
            permutation[j] = (offset + j * skip) % self.m

        return permutation

    def _populate_entry(self):
        if not self.permutation:
            return [None] * self.m, self.m

        next_tracker = dict.fromkeys(self.permutation.keys(), 0)
        entry = [None] * self.m

        n = 0
        while True:
            for node in sorted(self.permutation.keys()):
                c = self.permutation[node][next_tracker[node]]
                while entry[c] is not None:
                    next_tracker[node] += 1
                    c = self.permutation[node][next_tracker[node]]

                entry[c] = node
                next_tracker[node] += 1
                n += 1

                if n == self.m:
                    return entry