У DOM есть хеш-таблица элементов, ключи которых являются идентификаторами элементов?
Я хочу знать, если document.getElementById просматривает хеш-таблицу или пересекает все дерево.
Это поведение отличается от браузера?
Javascript getElementById lookups - хэш-карта или рекурсивный обход дерева?
Ответ 1
Реализации могут делать все, что им нравится, но поскольку 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
Так значительно быстрее по имени тега, чем 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
Значительно быстрее по идентификатору, чем имя тега.
Сделайте те результаты, что пожелаете. Для того, чтобы действительно установить механизмы, потребуется более сложный тестовый пример. Конечно, по крайней мере в двух случаях (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
Я знаю о реализациях 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 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
Ответ 3
Конкретная реализация не определена в спецификации HTML, чтобы она могла легко изменять браузер в браузере. Например документация IE утверждает
Возвращает ссылку на первый объект с указанным значением атрибута ID или NAME.
поэтому у меня возникнет соблазн сказать, что он выполняет поиск (или он просто выбрасывает элементы в случае хеш-коллизий).
EDIT Также имейте в виду, что существуют другие структуры данных (например, деревья), которые позволяют время доступа где-то между постоянным и линейным.
Ответ 4
Трудно проверить.
Если он основан на деревьях, то создание очень глубокого дерева (через Javascript) должно быть хорошим тестовым примером.