Skip to content

Instantly share code, notes, and snippets.

@yunazuno
Last active July 5, 2023 12:29
Show Gist options
  • Save yunazuno/f98c0bb176c9bf4934511dac60d7ea0b to your computer and use it in GitHub Desktop.
Save yunazuno/f98c0bb176c9bf4934511dac60d7ea0b to your computer and use it in GitHub Desktop.
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
@alexei-grigoriev
Copy link

Hello,
I came across this implementation of maglev hashing and want to use it for some private research. However, I would be able to use it only if it is licensed as open source (e.g Apache, MIT etc.). Would You be able mention the license somewhere in comments?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment