title: Is there any kind of hash list in python
body: <p>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.</p>
  
  <h1>Background</h1>
  
  <p>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:</p>
  
  <pre><code>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]
  </code></pre>
  
  <p>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 <code>get_children</code> 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(n<em>a</em>k + m<em>a</em>k)). 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))</p>
  
  <h1>Question</h1>
  
  <p>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 <code>x in list</code>?<br/>
  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.</p>
  
  <p>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.</p>