Implement a Hashtable

Today,

we implemented an array with object and a hashtable with array. Drinking food and eating drink. Same but different.

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
class HashTable:
def __init__(self, size):
self.array = [None] * size # hash size should be 1.3 larger and a prime number

def hash(self, key):
return key % len(self.array)

def add(self, key, value):
if self.isFull():
self.doubleSize()

hashIndex = self.hash(key)

if self.array[hashIndex] is None:
self.array[hashIndex] = [[key, value]]
else:
isValueExist = False
for i in self.array[hashIndex]:
if i[0] == key:
i[1] = value
isValueExist = True

if not isValueExist:
self.array[hashIndex].append([key, value])

def get(self, key):
hashIndex = self.hash(key)

if self.array[hashIndex] is None:
raise KeyError("invalid key")
else:
for i in self.array[hashIndex]:
if i[0] == key:
return i[1]

raise KeyError("missing key")

def isFull(self):
count = 0
for i in self.array:
if i:
count += 1
return count > len(self.array) // 2

def doubleSize(self):
newSize = len(self.array) * 2
newHashTable = HashTable(newSize)

for i in self.array:
if i:
for j in i:
newHashTable.add(j[0], j[1])

self.array = newHashTable.array


h = HashTable(3)
h.add(1, "hello")
h.add(1, "eh")
h.add(2, "woo")
h.add(5, "eh")
h.add(10, "eh")
h.add(6, "eh")