字典

没用过字典(英文一般叫dict或map)的，请举个手。

字典是常用的一种数据结构，在有的语言里叫做dict，有的语言里叫做map。字典一般用来实现KV存储，也就是说，给定一个Key，能够快速的把Value找出来。实现字典的方式一般有两种：

使用树
使用哈希表

接下来我们分别看一下这两种实现是怎么做的。

使用树实现字典

使用树来实现字典？没错，我们来看一个使用二叉树来实现字典的例子：

二叉树实现字典

可以看到，每当我们要查找一个元素是否在字典中时，我们就从root开始下降，如果等于当前节点，就返回当前节点，如果是比当前节点更小，就向左边的子节点下降，如果比当前节点更大，就向右边的子节点下降，一直到找到或者发现没有此节点为止。

使用二叉树来实现字典的优点就是二叉树是有顺序的，缺点和哈希表(使用链表解决冲突时)实现差不多，最差情况就是二叉树串成了一个链，大O为O(N)。

使用哈希表实现字典

哈希表，查一下百科，是这样的定义：

散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

也就是说，我们需要两个东西，第一，一个哈希函数，第二，一个数组用于存储数据。非常好，接下来我们就使用哈希表的定义，自己造一个字典出来，虽然我们的字典简陋无比，但是在互联网方法论中，我们这叫 MVP！

class MyHash:
    def __init__(self, size=10):
        self.__size = size  # size，你懂的
        self.__array = [None] * size  # 先申请一个长度为size的list，对应上面我们所说的"数组"，总之是用来存储元素的

    def __getitem__(self, key):
        hash_value = key % self.__size  # 取余数，为啥呢？这样可以保证，元素永远都在我们所申请的"数组"里
        return self.__array[hash_value]

    def __setitem__(self, key, value):
        hash_value = key % self.__size  # 同上
        self.__array[hash_value] = value

    def __str__(self):
        return str(self.__array)


if __name__ == "__main__":
    my_hash = MyHash()
    my_hash[3] = "hello"
    my_hash[12] = "world"
    print(my_hash)

执行一下：

$ python my_hash.py
[None, None, 'world', 'hello', None, None, None, None, None, None]

瞧见没，一个简单，哦不，简陋的哈希表就这么横空诞生，至于说什么key只能是数字，没法解决冲突嘛，这就交给我们实际项目中使用的实现来解决吧 :)

字典的用处

字典有什么用处呢？可能一时半会儿很难说出来，但实际上我们在项目实践中，到处都有用到，比如：JSON。写接口的时候，是不是会用到 JSON呢？没错，请求一个接口，返回JSON时，就可以把它反序列化到一个字典里，当然，可能写Go的同学们说，通常我们会序列化到一个 struct里，但是不要忘记了，也是可以反序列化到字典里的。

那还有没有例子呢？有的，比如有一堆的数据要进行去重，就可以用上字典（当然，更多是使用set），再比如，你需要在内存中维护一堆的KV，自然就需要使用到字典这种数据结构了。

总结

这一篇中，我们介绍了字典这种数据结构，我们从字典的两种实现方式入手，分别简要的介绍了如何使用树和哈希表来实现字典，最后我们列举了一些常见的字典的使用场景。

参考资料：

哈希表

字典

使用树实现字典

使用哈希表实现字典

字典的用处

总结

更多文章