Поиск getElementById в Javascript - хэш-карта или рекурсивный обход дерева? - PullRequest
33 голосов
/ 26 апреля 2010

Есть ли в DOM хеш-таблица элементов, ключами которых являются идентификаторы элементов?
Я хочу знать, просматривает ли document.getElementById хеш-таблицу или пересекает все дерево.
Отличается ли это поведение в разных браузерах?

Ответы [ 4 ]

24 голосов
/ 26 апреля 2010

Я знаю о реализациях 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

12 голосов
/ 26 апреля 2010

Реализации могут делать все, что им нравится, но поскольку id определяется как уникальное значение, представляется разумным использовать хеш-карту или подобный механизм поиска, а не обход. Однако то, что кажется разумным извне, может не сработать, когда вы приступаете к созданию сложного веб-браузера со многими (иногда противоречивыми) требованиями.

Я сделал простой , но очень упрощенный тест (см. Страницу в конце ответа). Это очень упрощенно не в последнюю очередь, потому что мы не знаем, что браузеры не кэшируют предыдущие результаты.

Chrome 4.1.249.1059 отчеты:

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

Итак, по идентификатору значительно быстрее, чем по имени тега.

IE7 отчеты:

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

Значительно быстрее по имени тега, чем по идентификатору (но помните, что 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

Значительно быстрее по идентификатору, чем по имени тега.

Делайте из этих результатов то, что вы будете. Более сложный контрольный пример был бы необходим, чтобы действительно вывести механизмы. Конечно, по крайней мере в двух из этих случаев (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>
2 голосов
/ 26 апреля 2010

Конкретная реализация не определена в HTML-спецификации , поэтому она может легко менять браузер на браузер. Например IE документация состояния

Возвращает ссылку на первый объект с указанным значением атрибута ID или NAME.

поэтому я хотел бы сказать, что он выполняет поиск (или просто выбрасывает элементы в случае коллизий хэшей).

РЕДАКТИРОВАТЬ Также имейте в виду, что существуют другие структуры данных (например, деревья), которые допускают время доступа где-то между постоянным и линейным.

0 голосов
/ 26 апреля 2010

Это не должно быть трудно проверить.

Если оно основано на дереве, то создание дерева глубиной очень (через Javascript) должно быть хорошим тестовым примером.

...