Skip to content

Commit 8c178c8

Browse files
nixrajputnixrajput
committed
stack and hash tableadded
1 parent 71f774d commit 8c178c8

File tree

10 files changed

+604
-169
lines changed

10 files changed

+604
-169
lines changed

‎src/data_structures/hash_table/__init__.py

Whitespace-only changes.

‎src/data_structures/hash_table/hash_table.py

Lines changed: 96 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,96 @@
1+
import os
2+
import sys
3+
from typing import List
4+
import functools
5+
6+
file_path = os.path.abspath(__file__)
7+
src_dir = os.path.dirname(os.path.dirname(os.path.dirname(file_path)))
8+
root_folder = os.path.abspath(src_dir)
9+
sys.path.append(root_folder)
10+
from data_structures.linked_list.singly.linked_list import LinkedList
11+
12+
defaultHashTableSize = 32
13+
14+
15+
class HashTable:
16+
def __init__(self, hashTableSize=defaultHashTableSize):
17+
arr = list()
18+
for _ in range(hashTableSize):
19+
arr.append(None)
20+
21+
bucketList = list()
22+
for _ in range(len(arr)):
23+
bucketList.append(LinkedList())
24+
25+
self.buckets = bucketList
26+
self.keys = {}
27+
28+
def hash(self, key):
29+
listFromKey = list(key)
30+
31+
hashedKey = 0
32+
for char in listFromKey:
33+
hashedKey += ord(char)
34+
35+
return hashedKey % len(self.buckets)
36+
37+
def set(self, key, value):
38+
keyHash = self.hash(key)
39+
self.keys[key] = keyHash
40+
bucketLinkedList = self.buckets[keyHash]
41+
42+
def getNode(nodeValue):
43+
return nodeValue["key"] == key
44+
45+
node = bucketLinkedList.find(callback=getNode)
46+
47+
if not node:
48+
bucketLinkedList.append({"key": key, "value": value})
49+
else:
50+
node.value["value"] = value
51+
52+
def delete(self, key):
53+
keyHash = self.hash(key)
54+
bucketLinkedList = self.buckets[keyHash]
55+
56+
def getNode(nodeValue):
57+
return nodeValue["key"] == key
58+
59+
node = bucketLinkedList.find(callback=getNode)
60+
61+
if node:
62+
del self.keys[key]
63+
return bucketLinkedList.delete(node.value)
64+
65+
return None
66+
67+
def get(self, key):
68+
bucketLinkedList = self.buckets[self.hash(key)]
69+
70+
def getNode(nodeValue):
71+
return nodeValue["key"] == key
72+
73+
node = bucketLinkedList.find(callback=getNode)
74+
75+
return node.value["value"] if node else None
76+
77+
def has(self, key):
78+
if key in self.keys:
79+
return True
80+
81+
return False
82+
83+
def getKeys(self):
84+
keys = []
85+
86+
for key in self.keys:
87+
keys.append(key)
88+
return keys
89+
90+
def getValues(self):
91+
bucketValues = list()
92+
for bucket in self.buckets:
93+
for linkedListNode in bucket.toArray():
94+
bucketValues.append(linkedListNode.value["value"])
95+
96+
return bucketValues

‎src/data_structures/hash_table/hash_table_test.py

Lines changed: 128 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,128 @@
1+
import os
2+
import sys
3+
import unittest
4+
5+
file_path = os.path.abspath(__file__)
6+
src_dir = os.path.dirname(os.path.dirname(os.path.dirname(file_path)))
7+
root_folder = os.path.abspath(src_dir)
8+
sys.path.append(root_folder)
9+
from data_structures.hash_table.hash_table import HashTable
10+
11+
12+
class TestCase(unittest.TestCase):
13+
def test_create_hash_table(self):
14+
"""
15+
Test to create an empty HashTable
16+
"""
17+
defaultHashTable = HashTable()
18+
19+
self.assertEqual(len(defaultHashTable.buckets), 32)
20+
21+
biggerHashTable = HashTable(64)
22+
23+
self.assertEqual(len(biggerHashTable.buckets), 64)
24+
25+
def test_generate_hash(self):
26+
"""
27+
Test to generate proper hash for specified keys
28+
"""
29+
hashTable = HashTable()
30+
31+
self.assertEqual(hashTable.hash("a"), 1)
32+
self.assertEqual(hashTable.hash("b"), 2)
33+
self.assertEqual(hashTable.hash("abc"), 6)
34+
35+
def test_set_read_delete_data_in_hash_table(self):
36+
"""
37+
Test to set, read and delete data with collisions
38+
"""
39+
hashTable = HashTable(3)
40+
41+
self.assertEqual(hashTable.hash("a"), 1)
42+
self.assertEqual(hashTable.hash("b"), 2)
43+
self.assertEqual(hashTable.hash("c"), 0)
44+
self.assertEqual(hashTable.hash("d"), 1)
45+
46+
hashTable.set("a", "sky-old")
47+
hashTable.set("a", "sky")
48+
hashTable.set("b", "sea")
49+
hashTable.set("c", "earth")
50+
hashTable.set("d", "ocean")
51+
52+
self.assertFalse(hashTable.has("x"))
53+
self.assertTrue(hashTable.has("b"))
54+
self.assertTrue(hashTable.has("c"))
55+
56+
def nodeStringifier(value):
57+
return f"{value['key']}:{value['value']}"
58+
59+
self.assertEqual(hashTable.buckets[0].toList(nodeStringifier), ["c:earth"])
60+
self.assertEqual(
61+
hashTable.buckets[1].toList(nodeStringifier), ["a:sky", "d:ocean"]
62+
)
63+
self.assertEqual(hashTable.buckets[2].toList(nodeStringifier), ["b:sea"])
64+
65+
self.assertEqual(hashTable.get("a"), "sky")
66+
self.assertEqual(hashTable.get("d"), "ocean")
67+
self.assertEqual(hashTable.get("x"), None)
68+
69+
hashTable.delete("a")
70+
71+
self.assertIsNone(hashTable.delete("xyz"))
72+
73+
self.assertEqual(hashTable.get("a"), None)
74+
self.assertEqual(hashTable.get("d"), "ocean")
75+
76+
hashTable.set("d", "ocean-new")
77+
self.assertEqual(hashTable.get("d"), "ocean-new")
78+
79+
def test_add_objects_to_hash_table(self):
80+
"""
81+
Test to add objects to HashTable
82+
"""
83+
hashTable = HashTable()
84+
85+
hashTable.set("objectKey", {"prop1": "a", "prop2": "b"})
86+
87+
obj = hashTable.get("objectKey")
88+
89+
self.assertEqual(obj["prop1"], "a")
90+
self.assertEqual(obj["prop2"], "b")
91+
92+
def test_track_actual_keys_in_hash_table(self):
93+
"""
94+
Test to track actual keys in HashTable
95+
"""
96+
hashTable = HashTable(3)
97+
98+
hashTable.set("a", "sky-old")
99+
hashTable.set("a", "sky")
100+
hashTable.set("b", "sea")
101+
hashTable.set("c", "earth")
102+
hashTable.set("d", "ocean")
103+
104+
self.assertEqual(hashTable.getKeys(), ["a", "b", "c", "d"])
105+
self.assertTrue(hashTable.has("a"))
106+
self.assertFalse(hashTable.has("x"))
107+
108+
hashTable.delete("a")
109+
110+
self.assertFalse(hashTable.has("a"))
111+
self.assertTrue(hashTable.has("b"))
112+
self.assertFalse(hashTable.has("x"))
113+
114+
def test_get_all_values_from_hash_table(self):
115+
"""
116+
Test to track values from HashTable
117+
"""
118+
hashTable = HashTable(3)
119+
120+
hashTable.set("a", "alpha")
121+
hashTable.set("b", "beta")
122+
hashTable.set("c", "gamma")
123+
124+
self.assertEqual(hashTable.getValues(), ["gamma", "alpha", "beta"])
125+
126+
127+
if __name__ == "__main__":
128+
unittest.main()

0 commit comments

Comments
 (0)