I tried to find an answer here and in Python doc but the only things I got were questions about hashing list objects and details abaut how dicts work.

Background

I'm developing a program that parses over a huge graphs (atm. 44K nodes, 14K of them are of any interest and they are connected by 15K edges) and have problems with performance although I allready optimized my algorithm as far as I could and now the last resort is to optimize the data structure:

def single_pass_build(nodes):
    for node in nodes:
        if node.__class__ in listOfRequiredClasses:
            children = get_children(node)
            for child in children:
                if child__class__ in listOfRequiredClasses:
                    add_edge(node, child)

def get_children(node):
    return [attr for attr in node.__dict__.values() if attr.__class__ in listOfRequiredClasses]

I still have to care about my add_connection function but even without it my program takes slightly over 10 Minutes for nothing but this iteration. For comparison: the module I get the data from generates it from an xml document in not more than 5 seconds. I have a total of 44K object, each representing a node in a ralation graph. The objects I get have plenty attributes so I could try to optimize get_children to know all relevant attributes for every class or just speed up the lookup. Lists take O(n) (so if a is the number os attributes and k the number of classes in my list I get a total O(nak + mak)). Many of my attribute classes are not in that list so I am closer to the worst case than to the average. I'd like to speed up the lookup from O(k) to O(1) or at least O(log(k))

Question

Knowing that a key lookup of dict should be O(log(n)) for many hash collision and with (few to) no hash collisions it becomes (almost) static. After I don't care for any values I'd like to know if there is a kind of (hash) list optimized for x in list?
I could use a dict with None values but with a total of 70000 lookups and greater graphs in future, every milli second counts. The space is not the big problem here because I expect ~50 classes total and in no case more than some hundred classes. In other cases, the space could be a issue too.

I don't expect the answer to be in standard Python but maby someone knows a common framework that can help or can make me believe that there is no reason at all why I can't use a dict for the job.