Create a gist now

Instantly share code, notes, and snippets.

@yokamaru /maglev.py
Last active Jul 23, 2017

What would you like to do?
import hashlib
class MaglevHash(object):
def __init__(self, m=65537):
self.m = m
self.permutation = {}
self.entry = [None] * self.m
def add(self, node):
if node in self.permutation.keys():
raise KeyError("Node already exist")
permutation = self._generate_permutation(node)
self.permutation[node] = permutation
def remove(self, node):
if node not in self.permutation.keys():
raise KeyError("Node not found")
del self.permutation[node]
def populate(self):
entry = self._populate_entry()
distance = [
a == b for a, b in zip(self.entry, entry)].count(False)
self.entry = entry
return distance
def lookup(self, key):
index_hash = int(hashlib.sha256(
"{}:lookup".format(key).encode("ascii")).hexdigest(), 16)
index = index_hash % self.m
return self.entry[index]
def _generate_permutation(self, node):
offset_hash = int(hashlib.sha256(
"{}:offset".format(node).encode("ascii")).hexdigest(), 16)
offset = offset_hash % self.m
skip_hash = int(hashlib.sha256(
"{}:skip".format(node).encode("ascii")).hexdigest(), 16)
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment