34

DOM 是否有一个元素的哈希表，其键是元素的 id？
我想知道是document.getElementById查找哈希表还是遍历整个树。
这种行为在浏览器中是否不同？

4

4 回答 4

25

我知道 Firefox 和 WebKit DOM 实现，它们都使用哈希表来查找元素，深入研究它们的来源，您可以查看内部实现：

WebKit 实现Document.cpp如果 是唯一的，则使用哈希表id，否则它遍历文档以获取第一个匹配项：

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 实现，nsDocument.cpp

于 2010-04-26T06:41:47.337 回答
13

实现可以自由地做任何他们喜欢的事情，但是由于id被定义为一个唯一的值，使用哈希映射或类似的查找机制而不是遍历似乎是明智的。然而，从外部看来，当您开始构建一个具有许多（有时是相互冲突的）命令的复杂 Web 浏览器时，可能并不明智。

我做了一个简单但非常简单的测试（参见答案末尾的页面）。这非常简单，尤其是因为我们不知道浏览器不会缓存以前的结果。

Chrome 4.1.249.1059报告：

ID: 0.0082ms per lookup
Tag: 0.0249ms per lookup

因此，ID 比标签名称快得多。

IE7报告：

ID: 2.4438ms per lookup
Tag: 0.0437ms per lookup

标记名称比 ID 快得多（但请记住 IE7 有一个错误的概念getElementById；这在 IE8 中已修复）。

IE8（在不同的机器上，不要比较绝对值，我们正在查看测试浏览器中的差异）报告：

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

所以它并不关心那么多（重复请求；再次，它可能正在缓存）。

Opera 10.5.1报告：

ID: 0.006ms per lookup
Tag: 1.467ms per lookup

ID 比标签名称快得多。

把这些结果做成你想要的。需要一个更复杂的测试用例来真正推断机制。当然，至少在其中两种情况下（Firefox 和 Chrome），我们可以去看看源代码。CMS 好心地向我们指出了WebKit和Firefox的实现（看着它，我对缓存的怀疑可能是在金钱上）。

测试页面：

<!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>
于 2010-04-26T06:35:28.587 回答
2

HTML 规范中没有定义具体的实现，因此它可以很容易地改变浏览器到浏览器。例如IE 文档状态

返回对具有指定 ID 或 NAME 属性值的第一个对象的引用。

所以我很想说它会进行搜索（或者它只是在哈希冲突的情况下抛出元素）。

编辑还请记住，还有其他数据结构（如树）允许访问时间介于常数和线性之间。

于 2010-04-26T05:45:25.207 回答
0

测试应该不难。

如果它是基于树的，那么制作一个非常深的树（通过 Javascript）应该是一个很好的测试用例。

于 2010-04-26T05:40:43.547 回答