1 Star 3 Fork 2

东圣/system-design-primer

加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
文件
克隆/下载
hash_map.ipynb 3.05 KB
一键复制 编辑 原始数据 按行查看 历史

This notebook was prepared by Donne Martin. Source and license info is on GitHub.

Design a hash map

Constraints and assumptions

  • For simplicity, are the keys integers only?
    • Yes
  • For collision resolution, can we use chaining?
    • Yes
  • Do we have to worry about load factors?
    • No
  • Can we assume inputs are valid or do we have to validate them?
    • Assume they're valid
  • Can we assume this fits memory?
    • Yes

Solution

%%writefile hash_map.py
class Item(object):

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


class HashTable(object):

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

    def _hash_function(self, key):
        return key % self.size

    def set(self, key, value):
        hash_index = self._hash_function(key)
        for item in self.table[hash_index]:
            if item.key == key:
                item.value = value
                return
        self.table[hash_index].append(Item(key, value))

    def get(self, key):
        hash_index = self._hash_function(key)
        for item in self.table[hash_index]:
            if item.key == key:
                return item.value
        raise KeyError('Key not found')

    def remove(self, key):
        hash_index = self._hash_function(key)
        for index, item in enumerate(self.table[hash_index]):
            if item.key == key:
                del self.table[hash_index][index]
                return
        raise KeyError('Key not found')
Overwriting hash_map.py
Loading...
马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化
1
https://gitee.com/doshengl/system-design-primer.git
git@gitee.com:doshengl/system-design-primer.git
doshengl
system-design-primer
system-design-primer
master

搜索帮助