Le DOM a-t-il une table de hachage des éléments dont les clés sont les identifiants des éléments?
Je veux savoir si document.getElementById recherche une table de hachage ou traverse l'arbre entier.
Ce comportement est-il différent d'un navigateur à l'autre?
Réponses
Trop de publicités?
CMS
Points
315406
Je sais que sur Firefox et WebKit DOM implémentations, les deux utilisent une table de hachage pour rechercher les éléments, de creuser dans la source d'eux, vous pouvez donner un coup d'oeil à l'intérieur de la implémentations:
WebKit mise en œuvre, Document.cpp, utilise la table de hachage si l' id est unique, sinon, il parcourt le document pour obtenir le premier 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 mise en œuvre, nsDocument.cpp
Les implémentations sont libres de faire ce qu'ils aiment, mais depuis id est définie comme une valeur unique, il semblerait raisonnable d'utiliser un hachage de la carte ou similaire, le mécanisme de recherche plutôt que de la traversée. Ce qui semble raisonnable à partir de l'extérieur, mais, peut-être pas quand vous arrivez dans la plomberie de la construction d'un complexe navigateur web avec de nombreux (parfois contradictoires) des impératifs.
J'ai fait un simple mais très simpliste de test (voir page à la fin de la réponse). C'est très simpliste, pas moins parce que nous ne savons pas que les navigateurs ne met pas en cache les résultats précédents.
Chrome 4.1.249.1059 rapports:
ID: 0.0082ms per lookup
Tag: 0.0249ms per lookup
Donc, beaucoup plus rapide par ID de nom de balise.
IE7 rapports:
ID: 2.4438ms per lookup
Tag: 0.0437ms per lookup
Donc beaucoup plus rapide par nom de balise que l'ID (mais n'oubliez pas IE7 a cassé concept d' getElementById; ceci est corrigé dans IE8).
IE8 (sur une machine différente, ne comparez pas des absolus, nous sommes à la recherche à des différences dans le navigateur testé) rapports:
ID: 1.1335ms per lookup
Tag: 0.0287ms per lookup
Donc, environ le même que IE7.
Firefox 3.6.3 rapports:
ID: 0.0042ms per lookup
Tag: 0.006ms per lookup
De sorte qu'il ne se soucie pas que beaucoup (sur demandes répétées; de nouveau, elle peut être mise en cache).
Opéra 10.5.1 rapports:
ID: 0.006ms per lookup
Tag: 1.467ms per lookup
Beaucoup plus rapide par ID de nom de balise.
Faire de ces résultats que vous voulez. De plus en plus complexes de cas de test serait nécessaire pour vraiment en déduire les mécanismes. Bien sûr, dans au moins deux de ces cas (Firefox et Chrome), nous pouvons aller chercher à la source. CMS de bien vouloir nous renvoie à la WebKit et Firefox implémentations (et en regardant, mes soupçons à l'égard de la mise en cache peut avoir été sur l'argent).
Page de Test:
<!DOCTYPE HTML>
<html>
<head>
<meta http-equiv="Content-type" content="text/html;charset=UTF-8">
<title>Test Page</title>
<style type='text/css'>
body {
font-family: sans-serif;
}
#log p {
margin: 0;
padding: 0;
}
</style>
<script type='text/javascript'>
window.onload = pageInit;
function pageInit() {
document.getElementById('btnGo').onclick = btnGoClick;
}
function btnGoClick() {
log("Testing...");
setTimeout(run, 0);
}
function run() {
var count, time;
try {
// Warm up
testid(10);
testtag(10);
// Test
count = 10000
time = testid(count);
log("ID: " + (time / count) + "ms per lookup");
time = testtag(count);
log("Tag: " + (time / count) + "ms per lookup");
}
catch (e) {
log("Error: " + (e.message ? e.message : String(e)));
}
}
function testid(count) {
var start;
start = new Date().getTime();
while (count-- > 0) {
if (!document.getElementById('fred')) {
throw "ID 'fred' not found";
}
}
return new Date().getTime() - start;
}
function testtag(count) {
var start;
start = new Date().getTime();
while (count-- > 0) {
if (document.getElementsByTagName('em').length == 0) {
throw "Tag 'em' not found";
}
}
return new Date().getTime() - start;
}
function log(msg) {
var log = document.getElementById('log');
log.innerHTML += "<p>" + msg + "<\/p>";
}
</script>
</head>
<body><div>
<input type='button' id='btnGo' value='Go'>
<div id='log'></div>
<hr>
<div>test test<span>test<span>test<span>test<span>test</span></span></span></span></div>
<div>test test<span>test<span>test<span>test<span>test</span></span></span></span></div>
<div>test test<span>test<span>test<span>test<span>test</span></span></span></span></div>
<div>test test<span>test<span>test<span>test<span>test</span></span></span></span></div>
<!-- repeat the above a couple of thousand times; I had about 2,200 -->
<div>test test<span>test<span>test<span>test<span>test</span></span></span></span></div>
<div>test test<span>test<span>test<span>test<em id='fred'>test</em></span></span></span></div>
</div></body>
</html>
R0MANARMY
Points
8440
La mise en œuvre spécifique n'est pas défini dans la spécification HTML donc il peut facilement varier d'un navigateur à l'autre. Par exemple IE documentation unis
Renvoie une référence vers le premier objet avec la valeur de l'ID ou le NOM de l'attribut.
donc je serais tenté de dire qu'il fait une recherche (ou elle jette des éléments dans les cas de collisions de hachage).
EDIT Également garder à l'esprit qu'il y a d'autres structures de données (comme les arbres) qui permettent l'accès en temps, quelque part entre la constante et linéaire.
David-SkyMesh
Points
3121
