Skip to content

Instantly share code, notes, and snippets.

@c7h c7h/gist:8670768
Last active Jan 4, 2016

Embed
What would you like to do?
Hashmap Example - Understanding Hashmap - linear probing
#!/usr/bin/env python
#Hashmap example
#Author: Christoph Gerneth
#usage: python ordinal-hashmap.py map-size x y STR_1 [STR_2 STR_3 .. STR_N]
#x and y are K_x K_y (Glaviner Standard values for Hashfunction
#example python ordinal-hash.py 13 1 3 Petrus Andreas Jakobus Johannes Phillippus Bartholomaus Thomas Matthaus Jakobus Thaddaus Simon Judas
import sys
debug=True
chars_start = int(sys.argv[2])
chars_end = int(sys.argv[3])
string_list = sys.argv[4:]
mod = int(sys.argv[1])
if debug==True:
print "modulo", mod
arr = [None]*mod
def insertInMap(key, value):
if arr.count(None) == 0:
raise mapFullException("Hashmap ist voll")
if arr[key]==None:
if debug==True:
print "insert value %s into place %i" % (value, key)
print
arr[key] = value
else:
if debug==True:
print "collison! place %i is occupied [%s]..." % (key, arr[key])
insertInMap( (key+1)%mod, value)
for string in string_list:
h=0
for char in string[chars_start:chars_end].upper():
h += ord(char)-64
key = h % mod
if debug==True:
print "key for %s is %2i" % (string, key)
try:
insertInMap(key, string)
except:
print "map is full"
break
print "resulting Hashmap"
for k, v in enumerate(arr):
print k, "=>", v
class mapFullException(Exception):
pass
@c7h

This comment has been minimized.

Copy link
Owner Author

commented Jan 30, 2014

python ordinal-hash.py 13 0 2 Petrus Andreas Jakobus Johannes Philippus Bartholomäus Thomas Matthäus Jakobus_junior Thaddäus Simon Judas

modulo 13
key for Petrus is 8
insert value Petrus into place 8

key for Andreas is 2
insert value Andreas into place 2

key for Jakobus is 11
insert value Jakobus into place 11

key for Johannes is 12
insert value Johannes into place 12

key for Philippus is 11
collison! place 11 is occupied [Jakobus]...
collison! place 12 is occupied [Johannes]...
insert value Philippus into place 0

key for Bartholomäus is 3
insert value Bartholomäus into place 3

key for Thomas is 2
collison! place 2 is occupied [Andreas]...
collison! place 3 is occupied [Bartholomäus]...
insert value Thomas into place 4

key for Matthäus is 1
insert value Matthäus into place 1

key for Jakobus_junior is 11
collison! place 11 is occupied [Jakobus]...
collison! place 12 is occupied [Johannes]...
collison! place 0 is occupied [Philippus]...
collison! place 1 is occupied [Matthäus]...
collison! place 2 is occupied [Andreas]...
collison! place 3 is occupied [Bartholomäus]...
collison! place 4 is occupied [Thomas]...
insert value Jakobus_junior into place 5

key for Thaddäus is 2
collison! place 2 is occupied [Andreas]...
collison! place 3 is occupied [Bartholomäus]...
collison! place 4 is occupied [Thomas]...
collison! place 5 is occupied [Jakobus_junior]...
insert value Thaddäus into place 6

key for Simon is 2
collison! place 2 is occupied [Andreas]...
collison! place 3 is occupied [Bartholomäus]...
collison! place 4 is occupied [Thomas]...
collison! place 5 is occupied [Jakobus_junior]...
collison! place 6 is occupied [Thaddäus]...
insert value Simon into place 7

key for Judas is 5
collison! place 5 is occupied [Jakobus_junior]...
collison! place 6 is occupied [Thaddäus]...
collison! place 7 is occupied [Simon]...
collison! place 8 is occupied [Petrus]...
insert value Judas into place 9

resulting Hashmap
0 => Philippus
1 => Matthäus
2 => Andreas
3 => Bartholomäus
4 => Thomas
5 => Jakobus_junior
6 => Thaddäus
7 => Simon
8 => Petrus
9 => Judas
10 => None
11 => Jakobus
12 => Johannes

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.