Javascript getElementById lookups - hash map or recursive tree traversal?

Question

Does the DOM have a hash-table of elements whose keys are the elements' ids?
I want to know if document.getElementById looks up a hash table or traverses the entire tree.
Is this behavior different across browsers?

Answer 1

I know about the Firefox and WebKit DOM implementations, both of them use a hashtable to lookup the elements, digging into the source of them you can give a look to the internal implementations:

WebKit implementation, Document.cpp, uses the hashtable if the id is unique, otherwise it traverses the document to get the first match:

Element* Document::getElementById(const AtomicString& elementId) const {     if (elementId.isEmpty())         return 0;      m_elementsById.checkConsistency();      Element* element = m_elementsById.get(elementId.impl());//<-- hastable lookup     if (element)         return element;      if (m_duplicateIds.contains(elementId.impl())) {         // We know there's at least one node with this id,         // but we don't know what the first one is.         for (Node *n = traverseNextNode(); n != 0; n = n->traverseNextNode()) {             if (n->isElementNode()) {                 element = static_cast<Element*>(n);                 if (element->hasID() &&                 element->getAttribute(element->idAttributeName()) == elementId) {                     m_duplicateIds.remove(elementId.impl());                     m_elementsById.set(elementId.impl(), element);                     return element;                 }             }         }         ASSERT_NOT_REACHED();     }     return 0; } 

Firefox implementation, nsDocument.cpp