dom - 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