Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Browse files

more tests, refined flat to use factors 1 through bound.

  • Loading branch information...
commit 8596dce1a605602550018131c332727883acb04b 1 parent cae9607
@scooby authored
Showing with 56 additions and 7 deletions.
  1. +16 −7 python/comp_hash.py
  2. +40 −0 python/test_words.py
View
23 python/comp_hash.py
@@ -1,15 +1,19 @@
"""
Experimenting with a composable hash for a rope class.
-What I need is for different orders of concatenations of different flats to not affect the hash value.
+What I need is for different orders of concatenations of different
+flats to not affect the hash value.
Requirements: h((a . b) . c) == h(a . (b . c))
Preferred: h(a . b) != h(b . a)
-Options: define h(expr) = f(g(expr), len(expr)), so that the length further hashes the result
+Options: define h(expr) = f(g(expr), len(expr)), so that the length
+ further hashes the result
"""
+import random as rn
+
def test(f, g, h):
a = "What I need is for different "
b = "orders of concatenations of different flats "
@@ -46,19 +50,24 @@ def test(f, g, h):
mask = (1 << 32) - 1
def flat(string):
+ """ Numbers are from 1 to bound. """
x = 1
for char in string:
- x = (x * (2 + ord(char))) % bound
+ x = ((x * (2 + ord(char))) - 1) % bound + 1
return x
def mult(hash_a, hash_b):
- return (hash_a * hash_b) % bound
+ """ Combine two hashes as though the flats had
+ been concatenated. """
+ return (hash_a * hash_b - 1) % bound + 1
def blorg(num, base=1627):
- """ Takes a value and gets something very large to xor against. """
+ """ Takes a value and gets something very large to xor
+ against. """
return pow(base, num, bound)
-def final(num, length):
- return (num ^ blorg(length + 4)) & mask
+def final(num, length, rand=rn.getrandbits(32)):
+ """ rand ensures that for any given session, hashes change. """
+ return (num ^ blorg(length + 4) ^ rand) & mask
print(test(flat, mult, final))
View
40 python/test_words.py
@@ -0,0 +1,40 @@
+prime_bound = (1 << 32) - 5
+pow_bound = 1 << 32
+mask = pow_bound - 1
+
+def flat(string):
+ """ Numbers are from 1 to bound. """
+ x = 1
+ for char in string:
+ x = ((x * (2 + ord(char))) - 1) % prime_bound + 1
+ return x
+
+def blorg(num, base=1627):
+ """ Takes a value and gets something very large to xor
+ against. """
+ return pow(base, num, pow_bound)
+
+def final(num, length, rand=rn.getrandbits(32)):
+ """ rand ensures that for any given session, hashes change. """
+ return (num ^ blorg(length + 4) ^ rand) & mask
+
+class word(str):
+ def __hash__(self):
+ return final(flat(self), len(self))
+
+words = set()
+strs = set()
+
+word_file = "/home/ben/tree"
+
+with open(word_file, "r") as fh:
+ words.update(word(line) for line in fh)
+
+with open(word_file, "r") as fh:
+ strs.update(fh)
+
+def compare(name, avast):
+ print("%s: %d elems, %s bytes" % (name, len(avast), avast.__sizeof__()))
+
+compare("words", words)
+compare("strs", strs)
Please sign in to comment.
Something went wrong with that request. Please try again.