| *.pyc |
A simple implementation of a HashMap in Python with linear time searching semantics.
One improvement that could increase its performance is at insert time, search and insert the new key-value pair
into a sorted position. Then upon reading, instead of doing a linear search, it may do a binary search to cut times to
log(n).
The code is written for Python 3 but should also work on Python 2.x.
| class HashMap: | |
| def __init__(self): | |
| self.items = [] | |
| def __getitem__(self, key): | |
| found_items = [item for item in self.items if item.key == key] | |
| if len(found_items) == 1: | |
| return found_items[0].value | |
| raise KeyError(key) | |
| def __setitem__(self, key, value): | |
| try: | |
| index = self._index(key) | |
| self.items[index] = HashEntry(key, value) | |
| except KeyError: | |
| self.items.append(HashEntry(key, value)) | |
| def _index(self, key): | |
| for (index, _) in enumerate(self.items): | |
| if self.items[index].key == key: | |
| return index | |
| raise KeyError(key) | |
| class HashEntry: | |
| def __init__(self, key, value): | |
| self.key = key | |
| self.value = value |
| import unittest | |
| from hash_map import HashMap | |
| class TestHashMap(unittest.TestCase): | |
| def setUp(self): | |
| self.hash_map = HashMap() | |
| self.hash_map['test_key'] = 'test_value' | |
| self.hash_map['another_test_key'] = 'another_test_value' | |
| def tearDown(self): | |
| self.hash_map = None | |
| def test_set_key_value(self): | |
| self.assertEqual(self.hash_map['test_key'], 'test_value') | |
| def test_adding_a_new_key_value(self): | |
| self.assertEqual(self.hash_map['another_test_key'], 'another_test_value') | |
| def test_overwrite_value_in_key(self): | |
| self.hash_map['test_key'] = 'another_test_value' | |
| self.assertEqual(self.hash_map['test_key'], 'another_test_value') | |
| def test_raise_key_error(self): | |
| with self.assertRaises(KeyError): | |
| self.hash_map['non-existent-key'] | |
| if __name__ == '__main__': | |
| unittest.main() |