为什么浮点字典键会覆盖具有相同值的整数键？

Question

我正在通过http://www.mypythonquiz.com工作,问题#45要求输出以下代码:

confusion = {}
confusion[1] = 1
confusion['1'] = 2
confusion[1.0] = 4

sum = 0
for k in confusion:
    sum += confusion[k]

print sum

输出是6,因为密钥1.0替换1.这对我来说有点危险,这是一个有用的语言功能吗？

Answer 1

首先:在散列函数的文档中明确记录了行为:

hash(object)

返回对象的哈希值(如果有的话).哈希值是整数.它们用于在字典查找期间快速比较字典键.该比较相等的数字值具有相同的散列值(即使它们是不同的类型,如对于壳体1 和1.0).

其次,在文档中指出了哈希的局限性 object.__hash__

object.__hash__(self)

通过内置的函数调用hash()和操作杂乱的集合成员,包括set,frozenset和dict. __hash__() 应该返回一个整数.唯一需要的属性是比较相等的对象具有相同的哈希值;

这不是python独有的.Java也有同样的警告:如果你实现hashCode那么,为了使事情正常工作,你必须以这样的方式实现它:x.equals(y)implies x.hashCode() == y.hashCode().

所以,蟒蛇决定1.0 == 1成立,因此它不得不提供一个实现hash这样hash(1.0) == hash(1).副作用是1.0与键1完全相同dict的行为,因此行为.

换句话说,行为本身不必以任何方式使用或使用.这是必要的.如果没有这种行为,可能会出现意外覆盖不同密钥的情况.

如果我们有,1.0 == 1但hash(1.0) != hash(1)我们仍然可以发生碰撞.如果1.0和1碰撞,dict将使用相等来确定它们是否是相同的密钥和kaboom,即使您打算将它们变为不同,该值也会被覆盖.

避免这种情况的唯一方法就是拥有1.0 != 1,以便dict即使在碰撞的情况下也能够区分它们.但是被认为1.0 == 1比避免你所看到的行为更重要,因为你几乎从不使用floats和ints作为字典键.

由于python试图通过在需要时自动转换它们来隐藏数字之间的区别(例如1/2 -> 0.5),即使在这种情况下也能反映出这种行为.它与python的其余部分更加一致.

此行为将出现在任何实现中,其中键的匹配至少部分(如在哈希映射中)基于比较.

例如,如果a dict是使用红黑树或其他类型的平衡BST实现的,当1.0查找键时,与其他键的比较将返回与之相同的结果1,因此它们仍将以相同的方式起作用.

哈希映射需要更加小心,因为它是用于查找键的条目的哈希值,并且仅在之后进行比较.因此,破坏上面提到的规则意味着你会引入一个很难发现的错误,因为有时dict可能看起来像你期望的那样工作,而在其他时候,当尺寸改变时,它会开始表现不正确.

请注意,将是解决这一问题的方式:对每种类型插在字典中的单独的散图/ BST.通过这种方式,不同类型的对象之间不会发生任何冲突,并且==当参数具有不同类型时,比较无关紧要.

然而,这会使实现复杂化,因为哈希映射必须保留相当多的空闲位置以便具有O(1)访问时间,所以它可能是低效的.如果它们变得太满,性能会下降.拥有多个哈希映射意味着浪费更多空间,而且在开始实际查找密钥之前,您还需要首先选择要查看的哈希映射.

如果您使用BST,则首先必须查找类型并执行第二次查找.因此,如果您要使用多种类型,您最终会得到两倍的工作(并且查找将采用O(log n)而不是O(1)).

Answer 2

您应该考虑dict根据逻辑数值存储数据的目的,而不是您如何表示它.

ints和floats 之间的区别确实只是一个实现细节而不是概念.理想情况下,唯一的数字类型应该是一个任意精度数,具有无限精度甚至是亚统一...但是这很难实现而不会遇到麻烦...但可能是Python将来唯一的数字类型.

因此,尽管出于技术原因而有不同的类型,Python会尝试隐藏这些实现细节,并且int- > float转换是自动的.

如果在一个Python程序这将是更更令人惊讶的if x == 1: ...是不会时要采取x一个float值为1.

请注意,还与Python 3的值1/2就是0.5(两个整数的除法),而且类型long和非Unicode字符串已被丢弃具有相同试图隐藏实现细节.

Answer 3

在python中:

1==1.0
True

这是因为隐式转换

然而:

1 is 1.0
False

我能看到为什么之间自动注入float和int简便,这是比较安全的投int入float,然而也有其他语言(如去)是远离隐式转换了.

它实际上是一种语言设计决定,而不仅仅是不同的功能

Answer 4

字典使用哈希表实现.要在哈希表中查找某些内容,请从哈希值指示的位置开始,然后搜索不同的位置,直到找到相等的键值或空桶.

如果您有两个比较相等但具有不同哈希值的键值,则可能会得到不一致的结果,具体取决于其他键值是否在搜索位置中.例如,当表格变满时,这种情况更有可能发生.这是你想要避免的.似乎Python开发人员考虑到了这一点,因为内置hash函数返回相同数字值的相同哈希值,无论这些值是否为int或float.请注意,这扩展到其他数字类型,False等于0和True等于1.甚至fractions.Fraction并decimal.Decimal坚持这个财产.

如果要求a == b则hash(a) == hash(b)在定义中记载object.__hash__():

通过内置的函数调用hash()和杂乱的集合的成员包括运营set,frozenset和dict.__hash__()应该返回一个整数.唯一需要的属性是比较相等的对象具有相同的哈希值; 建议以某种方式将对象的组件的哈希值混合在一起(例如,使用异或),这些哈希值也在对象的比较中起作用.

TL; DR:如果比较相等的键没有映射到相同的值,则字典会中断.