无需迭代即可获取集合的元素

Question

假设您想要一个可能在集合中的元素。你没有元素本身，但你知道如何计算它的散列。你如何获得元素？

到目前为止，这是我的代码：

import random

class A(object):

    def __init__(self, x):
        self.x = x
        self.rand = random.random()


    def __hash__(self):
        return hash('A{}'.format(self.x))


    def __eq__(self, other):
        return self.__hash__()==other.__hash__()


# create many A instances
N = 10**7
s = set()
for x in xrange(N):
    s.add(A(x))


# test some ways to find a particular A
def find_A_given_x(x):
    """ Iterate over s to find A """
    for a in s:
        if a.x == x:
            return a


def find_A_given_x_without_iterating_s(x):
    """ Try to use hash to get the element??? """
    raise NotImplemented('I don\'t know how to do this!')

Answer 1

您不能通过散列从集合中检索对象。请注意，散列不需要是唯一的！在任何情况下，集都不是为检索特定的单个元素而设计的（除了从集合中返回一个任意元素）。

您唯一的选择是遍历集合的所有元素并测试散列是否匹配，并接受可能有多个这样的匹配。

无论如何，散列用于将对象减少到散列中的一个槽table；如果该插槽被不同的对象占用（tested_object == object_in_slot 为 false），则处理哈希以生成新的插槽等。底层哈希 table 是一个实现细节，不会以其他方式暴露给内省或其他应用程序。

无需迭代即可获取集合的元素

Get an element of a set without iteration

python

hash

set

python-2.7