34

DOM には、キーが要素の ID である要素のハッシュ テーブルがありますか? がハッシュ テーブルを検索するのか、それともツリー全体をトラバースするのか
を知りたいです。 この動作はブラウザーによって異なりますか?document.getElementById

4

4 に答える 4

25

私は Firefox と WebKit の DOM 実装について知っています。どちらもハッシュテーブルを使用して要素を検索し、それらのソースを掘り下げて、内部実装を確認できます。

WebKit の実装であるDocument.cppidは、一意の場合はハッシュ テーブルを使用します。それ以外の場合は、ドキュメントを走査して最初の一致を取得します。

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の方が劇的に高速です。

それらの結果をあなたが望むものにしてください。メカニズムを実際に推測するには、より複雑なテストケースが必要になります。もちろん、これらのケースの少なくとも2つ（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 に答える