字典

没用过字典(英文一般叫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,自然就需要使用到字典这种数据结构了。

总结

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


参考资料:


更多文章
  • Web开发系列(四):Flask, Tornado和WSGI
  • Web开发系列(三):什么是HTML,CSS,JS?
  • Web开发系列(二):HTTP协议
  • Web开发系列(一):从输入网址到最后,这个过程经历了什么?
  • SNI: 让Nginx在一个IP上使用多个证书
  • Haskell: infixl, infixr, infix
  • Haskell简明教程(五):处理JSON
  • Haskell简明教程(四):Monoid, Applicative, Monad
  • HTTPS 的详细流程
  • OAuth2 为什么需要 Authorization Code?
  • 任务队列怎么写?python rq源码阅读与分析
  • XMonad 配置教程
  • Haskell简明教程(三):Haskell语法
  • Haskell简明教程(二):从命令式语言进行抽象
  • Haskell简明教程(一):从递归说起