-
Notifications
You must be signed in to change notification settings - Fork 3
Expand file tree
/
Copy pathhashing.py
More file actions
95 lines (81 loc) · 2.89 KB
/
Copy pathhashing.py
File metadata and controls
95 lines (81 loc) · 2.89 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
84
85
86
87
88
89
90
91
92
93
94
95
# hashing with resizing
class HashData:
def __init__(self,id,*values):
self.id = id
self.values = values
def __str__(self):
return self.id + str(self.values)
def __repr__(self):
return self.id + str(self.values)
class HashTable:
def __init__(self,size):
self.size = size
self.buckets = [[] for e in range(size)]
def generate_hash(self,k):
s = sum([ord(e) for e in k])
hash_index = s % self.size
return hash_index
def resize(self):
self.size = self.size * 2
self.new_bucket = [ [] for e in range(self.size)]
for i, bucket in enumerate(self.buckets):
if bucket:
index = self.generate_hash(bucket[0].id)
self.new_bucket[index] = bucket
print(f"old bucket {self.buckets} new bucket {self.new_bucket}")
self.buckets = self.new_bucket
def insert_data(self,k):
if -1 == self.retrieve_data(k.id):
self.buckets[self.generate_hash(k.id)].append(k)
op = sum([1 for x in self.buckets if x])
if op > self.size * 0.6:
# trigger resize
print("triggered resize")
self.resize()
def remove_data(self,k):
if -1 != self.retrieve_data(k.id):
print("removing ",k)
bucket = self.buckets[self.generate_hash(k.id)]
for i, e in enumerate(bucket):
if k.id == e.id:
print("removing inside loop",k)
bucket.pop(i)
def update_data(self,k):
self.remove_data(k)
self.buckets[self.generate_hash(k.id)].append(k)
def retrieve_data(self,k):
bucket = self.buckets[self.generate_hash(k)]
for e in bucket:
if k == e.id:
return e
return -1
if __name__ == "__main__":
o = HashTable(12)
hd = HashData("prem","email","phone")
o.insert_data(hd)
# o.insert_data("prem")
hd = HashData("prem","fax","bra","penty")
o.insert_data(HashData("prem","fax","bra","penty"))
ash = HashData("seema","ashim")
o.insert_data(ash)
ash = HashData("seema45","ashim")
o.insert_data(ash)
print(o.buckets)
# o.insert_data("seema")
# o.remove_data(ash)
o.update_data(hd)
print(o.buckets)
print(o.retrieve_data("prem"))
print(o.retrieve_data("aseem1"))
# o.resize()
ash = HashData("zebra","ashim")
o.insert_data(ash)
print(o.buckets)
o.insert_data(HashData("prem1","fax","bra","penty"))
o.insert_data(HashData("prem2","fax","bra","penty"))
o.insert_data(HashData("prem3","fax","bra","penty"))
o.insert_data(HashData("prem4","fax","bra","penty"))
o.insert_data(HashData("prem5","fax","bra","penty"))
o.insert_data(HashData("prem6","fax","bra","penty"))
o.insert_data(HashData("prem7","fax","bra","penty"))
o.insert_data(HashData("prem8","fax","bra","penty"))