Hashing

In [1]:
ord("A")
Out[1]:
65
In [2]:
ord("a")
Out[2]:
97

Create our hash table data structure

In [3]:
tablesize = 11

First attempt at hashing

In [4]:
def hash(astring, tablesize):
    """Basic hashing with weighted ordinal values"""
    sum_ = 0
    for i,c in enumerate(astring, start=1):
        sum_ += ord(c)
    return sum_%tablesize
In [5]:
hash("cat", tablesize)
Out[5]:
4
In [6]:
hash("act", tablesize)
Out[6]:
4

Second attempt at hashing, with weighting

In [17]:
def hash(astring, tablesize):
    """Basic hashing with weighted ordinal values"""
    sum_ = 0
    for i,c in enumerate(astring, start=1):
        sum_ += ord(c)*i
    print(f"The sum of {astring} is {sum_}")
    return sum_%tablesize
In [18]:
hash("cat", tablesize)
The sum of cat is 641
Out[18]:
3
In [19]:
hash("act", tablesize)
The sum of act is 643
Out[19]:
5

Casual testing of this hash setup

In [12]:
wordlist = ["cat", "act", "tac", "bat"]
In [13]:
ht = [None] * tablesize
print(ht)

for word in wordlist:
    hv = hash(word, tablesize)
    ht[hv] = word
    print(ht)
[None, None, None, None, None, None, None, None, None, None, None]
[None, None, None, 'cat', None, None, None, None, None, None, None]
[None, None, None, 'cat', None, 'act', None, None, None, None, None]
[None, None, 'tac', 'cat', None, 'act', None, None, None, None, None]
[None, None, 'bat', 'cat', None, 'act', None, None, None, None, None]
In [20]:
print(hash("tac", tablesize))
print(hash("bat", tablesize))
The sum of tac is 607
2
The sum of bat is 640
2
In [21]:
print(77%11, 55%11, 44%11)
0 0 0