the art of
Algorithm
Notes on Analysis and Design



Hash Functions

Hash Function The hash function will take any item in the collection and return an integer in the range of slot names, between 0 and m-1, m is size of Hash Table.

0 1 2 m-1 [0, 1, 2, , , , , ,m-1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
"""
Hash Function #1
Remainder Method
"""
def hash_rem(num, hash_table):
    return num % len(hash_table)

"""
Hash Function #2
Folding Method

Begins by dividing the item into equal-size pieces (the last piece may not be of
equal size). These pieces are then added together to give the resulting
hash value.
"""
def hash_fold(num, hash_table, folding_factor):
    num_list = list(str(num))
    temp_num_list = []
    i = 0

    while(i < len(num_list)):
        temp_str = ""
        for j in range(folding_factor):
            if i < len(num_list):
                temp_str += num_list[i]
                i += 1
            else:
                temp_str += '0'
        temp_num_list.append(temp_str)

    sum = 0
    for item in temp_num_list:
        sum += int(item)
    return sum % len(hash_table)

hash_fold(321313313, {'0' : '', '1' : '','2':'' }, 2)

"""
Hash Function #3
Mid-Square Method
"""
def hash_mid(num, hash_table, mid_square_factor):
    num_element = int(num) *  int(num)
    element = str(num_squared)[mid_square_factor[0]:mid_square_factor[1]]
    return int(element) % len(hash_table)

"""
Hash Function #4
Ordinal Values Method
"""
def hash_ord(string, hash_table):
    sum = 0
    for x in range(len(string)):
        sum += ord(string[x])
    return sum % len(hash_table)

"""
Hash Function #5
Weighted Ordinal Values Method
"""
def hash_ord_weighted(string, hash_table):
    sum = 0
    for x in range(len(string)):
        sum += (x+1)*ord(string[x])
    return sum % len(hash_table)