CODEWITHSUNDEEP
pythonhashset
Sebastian Werk
Sebastian Werk

Reputation: 1796

Find item in set via hash

Is there a fast way to find an object of a set, if I know how the hash was calculated?

I have the following class, uid is an unique string (never used twice for different objects):

class Foo():
    def __init__(self, uid):
        self.uid = uid
        self.__hash = hash(self.uid)

    def __hash__(self):
        return self.__hash

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

I have a set created with different uids:

foos = {Foo('a'), Foo('b'), Foo('c')}

I now wonder, if I want to have the item, which was initialized with b, if there is a faster (and if possible more pythonic) way to get the element out of the sets than

b_object = next(foo for foo in foos if foo.uid == 'b')

since I could get hash_b = hash('b'), which should provide somehow faster access, if the set is really huge (which is in my particular case obviously the case).

Upvotes: 1

Views: 1240

Answers (1)

Reut Sharabani
Reut Sharabani

Reputation: 31339

I'm not sure what you're using this for, but you could do something like:

uid_to_foo = {foo.uid: foo for foo in foos}

# use 'uid_to_foo[some_foo.uid]' to find an instance fast

And now you get fast access to any Foo instance through it's uid.

Note that your current hash does not promise no collisions (although they are probably not likely).

You can even have this in the class itself:

class Foo():

    # add class dictionary mapping uids to foos
    uid_to_foo = {}

    def __init__(self, uid):
        self.uid = uid
        self.__hash = hash(self.uid)

        # add to class-level mapping
        Foo.uid_to_foo[uid] = self

    def __hash__(self):
        return self.__hash

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

To create a mapping for every sub-class you can do something like (as asked in comments), using defaultdict:

class Base():

    # add class dictionary mapping uids to instances
    uid_to_obj = defaultdict(dict)

    def __init__(self, uid):
        self.uid = uid
        self.__hash = hash(self.uid)

        # add specific sub-class mapping for each sub-class
        Foo.uid_to_obj[type(self).__name__][uid] = self

    def __hash__(self):
        return self.__hash

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

The class-specific dictionaries are now obviously under Foo.uid_to_obj[type(self).__name__].

Upvotes: 1

Related Questions