Ex17 LMPTHW: Dictionary

Hi,

I am working on ex17 in which I have to analyze the dictionary.py code of Zed and I am trying to figure out why he does the following:
after initializing the self.map attribute and setting it to the doublelinkedlist instance, he is using the push method to push another doublelinkedlist to this instance (see code below). Seeing a string or number being pushed to this linkedlist makes perfect sense to me but pusing another instance? I would like to know why this makes sense because seemingly this works.

Thanks in advance for your response.

class Dictionary(object):
    def __init__(self, num_buckets=256):
        """Initializes a Map with the given number of buckets."""
        self.map = DoubleLinkedList()
        for i in range(0, num_buckets):
            self.map.push(DoubleLinkedList())

This dictionary contains three data structures: ‘slots’, ‘buckets’ and the ‘map’.

  • The map is a linked list. Each element in this linked list contains a bucket.
  • The bucket is a linked list. Each element in this linked list is a slot.
  • The slot is a two-element tuple. The elements are the key-value pair.

Here’s a way to think about the basic structure (I won’t get into hash function and modulus with this metaphor).

Imagine the dictionary’s map as a city street.

There are multiple apartment buildings on this street. The city planners can put any number of buildings on this street, but once they are built, that number of addresses is fixed. We cannot add or remove buildings. Imagine the buckets as apartment buildings.

There can be any number of occupants in this building. They can move in and out of the apartment as they please. Imagine the slots as occupied apartments in the building.

I’ll stop there. Once you have a mental model that works for you, I would suggest studying the hash_id method.

2 Likes

Hi Austen,

Thank you for your reply. It really makes sense now. Especially after your illustrative example. Thank you very much! :+1:

1 Like

FYI, I mentioned hash function and modulus. That should’ve been modulo, which is the % operator. Similar-sounding word, different math.

1 Like