python-algorithms/algorithms/map/hashtable.py at master · ilyvsc/python-algorithms · GitHub

History

119 lines (98 loc) · 3.81 KB

Raw

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

class HashTable(object):

"""

HashMap Data Type

HashMap() Create a new, empty map. It returns an empty map collection.

put(key, val) Add a new key-value pair to the map. If the key is already in the map then replace

the old value with the new value.

get(key) Given a key, return the value stored in the map or None otherwise.

del_(key) or del map[key] Delete the key-value pair from the map using a statement of the form del map[key].

len() Return the number of key-value pairs stored in the map.

in Return True for a statement of the form key in map, if the given key is in the map, False otherwise.

"""

_empty = object()

_deleted = object()

def __init__(self, size=11):

self.size = size

self._len = 0

self._keys = [self._empty] * size # keys

self._values = [self._empty] * size # values

def put(self, key, value):

initial_hash = hash_ = self.hash(key)

while True:

if self._keys[hash_] is self._empty or self._keys[hash_] is self._deleted:

# can assign to hash_ index

self._keys[hash_] = key

self._values[hash_] = value

self._len += 1

return

elif self._keys[hash_] == key:

# key already exists here, assign over

self._keys[hash_] = key

self._values[hash_] = value

return

hash_ = self._rehash(hash_)

if initial_hash == hash_:

# table is full

raise ValueError("Table is full")

def get(self, key):

initial_hash = hash_ = self.hash(key)

while True:

if self._keys[hash_] is self._empty:

# That key was never assigned

return None

elif self._keys[hash_] == key:

# key found

return self._values[hash_]

hash_ = self._rehash(hash_)

if initial_hash == hash_:

# table is full and wrapped around

return None

def del_(self, key):

initial_hash = hash_ = self.hash(key)

while True:

if self._keys[hash_] is self._empty:

# That key was never assigned

return None

elif self._keys[hash_] == key:

# key found, assign with deleted sentinel

self._keys[hash_] = self._deleted

self._values[hash_] = self._deleted

self._len -= 1

return

hash_ = self._rehash(hash_)

if initial_hash == hash_:

# table is full and wrapped around

return None

def hash(self, key):

return key % self.size

def _rehash(self, old_hash):

"""

linear probing

"""

return (old_hash + 1) % self.size

def __getitem__(self, key):

return self.get(key)

def __delitem__(self, key):

return self.del_(key)

def __setitem__(self, key, value):

self.put(key, value)

def __len__(self):

return self._len

class ResizableHashTable(HashTable):

MIN_SIZE = 8

def __init__(self):

super().__init__(self.MIN_SIZE)

def put(self, key, value):

rv = super().put(key, value)

# increase size of dict * 2 if filled >= 2/3 size (like python dict)

if len(self) >= (self.size * 2) / 3:

self.__resize()

def __resize(self):

keys, values = self._keys, self._values

self.size *= 2 # this will be the new size

self._len = 0

self._keys = [self._empty] * self.size

self._values = [self._empty] * self.size

for key, value in zip(keys, values):

if key is not self._empty and key is not self._deleted:

self.put(key, value)

python-algorithms/algorithms/map/hashtable.py at master · ilyvsc/python-algorithms · GitHub

Expand file tree

Breadcrumbs

hashtable.py

Latest commit

History

Breadcrumbs

hashtable.py

File metadata and controls