Created
April 17, 2020 10:16
-
-
Save Nasdin/94084c87ce8fb8125e3963c54c6e92ac to your computer and use it in GitHub Desktop.
Hashmap in Python without dictionaries
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # Implement a hashmap in Python without using a dictionary | |
| # A simple toy example, look to improve when the hashes start clashing with each other either by adapting a dynamic size | |
| # Or using a better hash function | |
| class HashMap(object): | |
| def __init__(self, size, hash_function): | |
| self.array = [None] * size | |
| self.size = size | |
| self.hash_function = hash_function | |
| def __getitem__(self, item): | |
| index = self._get_index(item) | |
| value = self.array[index] | |
| if value is None: | |
| raise KeyError("Value does not exist") | |
| return value | |
| def _get_index(self, val): | |
| return self.hash_function(val) % self.size | |
| def __setitem__(self, item, value): | |
| if item is None: | |
| return ValueError("NoneTypes are not hashable") | |
| if value is None: | |
| return ValueError("NoneTypes cannot be stored") | |
| index = self._get_index(item) | |
| self.array[index] = value | |
| def simple_hash_function(value): | |
| str_hash = str(value) | |
| hash_strs = 'abcdefghijklmnopqrstuvwxyz' | |
| hash_strs = hash_strs + hash_strs.upper() | |
| hash_strs = hash_strs + '0123456789' | |
| hash_dict = {v:i for i,v in enumerate(hash_strs)} | |
| value = [hash_dict[v] for v in value] | |
| return sum(value) | |
| example_hashmap = HashMap(30, simple_hash_function ) | |
| example_hashmap['toy'] = 123 | |
| example_hashmap['duck'] = 'quack' | |
| assert example_hashmap['toy'] == 123 | |
| assert example_hashmap['duck'] == 'quack' | |
| print(example_hashmap['toy']) | |
| print(example_hashmap['duck']) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment