Q:

Most efficient method to get key for similar values in a dict

I have a dictionary of objects:
# I have thousands of objects in my real world scenario
dic = {'k1':obj1, 'k2':obj2, 'k3':obj3, ...}
# keys are string
# objs are MyObject

Edit: Sorry for letting doubt in the question.  Here is the exact class and the like() function:
class MyObject(object):
    def __init__(self, period, dimensions):
        self.id = None
        self.period = period # period is etree. Element
        self.dimensions = dict() # id -> lxml. XMLElements
        for dim in dimensions:
            # there must be only one child: the typed dimension
            self.dimensions[dim.get('dimension')] = dim[0]
        self._hash = None

    def __eq__(self, other):
        return isinstance(other, MyObject)
            and self.period == other.period
            and self.dimensions == other.dimensions

    def like(self, other):
        return (other is not None \
            and self.period == other.period \
           and self.dimensions.keys() == other.dimensions.keys())

I wonder how I can have the best implementation for finding objects in dictionary dic that are similar to a given value val.  Something equivalent to:
def find_keys(dic, val):
    return [v for v in dic if v.like(val))

However this method is too slow, because I have thousands of iterations over find-keys() and thousands objects in the dictionary. 
Right now, I have implemented a __hash__(self) on these objects, and added the key as a property:
    def __hash__(self):
        if self._hash is None:
            self._hash = hash(self.periodtype) ^ \
                hash(tuple(sorted(self.dimensions.values())))
        return self._hash

Then, I have built a lookup dictionary that is
hash_dic = { hash(obj1): [obj1], hash(obj2): [obj2, obj3] }

And this new search method is much faster:
def find_keys_fast(dic, val):
    prefetched=hash_dic[hash(val)]
    return [x.key for x in prefetched if x.like(val)]

Since __hash__ is a native function internally used by Sets and Dictionaries, is there anything faster or more elegant I could do? 

A:

Since I don't know the structure of your data or the nature of the similarity you are seeking, I can only guess at what might work.  But perhaps you could build some kind of prefix tree using dictionaries.  As in:
trie = {'a':{'b':{'e':{}, 's':{}}, 'c':{'t':{}, 'k':{}}}}

These are most commonly used for looking up strings with common prefixes, but perhaps there's some sense in which the data in your objects can be represented as a string.  This seems like it would work especially well if there's some order the data can be put in such that earlier data in the string must compare as ==.  I think I can even imagine the leaves of the trie including all similar, rather than all strictly equivalent, objects. 
A small toy example of how to work with a trie:
>>> trie = {'a':{'b':{'e':{}, 's':{}}, 'c':{'t':{}, 'k':{}}}}
>>> def rec_print(trie, accum=''):
...     if trie:
...         for k in trie:
...             rec_print(trie[k], accum + k)
...     else:
...         print accum
... 
>>> rec_print(trie)
ack
act
abs
abe

A:

Now that we can see the implementation of like, a quite simple approach seems feasible---far simpler than my other answer, for one.  Define a new signature method on MyObject:
def signature(self):
    return (self.period, frozenset(self.dimensions.keys()))

And then iterate through the objects:
import collections
sig_keys = collections.defaultdict(set)
for k, obj in dic.iteritems():
    sig_keys[obj.signature()].add(k)

With that, sig_keys.values() gives all the sets of identifiers for objects which are alike.  Lists of objects could instead be directly constructed, if that would better:
sig_objs = collections.defaultdict(list)
for obj in dic.itervalues():
    sig_objs[obj.signature()].append(obj)

If you want, you could define __hash__ to return hash(self.signature()) or the equivalent. 