PYTHON ORDERED HASHTABLE Ordered Hashtable Overview For this assignment you will

Question

PYTHON ORDERED HASHTABLE

Ordered Hashtable

Overview

For this assignment you will update and complete the implementation of the hashtable data structure presented in class, which exposes an API mirroring that of the built-in Python dict. When iterating over its contents (supported by the __iter__, keys, values, and items methods), your updated implementation will also reflect the order in which key/value pairs were originally inserted into the hashtable. This will require that you implement the two-tiered list system described during lecture.

The operations you will implement are listed alongside their descriptions below (h refers to a hashtable):

Your hashtable will be provided with the initial number of buckets on creation (i.e., in __init__); your implementation must heed this value, as there may be performance ramifications if it does not.

In [ ]:

In [ ]:

In [ ]:

In [ ]:

In [ ]:

In [ ]:

In [ ]:

Operation Description h[k] = v If h does not contain key k, a new k?v mapping is added, else the value for key k is updated to v. h[k] If h contains key k, the corresponding value is returned, else a KeyError is raised. del h[k] If h contains key k, it is removed along with its value, else a KeyError is raised. Note that if k is re-inserted at some later point it is considered a new key (for ordering purposes). k in h Returns True if key k is in h. len(h) Returns the number of keys in h. iter(h) Returns an iterator over all the keys in h, in the order they were added. h.keys() (Same as above) h.values() Returns an iterator over all the values in h, in the order they were added. h.items() Returns an iterator over all the key/value pairs (as tuples) in h, in the order they were added.

Explanation / Answer

the below code is the best of my knowledge

class OrderedHashtable:
class Node:
"""This class is used to create nodes in the singly linked "chains" in
each hashtable bucket."""
def __init__(self, index, next=None):
# don't rename the following attributes!
self.index = index
self.next = next
  
def __init__(self, n_buckets=1000):
# the following two variables should be used to implement the "two-tiered"
# ordered hashtable described in class -- don't rename them!
self.indices = [None] * n_buckets
self.entries = []
self.count = 0
  
def __getitem__(self, key):
i = hash(key) % len(self.indices)
b = self.indices[i]
while b is not None:
if self.entries[b.index][0] == key:
return self.entries[b.index][1]
b = b.next
raise KeyError
  
def __setitem__(self, key, val):
i = hash(key) % len(self.indices)
valindex = len(self.entries)

if self.indices[i] is None:
self.entries.append([key, val])
self.count += 1
self.indices[i] = OrderedHashtable.Node(valindex, None)
else:
b = self.indices[i]
while b:
n = self.entries[b.index]
if n[0] == key:
n[1] = val
return
if b.next is None:
self.entries.append([key, val])
b.next = OrderedHashtable.Node(valindex, None)
self.count += 1
return;
b = b.next

  
  
def __delitem__(self, key):
deletedindex = None
hashindex = hash(key) % len(self.indices)
node = self.indices[hashindex]
if self.entries[node.index][0] == key:
self.count -= 1
del self.entries[node.index]
deletedindex = node.index
if node.next is not None:
self.indices[hashindex] = node.next
else:
self.indices[hashindex] = None
else:
while node is not None:
last_node = node
node = node.next
if self.entries[node.index][0] == key:
self.count -= 1
del self.entries[node.index]
deletedindex = node.index
last_node.next = node.next
break
else:
raise KeyError
for bucket in self.indices:
node = bucket
while node is not None:
if node.index > deletedindex:
node.index -= 1
node = node.next
  
def __contains__(self, key):
try:
_ = self[key]
return True
except:
return False
  
def __len__(self):
return self.count
  
def __iter__(self):
for i in self.entries:
yield i[0]
  
def keys(self):
return iter(self)
  
def values(self):
for i in self.entries:
yield i[1]

def items(self):
for i in self.entries:
yield tuple(i)
  
def __str__(self):
return '{ ' + ', '.join(str(k) + ': ' + str(v) for k, v in self.items()) + ' }'
  
def __repr__(self):
return str(self)

  
ht = OrderedHashtable(1)
# for i in range(10):
# ht[i] = i * i

ht["a"] = "b"
ht["b"] = "c"
print(ht)
del ht["a"]
print(ht["b"])

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.