-
Notifications
You must be signed in to change notification settings - Fork 42
/
open_addressing.py
90 lines (67 loc) · 2.34 KB
/
open_addressing.py
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
class HashTable:
def __init__(self):
self.size = 13
self.n = 4
self.count = 0
self.load = 0.6
self.table = [None]*self.size
def __nextPrime(self):
self.size = 2**self.n -1
self.n += 1
def __hash(self, key): # random hashing function (replace with better function)
if (type(key) is str): # accepts chars, strings, and ints
hash = ((ord(key)*5)+2)//3
else:
hash = (key*5+2)//3
index = hash % self.size
return index
def __resize(self):
self.__nextPrime()
tmp = [None]*self.size
for i in self.table:
if i is not None:
index = self.__hash(i)
if tmp[index] is None:
tmp[index] = i
else:
j = 1
newIndex = index + 1
if newIndex >= self.size:
newIndex %= self.size
while tmp[newIndex]:
#j += 1 # linear probing
j = (j+1)**2 # quadratic probing
newIndex += j
if newIndex >= self.size:
newIndex %= self.size
tmp[newIndex] = i
self.table[:] = tmp
def set(self, key):
index = self.__hash(key)
if self.table[index] is None:
self.table[index] = key
else:
i = 1
newIndex = index + 1
if newIndex >= self.size:
newIndex %= self.size
while self.table[newIndex]:
#i += 1 # linear probing
i = (i+1)**2 # quadratic probing
newIndex += i
if newIndex >= self.size:
newIndex %= self.size
self.table[newIndex] = key
self.count += 1
if self.count/self.size >= self.load:
self.__resize()
def get(self, key):
index = self.__hash(key)
return index
def __getitem__(self, index):
return self.table[index]
def __contains__(self, key):
index = self.__hash(key)
return key == self.table[index]
def __len__(self):
return self.count