// hash.txt
// implement   hash by separate chaining

enum
	1999  TSIZE			// hash table size
enum
	#0ffffff MAXN		// max 24 bits

keybuffer = array 100

to init_hash | i =
	htab = array TSIZE
	for i 0 TSIZE-1
		htab[i] = NIL

to hash1 key | n i =
	str2array keybuffer key
	n = 0
	i = 0
	while keybuffer[i] != 0		// convert to number
		n = 37 * ((n + (keybuffer[i]-48)) % MAXN)
		i = i + 1
	n

to hash2 key | n i =
	str2array keybuffer key
	n = 0
	i = 0
	while keybuffer[i] != 0		// convert to number
		n = n + (keybuffer[i]-48)
		i = i + 1
	n

to hash key =
	(hash2 key) % TSIZE

to insert key | n a =
	n = hash key
	a = newNode key
	if htab[n] == NIL	// free
		htab[n] = newList a
	else				// occupied
		if ! (containsNode a htab[n])
			addNode a htab[n]

to find key | n a =
	n = hash key
	a = newNode key
	if htab[n] == NIL
		0
	else
		containsNode a htab[n]

// ---------- display ---------

to showKey el =
	if el != NIL
		prints head el  space
		showKey next el

to showHtab | i =
	for i 0 TSIZE-1
		if htab[i] != NIL
			showKey htab[i]  nl

// ---------- test ----------------

to testhash | a b c d =
	a = "11223344"
	b = "55667788"
	c = "22446688"
	d = "55778899"
//	print hash a nl
//	print hash b nl
//	print hash c nl
//	print hash d nl
	insert a
	insert b
	insert c
	insert d
	showHtab
	print find a nl
	print find "123" nl

to main =
	init_list
	init_hash
	testhash