3
\$\begingroup\$

Here's the API my teacher assigned:

API

and here is what I came up with:

class MyMap:
    def __init__(self,size=10):
        self.size = size
        self.internal_list = [None] * size
    def _getHash(string,size):
        total = 0
        for ch in string:
            total += ord(ch)
        total = total % size
        return total
    def set(self,key,value):
        listnum = MyMap._getHash(key,self.size)
        if key in self.internal_list:
            print("already there")
            return None
        if self.internal_list[listnum] == None or self.internal_list[listnum] is type(tuple):
            self.internal_list[listnum] = (key, value)
        else:
            pass
    def get(self,key):
        listnum = MyMap._getHash(key,self.size)
        if self.internal_list[listnum] == None:
            return None
        else:
            return self.internal_list[listnum][2]
    def size(self):
        sizecount = 0
        count = 0
        while len(self.internal_list)-count != 0:
            if self.internal_list[count] != None:
                sizecount += 1
            count += 1 
        return sizecount
    def getKeys(self):
        keylist = []
        count = 0
        while len(self.internal_list) - count != 0:
            if self.internal_list[count] != None:
                keylist.append(self.internal_list[count][0])
            count += 1
        return keylist

Just wondering

  1. if it will fulfill the requirements of the assignment
  2. what I can do to clean up the code

Here's what I've tested:

x = MyMap()
x.set('test',2)
x.set('crest',3)
x.set('best',5)
print(MyMap.size(x))
print(x.get('test'))
print(MyMap.getKeys(x))
print(x.internal_list)

and the results...

results

\$\endgroup\$
8
  • \$\begingroup\$ this is untested code, right? \$\endgroup\$
    – Malachi
    Nov 10, 2014 at 23:37
  • \$\begingroup\$ No I have tested it not sure I have fully tested it though \$\endgroup\$ Nov 10, 2014 at 23:38
  • \$\begingroup\$ does it work the way it was intended? \$\endgroup\$
    – Malachi
    Nov 10, 2014 at 23:39
  • 2
    \$\begingroup\$ Could you provide your tests? How much of the code do they cover, and what are you still unsure of? \$\endgroup\$
    – jonrsharpe
    Nov 10, 2014 at 23:44
  • 3
    \$\begingroup\$ we are not here to test code, we are here to review code that works. does that make sense? you should make sure that it functions the way you anticipate by giving it data and analyzing the output usually with control data where you know what the output will be given specific input. \$\endgroup\$
    – Malachi
    Nov 10, 2014 at 23:44

2 Answers 2

3
\$\begingroup\$

The first thing you need to do is learn how to unittest your code. This will assume Python3.

# filename: test_MyMap.py
import unittest
import unittest.mock as mock
from mymap import MyMap # the filename for your code

class Test(unittest.TestCase):

    # here's where you write the tests.
    def test_default_size(self):
        m = MyMap()
        self.assertEqual(m.size, 10)

    def test_set_method(self):
        """we use unittest.mock.patch to swap in an easy version of
        _getHash that we know cannot fail. This way we don't introduce
        any other reason of failure into our test for MyMap.set"""

        def replace_getHash(self,key):
            return {'string':0, 1:1, tuple(1,2):2}[key]
        with mock.patch("__main__.MyMap._getHash", new=replace_getHash):
            for key,value in [('string','value'),
                              (1,2),
                              (tuple(1,2), tuple(3,4))]:
                m.set(key, value)
                self.assertEqual(m.internal_list[m._getHash(key)], value)

    def test_get_method(self):
        # etc for all the specs you need to fulfill

if __name__ == "__main__":
    """Will run all the TestCase classes, which each run all their methods
    that begin with test_"""
    unittest.main()

The first thing you should do when you get an assignment or any other spec to write from is design a set of unit tests (as above) to write your code to meet. It's much harder to create unit tests from a program than from a spec so do it this way first! Then every time you change the code, check it against the unit tests to make sure you haven't broken anything.

As far as the actual review goes, it's going to be hard to look at until you can design a full suite of tests against it. A quick glance looks like this will fail if you give it a non-iterable key (e.g. an int, which should be doable) and will also lead to hash collision if you give it an anagram (e.g. foo.set("test",3) == foo.set("etst", 3)). These are edge cases that your unit tests should catch.

Beyond that I'd implement item access (so you can do my_map_object[some_key] instead of having to rely on my_map_object.get(some_key)) and it really seems like you could clean up your MyMap.getkeys function. Something like:

def getkeys(self):
    return [keyvalue[0] for keyvalue in self.internal_list if keyvalue is not None]

should work perfectly. It also stands to reason that

def size(self):
    return sum([1 for key in self.getkeys()])

would work too!

Oh and your MyMap._getHash function will break completely, since string will never be iterable. It should be def _getHash(self, string) (and reference self.size()) rather than def _getHash(string, size) unless you make it a @staticmethod (which WOULD make sense except that your size modulo is dependent on your particular mapping!)

\$\endgroup\$
1
  • \$\begingroup\$ When perfect answers don't get marked by new users... \$\endgroup\$ Dec 23, 2015 at 22:18
2
\$\begingroup\$

I am going to assume that the reason you're supposed to be doing this is to better understand the costs and benefits of hash tables/dictionaries generally. Therefore I think that the key issue is that instead of:

[None] * size

your storage should be:

[[] for _ in range(size)]

(see here for why you can't use the same syntax. TL;DR: mutability.)

Note also that Python's dictionaries don't hash their keys; they ask the keys for their hash. To reflect that, here is a simple key-value pair class:

class KeyValuePair:

    """An container to store things in a HashTable."""

    def __init__(self, key, value=None):
        self.key = key
        self.value = value
        self._hash()

    def __repr__(self):
        return "{0.key!r}: {0.value!r}".format(self)

    def __eq__(self, other):
        return self.key == other.key

    def _hash(self):
        """Calculate the hash of the key.

        Notes:
          Currently only works for strings.

        Raises:
          TypeError: If the key isn't supported.

        """ 
        if isinstance(self.key, str):
            self.hash = sum(map(ord, self.key))
        else:
            raise TypeError("Can't hash {!r}.".format(self.key))

(Note that this isn't what your spec asks for, but you can adapt these ideas into your own code.)

And here is a hash table, with just set and get implemented:

 class HashTable:

     """A very rough approximation of a Python dictionary."""

     def __init__(self, size=10):
         self.buckets = [[] for _ in range(size)]
         self.size = size

     def __repr__(self):
         return "\n".join(["{}: {!r}".format(index, bucket) for
                           index, bucket in enumerate(self.buckets)])

     def set(self, key, value=None):
         """Add a new key-value pair to the hash table.

         Notes:
           The key must be hashable by KeyValuePair._hash.

         Args:
           key: The key to use.
           value (optional): The value to store (defaults to None).

         """
         keyval = KeyValuePair(key, value)
         bucket = self.buckets[keyval.hash % self.size]
         for kvp in bucket:
             if kvp == keyval:
                 bucket.remove(kvp)
                 break
         bucket.append(keyval)

     def get(self, key):
         """Retrive the value for the specified key.

         Notes:
           The key must be hashable by KeyValuePair._hash.

         Args:
           key: The key to use.

         Raises:
           KeyError: If the key can't be found.

         """
         keyval = KeyValuePair(key)
         bucket = self.buckets[keyval.hash % self.size]
         for kvp in bucket:
             if kvp == keyval:
                 return kvp.value
         raise KeyError("Key {!r} not found.".format(key))

Now in use:

>>> table = HashTable(8)
>>> for python in ("John Cleese", "Graham Chapman", "Terry Gilliam", 
                   "Eric Idle", "Terry Jones", "Michael Palin"):
    first, last = python.split()
    table.set(last, first)


>>> table
0: ['Chapman': 'Graham']
1: ['Cleese': 'John']
2: []
3: []
4: ['Palin': 'Michael']
5: []
6: ['Idle': 'Eric']
7: ['Gilliam': 'Terry', 'Jones': 'Terry']
>>> table.get("Gilliam")
'Terry'
>>> table.set(1, "foo")
Traceback (most recent call last):
  File "<pyshell#21>", line 1, in <module>
    table.set(1, "foo")
  File "<pyshell#5>", line 12, in set
    keyval = KeyValuePair(key, value)
  File "<pyshell#15>", line 6, in __init__
    self._hash()
  File "<pyshell#15>", line 27, in _hash
    raise TypeError("Can't hash {!r}.".format(self.key))
TypeError: Can't hash 1.
>>> table.get("Smith")
Traceback (most recent call last):
  File "<pyshell#23>", line 1, in <module>
    table.get("Smith")
  File "<pyshell#5>", line 26, in get
    raise KeyError("Key {!r} not found.".format(key))
KeyError: "Key 'Smith' not found."

So what's important here?

  1. Not every bucket has anything in - we're reserving more space than we strictly need (space vs. speed is a classic computing trade-off).
  2. Using a hash to determine the bucket means we can quickly (hopefully O(1)) find out where we should be looking, rather than searching through the whole table. This is why:
    1. hash speed is important - if it takes ages to calculate the hash, we lose the advantage; and
    2. hash stability is important - if you get a different hash for the same key, you can't find it again;
  3. Some buckets have more than one thing in, in which case we fall back to a linear search O(len(bucket)). This is why hash distribution is important - if everything ended up in the same bucket (e.g. def _hash(self): self.hash = 42, this is known as hash collision) we're back to a O(n) search through everything.

Note the following general points:

  • Lots of docstrings to explain what's going on (your code has none);
  • Compliance with the style guide (your code lacks e.g. whitespace after commas, and (despite your specification!) it should really be e.g. _get_hash); and
  • Raising errors rather than returning None when something goes wrong - None can be a valid return value!

If you're interested in learning more about dictionaries, see The Mighty Dictionary.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.