1.1 --- a/src/chaining_hash.py	Mon Jun 20 20:29:03 2011 +0200
     1.2 +++ b/src/chaining_hash.py	Tue Jun 21 15:21:25 2011 +0200
     1.3 @@ -6,8 +6,8 @@
     1.4      args = parse_arguments()
     1.5      table = {}
     1.6      for key in args.values.split():
     1.7 -        table = chained_hash(int(key), table, int(args.table_size))
     1.8 -    for k in range(int(args.table_size)):
     1.9 +        table = chained_hash(int(key), table, args.table_size)
    1.10 +    for k in range(args.table_size):
    1.11          if k not in table:
    1.12              table[k] = []
    1.13          print "%i: %s" % (k, table[k])
    1.14 @@ -24,7 +24,7 @@
    1.15  
    1.16  def parse_arguments():
    1.17      parser = ArgumentParser(description="")
    1.18 -    parser.add_argument("table_size", help="size of the hash table")
    1.19 +    parser.add_argument("table_size", type=int, help="size of the hash table")
    1.20      parser.add_argument("values", help="values")    
    1.21      return parser.parse_args()
    1.22  

     2.1 --- a/src/double_hash.py	Mon Jun 20 20:29:03 2011 +0200
     2.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.3 @@ -1,39 +0,0 @@
     2.4 -"""
     2.5 -Name: string_hash -  a string hashing program
     2.6 -Description: Basic string hashing program according to Theory I lecture.
     2.7 -Author: Eugen Sawin <sawine@informatik.uni-freiburg.de>
     2.8 -"""
     2.9 -
    2.10 -def main():    
    2.11 -    args = parse_arguments()
    2.12 -    used = set()
    2.13 -    for key in args.values.split():
    2.14 -        print "%s: %i" % (key, double_hash(int(key), used))
    2.15 -
    2.16 -def double_hash(k, used):
    2.17 -    j = 0
    2.18 -    code = (h(k) - s(j, k)) % 15
    2.19 -    while code in used:
    2.20 -        j += 1
    2.21 -        code = (h(k) - s(j, k)) % 15
    2.22 -    used.add(code)
    2.23 -    return code
    2.24 -
    2.25 -def s(j, k):
    2.26 -    return j * h2(k)
    2.27 -
    2.28 -def h(k):
    2.29 -    return k % 15
    2.30 -
    2.31 -def h2(k):
    2.32 -    return 1 + (k % 13) 
    2.33 -
    2.34 -from argparse import ArgumentParser
    2.35 -
    2.36 -def parse_arguments():
    2.37 -    parser = ArgumentParser(description="Returns the hash for given string using the double-hash technique.")
    2.38 -    parser.add_argument("values", help="values")    
    2.39 -    return parser.parse_args()
    2.40 -
    2.41 -if __name__ == "__main__":
    2.42 -    main()

     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/src/open_addressing.py	Tue Jun 21 15:21:25 2011 +0200
     3.3 @@ -0,0 +1,60 @@
     3.4 +"""
     3.5 +Author: Eugen Sawin <sawine@informatik.uni-freiburg.de>
     3.6 +"""
     3.7 +import math
     3.8 +
     3.9 +def main():    
    3.10 +    args = parse_arguments()
    3.11 +    if args.d:
    3.12 +        probe = double_hash
    3.13 +    elif args.l:
    3.14 +        probe = linear_probing
    3.15 +    elif args.q:
    3.16 +        probe = quadratic_probing
    3.17 +    else:
    3.18 +        print "you need to select a probing procedure"
    3.19 +        exit()
    3.20 +    table = {}
    3.21 +    for key in args.values.split():
    3.22 +        table = hash(int(key), args.table_size, table, probe)
    3.23 +    for k, v in table.iteritems():      
    3.24 +        print "%i: %i" % (k, v)
    3.25 +    #print "%s: %i" % (key, double_hash(int(key), used))
    3.26 +
    3.27 +def hash(k, size, table, probe):
    3.28 +    j = 0
    3.29 +    code = h(k, size) % size
    3.30 +    while code in table:
    3.31 +        j += 1
    3.32 +        code = (h(k, size) - probe(j, k, size)) % size
    3.33 +    table[code] = k
    3.34 +    return table
    3.35 +
    3.36 +def linear_probing(j, k, size):
    3.37 +    return j
    3.38 +
    3.39 +def quadratic_probing(j, k, size):
    3.40 +    return (-1)**j * math.ceil(j/2.0)**2
    3.41 +
    3.42 +def double_hash(j, k, size):
    3.43 +    return j * h2(k, size)
    3.44 +
    3.45 +def h(k, size):
    3.46 +    return k % size
    3.47 +
    3.48 +def h2(k, size):
    3.49 +    return 1 + (k % (size - 2)) 
    3.50 +
    3.51 +from argparse import ArgumentParser
    3.52 +
    3.53 +def parse_arguments():
    3.54 +    parser = ArgumentParser(description="Returns the hash for given string using the double-hash technique.")
    3.55 +    parser.add_argument("table_size", type=int, help="size of the hash table")
    3.56 +    parser.add_argument("values", help="values")    
    3.57 +    parser.add_argument("-d", action="store_true", help="double hashing")
    3.58 +    parser.add_argument("-l", action="store_true", help="linear probing")
    3.59 +    parser.add_argument("-q", action="store_true", help="quadratic probing")
    3.60 +    return parser.parse_args()
    3.61 +
    3.62 +if __name__ == "__main__":
    3.63 +    main()