Home » programming » Part of exercise 12.4-1 in CLR

Part of exercise 12.4-1 in CLR

For CLR, exercise 12.4-1 in case you are lazy to do the math.

from __future__ import print_function

def quadratic_probing(k, i, m, h1, c1, c2):
	return (k + h1(k, m) + c1 * i + c2 * i**2) % m

def double_hashing(k, i, m, h1, h2):
	return ((h1(k, m) + i * h2(k, m))) % m

def main():
	m = 11
	k = input("Insert next key (k): ")
	print("Printing the first 10 possible positions for the key...")
	print("quadratic_probing")
	for i in range(10):
		print(quadratic_probing(k, i, m, lambda k, m: k % m, 1, 3))
	print("quadratic_probing")
	for i in range(10):
		print(double_hashing(k, i, m, lambda k, m: k % m, lambda k, m: 1 + (k % (m - 1))))

if __name__ == '__main__':
	main()

The code snippet does not generate the solutions though because it is instructive to see how the table gets different by using different methods of collision resolution.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: