How does document.getElementById() search the DOM tree?

Question

I know some browsers (most today?) make a Hash table of all elements with an ID. So in this case a call to document.getElementById() could just search the Hash table. But how will it do this otherwise in the context of the DOM tree - is it a depth first search for example?

I'm asking because I want to know where the quickest place to put a DOM element would be, so it is found in a search as soon as or close to when the search itself starts.

Had a quick look and could not find any info on this subject specifically.

Much obliged for any help.

Answer 1

Since DOM implementation is browser dependent thing, every browser may implement it in a different manner. There is also a chance that browser do have a hash map for all IDs and performs document.getElementById using it.

In order to understand in which order browser looks up in the DOM, you can take a look at document.all collection that contains plain list of all DOM elements in the document. In case of Chrome, Safari and Firefox it seems to be DFS.

Another interesting question is: if two elements in the same document have the same ID, which one will be returned by document.getElementById. Using the snippet below it is possible to see, that it is the first element found using DFS algorithm (at least in the browsers mentioned bellow).

HTML

<div>
  <div id="id" data-index="DFS"></div>
</div>
<div id="id" data-index="BFS"></div>

JavaScript

console.log(document.getElementById('id').getAttribute('data-index'));

Console Output

DFS

Plunker

http://plnkr.co/edit/jaUolyxwrZcXsNXwkmtm?p=preview

Edit:

Regarding additional question in the comment to the answer

I am not sure if the search will stop at the location of the first result, which would of course be quicker...is there a way to test this at all?

Below you can find a code snippet that creates 10000 elements one inside another and one sibling element. In one case the same ID is set to the deepest element and sibling element, in another to all elements. The second case is ~10x time faster than the first one. This proves that the search stops after the first element with matching ID is found.

JavaScript

function Div(el) {
    var div = document.createElement('div');
    el.appendChild(div);
    return div;
}

var i, body, el, t0, t1;

el = body = document.querySelector('body');
for(i=0; i<10000; i++) {
    el = new Div(el);
    el.setAttribute('id', 'ix'); // <- setting id="id" in this line will produce ~10x time difference
}
el.setAttribute('id', 'id');

el = new Div(body);
el.setAttribute('id', 'id');

t0 = performance.now();
document.getElementById('id');
t1 = performance.now();

console.log('Time to find element by ID: ' + (t1 - t0) + 'ms');

Plunker

http://plnkr.co/edit/jmGRJvq0qB7qMyyMULhz?p=info