Javascript getElementById查找 - 哈希映射或递归树遍历？ [英] Javascript getElementById lookups - hash map or recursive tree traversal?
问题描述
DOM是否有一个元素的哈希表，其元素是元素的ids？
我想知道如果 document.getElementById 一个哈希表或遍历整个树。
这个行为在浏览器之间是不同的吗？
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?
推荐答案
实现可以自由地做任何他们喜欢的，但是由于 id 被定义为一个唯一的值，所以使用散列图或类似的查找机制而不是遍历似乎是明智的。然而，从外部看来似乎是明智的，可能不是当您进入建立具有许多（有时是冲突的）需求的复杂网络浏览器的管道时。
Implementations are free to do whatever they like, but since id is defined as a unique value, it would seem sensible to use a hash map or similiar lookup mechanism rather than traversal. What seems sensible from the outside, though, may not be when you get into the plumbing of building a complex web browser with many (sometimes conflicting) imperatives.
我做了简单但非常简单的测试（请参阅答案末尾的页面）。 非常简单化，尤其是因为我们不知道浏览器不会缓存以前的结果。
I did an easy but very simplistic test (see page at end of answer). It's very simplistic not least because we don't know that browsers don't cache previous results.
Chrome 4.1.249.1059 报告：
ID: 0.0082ms per lookup
Tag: 0.0249ms per lookup
所以，ID比标签名称快得多。
So, dramatically faster by ID than tag name.
IE7 报告：
ID: 2.4438ms per lookup
Tag: 0.0437ms per lookup
标签名称比ID快得多（但记住IE7有一个破坏的概念 getElementById ;这是在IE8中修复的。
So dramatically faster by tag name than ID (but remember IE7 has a broken concept of getElementById; this is fixed in IE8).
IE8 （在不同的机器上 ，不要比较绝对，我们正在浏览测试中的差异）报告：
IE8 (on a different machine, don't compare absolutes, we're looking at diffs within the browser tested) reports:
ID: 1.1335ms per lookup
Tag: 0.0287ms per lookup
所以与IE7相同。
Firefox 3.6.3 报告：
ID: 0.0042ms per lookup
Tag: 0.006ms per lookup
所以不太在意（重复的请求; 再次，可能是缓存）。
So it doesn't care that much (on repeated requests; again, it may be caching).
Opera 10.5.1 报告：
ID: 0.006ms per lookup
Tag: 1.467ms per lookup
ID比标签名称快得多。
Dramatically faster by ID than tag name.
将这些结果做成你会做什么。需要一个更复杂的测试用例来真正推断机制。当然，至少在这两种情况（Firefox和Chrome）中，我们可以查看源。 CMS请将我们指向 WebKit 和 Firefox 实现（并查看它，我对缓存的怀疑可能是
Make of those results what you will. A more complex test case would be needed to really infer the mechanisms. Of course, in at least two of those cases (Firefox and Chrome), we can go look at the source. CMS kindly points us to the WebKit and Firefox implementations (and looking at it, my suspicion about caching may have been on the money).
测试页：
<!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>
这篇关于Javascript getElementById查找 - 哈希映射或递归树遍历？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
