ZTCG81m7

1"""
2file: hash.py:
3language: python3
4author: dhd5076@rit.edu Dylan H Dunn
5description: This file contains 5 different hashing functions. Each hashing function is used to create a hash table,
6afterwards their performance in getting and putting value is compared using a given list of values to input.
7"""
8from time import *
9from math import *
10from random import *
11from hashtable import *
12from test_hashes import *
13
14
15def always_hashes_to_zero(key):
16    """An outstandingly bad hash function; it always returns 0.
17
18    :param key: The string to hash
19    :return: The hashed value
20    """
21    return 0
22
23
24def add_ordinal_values(key):
25    """Add ordinal values, Adds the ordinal values of a string together to get a hash.
26
27    :param key: The string to hash
28    :return: The hashed value
29    """
30    return sum(ord(char[0]) for char in key)
31
32
33def pow_ordinal_values(key):
34    """Hashes the string given by summing the ordinal values of the string given to the power of themselves.
35
36    :param key: The string to hash
37    :return: The hashed value
38    """
39    return int(sum((pow(ord(char[0]), ord(char[0])) * 3) for char in key))
40
41
42def good_hash_func(key):
43    """Sums the ordinal value of each character in the string times 31 to the power of the length of the string minus
44    the position of that character in the string.
45
46    :param key: The string to hash
47    :return: The hashed value
48    """
49    return int(sum(ord(key[x]) * pow(31, len(key) - x) for x in range(len(key))))
50
51
52def my_hash_func(key):
53    """A hash function that exploits the even distribution of the random function. This hash function should be really
54    good at evenly distributing the elements in the table, minimizing the number of collisions. Much like
55    more complex hashing functions, tiny changes given a drastically different value. Additionally, The output is
56    standardized to a length n where n is the upper bounds of the random function at the former part of the return.
57    Lastly, since we can seed the random function it allows us to make sure our code is consistent and gives the same
58    output each time for the same input.
59
60    :param key: The string to hash
61    :return: The hashed value
62    """
63    return randint(0, 1000) if not seed(sum(ord(x) % 12 for x in key)) else None
64
65
66def put_count(hTable, key, value):
67    """
68    put: HashTable(K, V) K V -> Boolean
69
70    Using the given hash table, set the given key to the
71    given value. If the key already exists, the given value
72    will replace the previous one already in the table.
73    If the table is full, an Exception is raised.
74    """
75    count = 0
76    index = hTable.hash_func(key) % hTable.capacity
77    startIndex = index  # We must make sure we don't go in circles.
78    while hTable.table[index] != None and hTable.table[index].key != key:
79        index = (index + 1) % hTable.capacity
80        if index == startIndex:
81            raise Exception("Hash table is full.")
82        count += 1
83    if hTable.table[index] is None:
84        hTable.table[index] = Entry(key, value)
85        hTable.size += 1
86    else:
87        hTable.table[index].value = value
88    return count
89
90
91def tst_hfuncs(keys, funcs):
92    """Evaluates the function's efficiency in adding the keys to the hash table. Both in its speed and amount of tries
93    it takes to find an open space in the table; how good is is at preventing collisions.
94
95    :param keys: A python list of keys to put into the hash table
96    :return:
97    """
98    for func in funcs:
99        hash_table = createHashTable(func, len(keys))
100        start = clock()
101        print("\nEvaluating " + func.__name__ + "\n\t" +
102              "Average length of linear search: " +
103              str(float(sum(put_count(hash_table, key, key) for key in keys)) / len(keys)) + "\n\t"
104              "Inserted " + str(len(keys)) + " items into the hashtable in " + str(clock() - start) + " seconds" +
105              "\n\t")
106        test_hash_func(func)
107
108
109def main():
110    """Entry point to the program, gets input from the user and then tests the hash functions
111
112    """
113    fp = open(input("Enter the name of the key file: "))
114    tst_hfuncs(list([fp.readline().strip() for x in range(int(input("Enter the capacity of the table: ")))]), \
115               [always_hashes_to_zero, add_ordinal_values, pow_ordinal_values, good_hash_func, my_hash_func])
116    fp.close()
117
118
119if __name__ == "__main__":
120    main()
121
122
123"""
124The real worst hash function would do it in O(g(n)) time where g is 3↑^g(n-1)3 and g(1) = 3↑↑↑↑3 and returns 0. If
125you wrote a function that could break that hash quickly enough you'd have an insta_graham_cracker() | goo.gl/2eDuz6
126"""