-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathHashing.py
More file actions
83 lines (61 loc) · 1.76 KB
/
Hashing.py
File metadata and controls
83 lines (61 loc) · 1.76 KB
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
## the demonstration of Hashing functionalities,
# assuming the key to be stirng
class HashItem():
"""This represent one single item in the hashtable"""
def __init__(self, key, value):
self.key = key
self.value = value
class HashTable(object):
"""This class represent our HashTable
size of the hash table has been taken to 256 item currently"""
def __init__(self, ):
# super(HashTable, self).__init__()
self.size = 256
self.slots = [None for i in range(self.size)]
self.count = 0
def _hash(self, key):
"""It is assumed that key will of type string only and this hash is
base on this assumption"""
mult =1
hv = 0
for ch in key:
hv += mult*ord(ch)
mult += 1
return hv % self.size
def put(self, key, value):
"""
we are going to resolve the collision by adding one to the previos hash value we
had and getting the remainder dividing this value by the size of the hash table.
This is a linear way of resolving collision
"""
item = HashItem(key, value)
h = self._hash(key)
while self.slots[h] is not None:
if self.slots[h].key == key:
break
h = (h+1) % self.size
if self.slots[h] is None:
self.count += 1
self.slots[h] = item
def get(self, key):
h = self._hash(key)
while self.slots[h] is not None:
if self.slots[h].key == key:
return self.slots[h].value
h = (h+1) % self.size
return None
def __getitem__(self, key):
return self.get(key)
def __setitem__(self, key, value):
self.put(key, value)
def test():
ht = HashTable()
ht['good']= 'eggs'
ht['better']= 'ham'
ht['best']= 'spam'
# for these the collision of has will occur and will be resolve using linear
ht['ad`']= 'do not'
ht['ga']= 'collide'
for key in ['good', 'better', 'best', 'worst', 'ad`','ga']:
print(ht[key])
test()