Linear hashing example

lintest.py

import collections
import random

i = 0
n = 0

d = [collections.OrderedDict()]

def lin(k):
	global i
	global n
	x = k % (2 ** i)
	if x < n:
		x = k % (2 ** (i + 1))
	return x

def split():
	global i
	global n
	global d
	oldi = n
	oldb = d[oldi]
	newb = collections.OrderedDict()
	if n >= 2**i - 1:
		i += 1
		n = 0
	else:
		n += 1
	for k in list(oldb):
		kk = lin(k)
		if kk != oldi:
			newb[k] = oldb[k]
			del oldb[k]
	d.append(newb)

since_last_split = 0
for a in xrange(0, 10000):
	for z in xrange(0, 100):
		key = random.randint(0, 2**64)
		num = lin(key)
		bucket = d[num]
		bucket[key] = 'value %d' % key
		if len(d[n]) > 70:
			split()
			print len(d), ',', since_last_split
			since_last_split = 0
		else:
			since_last_split += 1