4

Can somebody please explain to me the internal implementation of HTML getElementById() method ? Is it traversing whole DOM tree to find the specified element or is it intelligent enough to look for near-by elements first ?

Thank you

bfontaine
  • 18,169
  • 13
  • 73
  • 107
nimo
  • 45
  • 1
  • 3
  • possible duplicate of [Javascript getElementById lookups - hash map or recursive tree traversal?](http://stackoverflow.com/questions/2711303/javascript-getelementbyid-lookups-hash-map-or-recursive-tree-traversal) – T.J. Crowder Jan 02 '11 at 11:17
  • Probably, Unfortunately topic title was too specific than I thought when googling.. :) – nimo Jan 02 '11 at 11:25
  • Well as @Matthew points out below, things are moving so quickly in browsers as they respond to changes in use patterns that it may well justify an update. :-) – T.J. Crowder Jan 02 '11 at 11:31

3 Answers3

8

The implementation is entirely (er) implementation-dependent. Some browsers may use a hashmap or similar, or they may not (because although id is required to be unique, there are lots of poorly-authored pages out there that provide invalid markup with duplicated ids). Internet Explorer 6 and 7 don't even limit getElementById to id values, they conflate namespaces terribly, although Microsoft has clearly seen the light and both IE8 and IE9 improve that.

For browsers that are implemented open source, you can find out, of course. Here's a link to the WebKit source, and here's one to Mozilla's (that line number may vary a bit, if you don't land right on it, just search for GetElementById and GetElementByIdInternal). Both of those come from this related answer here on StackOverflow. (In fact, looking at that question, I think this one may be a duplicate, although as Matthew points out in a comment below, things are moving fast enough that it might justify an update...)

Community
  • 1
  • 1
T.J. Crowder
  • 1,031,962
  • 187
  • 1,923
  • 1,875
  • But I don't know *any* browser that will return a collection from `document.getElementById`. Even IE, which as you note, violates the spec, will return null or an element. So I still don't see why any browser (even IE 6) couldn't use a hash map. – Matthew Flaschen Jan 02 '11 at 11:14
  • @Matthew: Neither do I (I'd just grab the first one and not set any further ones; if they delete an element, I'd probably do a search to see if that unveiled a previously-hidden ID), but then, I've never written a browser. – T.J. Crowder Jan 02 '11 at 11:15
  • You have a point about falling back on another element with the same id when one is deleted. That (if real browsers do it) could be reason to use a more complex data structure. – Matthew Flaschen Jan 02 '11 at 11:20
  • It looks like the WebKit implementation at least has changed, so I don't think it's an exact duplicate. – Matthew Flaschen Jan 02 '11 at 11:28
  • I also updated the Mozilla URL to always go to tip (latest version) so it won't go out of date as fast. Your WebKit link was already the latest. – Matthew Flaschen Jan 02 '11 at 11:35
  • @Matthew: Thanks. That's weird, I thought it *was* linking to the tip. Ah, well. – T.J. Crowder Jan 02 '11 at 11:37
  • @T.J.Crowder - The source code for firefox is written in Cpp, then why do people call this a 'JavaScript' method.? – user3170122 May 26 '18 at 15:27
  • 1
    @user3170122 - They shouldn't. It's a DOM method. It's not defined by the JavaScript spec, and it's usually implemented in some other language, not JavaScript (DOM libraries for Node.js and such would be the exception). But people also say "pure JavaScript" when what they really mean is "using the DOM directly, not via a library," so... :-) It's just a fundamental confusion in people's minds, and in my experience, an intractable one. – T.J. Crowder May 26 '18 at 15:31
  • ah, makes sense! So it's just a DOM interface implementation and has nothing to do with JavaScript in particular.? – user3170122 May 26 '18 at 15:33
  • 1
    @user3170122 - Right. It's just commonly *used from* JavaScript. :-) – T.J. Crowder May 26 '18 at 15:39
7

It depends on the browser, but most probably use a hash map from id->element. It's true that there are many invalid pages that have duplicate ids. However, the browser will still only return one element, not a collection.

I don't know what you mean by "near by elements" since the method only exists on document.

If you're interested, you can find the implementation for free software browsers such as Firefox and Chrome.

Matthew Flaschen
  • 278,309
  • 50
  • 514
  • 539
1

That depends. The method is implemented by each web browser vendor, so the details may be different from one to another and possibly from one version of a browser to another.

I'd suggest taking a look at the source code for a browser such as Mozilla Firefox and see if you can find the implementation.

jamesmortensen
  • 33,636
  • 11
  • 99
  • 120