Python教程

【python】 字典 与 集合 的特点,及它们背后的散列表

本文主要是介绍【python】 字典 与 集合 的特点,及它们背后的散列表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

字典的特点

  • 键查询很快:字典类型提供了无视数据量大小的快速访问——只要字典能被装在内存里。
  • 当往 dict 里添加新键而又发生散列冲突的时候,新键可能会被安排存放到另一个位置。但字典是否等价则与键的添加次序无关。
  • 往字典里添加新键可能会改变已有键的顺序:无论何时往字典里添加新的键,Python 解释器都可能做出为字典扩容的决定。扩容导致的结果就是要新建一个更大的散列表,并把字典里已有的元素添加到新表里。这个过程中可能会发生新的散列冲突,导致新散列表中键的次序变化。
    • 因此不要对字典同时进行迭代和修改。如果想扫描并修改一个字典,最好分成两步来进行:
      1. 首先对字典迭代,以得出需要添加的内容,把这些内容放在一个新字典里;
      2. 迭代结束之后再对原有字典进行更新。
  • 由于字典使用了散列表,而散列表又必须是稀疏的,这导致它在空间上的效率低下。如果需要存放数量巨大的记录,那么放在由元组或是具名元组构成的列表中会是比较好的选择。
    • 在用户自定义的类型中,__slots__ 属性可以改变实例属性的存储方式,由 dict 变成 tuple

集合的特点

  • 集合里的元素必须是可散列的。
  • 集合很消耗内存。
  • 可以很高效地判断元素是否存在于某个集合。
  • 元素的次序取决于被添加到集合里的次序。
  • 往集合里添加元素,可能会改变集合里已有元素的次序。

dictset 背后:散列表

  • 在具有一千万个浮点数的字典中使用 in 查找一个数花费约三分之一微秒(0.000000337s)。使用列表需要 0.01s。
  • Python 会设法保证大概还有三分之一的表元是空的,所以在快要达到这个阈值的时候,原有的散列表会被复制到一个更大的空间里面。
  • 内置的 hash() 方法可以用于所有的内置类型对象。如果是自定义对象调用 hash() 的话,实际上运行的是自定义的 __hash__
  • 如果两个对象在比较的时候是相等的,那它们的散列值必须相等。例如,如果 1 == 1.0 为真,那么 hash(1) == hash(1.0) 也必须为真。
  • 从 Python 3.3 开始,strbytesdatetime 对象的散列值计算过程中多了随机的“加盐”这一步。所加盐值是 Python 进程内的一个常量,但是每次启动 Python 解释器都会生成一个不同的盐值。随机盐值的加入是为了防止 DOS 攻击而采取的 一种安全措施。
  • 为了获取 my_dict[search_key] 背后的值,Python 首先会调用 hash(search_key) 来计算 search_key 的散列值,把这个值最低的几位数字当作偏移量,在散列表里查找表元(具体取几位,得看当前散列表的大小)。若找到的表元是空的,则抛出 KeyError 异 常。若不是空的,则表元里会有一对 found_key:found_value 。 这时候 Python 会检验 search_key == found_key 是否为真,如果它们相等的话,就会返回 found_value 。若发生散列冲突,则会在散列值取另一部分,来得散列表中的另一行。
  • 一个可散列的对象必须满足以下要求:
    1. 支持 hash() 函数,并且通过 __hash__() 方法所得到的散列值是不变的。
    2. 支持通过 __eq__() 方法来检测相等性。
    3. a == b 为真,则 hash(a) == hash(b) 也为真。 所有由用户自定义的对象默认都是可散列的,因为它们的散列值由 id() 来获取,而且它们都是不相等的。
  • 如果实现了一个类的 __eq__ 方法,并且希望它是可散列的,那么它一定要有个恰当的 __hash__ 方法,保证在 a == b 为真的情况下 hash(a) == hash(b) 也必定为真。另一方面,如果一个含有自定义的 __eq__ 依赖的类处于可变的状态,那就不要在这个类中实现 __hash__方法,因为它的实例是不可散列的。


 

这篇关于【python】 字典 与 集合 的特点,及它们背后的散列表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!