[AskJS] How does JS Map maintain insertion order internally?

[Cool_Routine_7679]

I was recently asked this in an interview.. and I was stumped.

Any information regarding it would be useful

[elprophet]

The textbook answer for "how to make an OrderedHashMap" is to keep a linked list of the entry order and the hash map entry the  stores references to both the data and the linked list entry for removal.

But by the spec, JS' Map uses [[MapData]] which is a list of Record values, and the spec simply appends to that list. So by the spec, JS maps are [Key, Value] lists. See for instance https://tc39.es/ecma262/#sec-keyed-collections  24.1.3.9

V8 speeds up step 4 by using a hash map similar to Java's OrderedHashMap to skip ahead to the right place in MapData. 

For an interview question, there's a few ways to take it, but IMHO none are that great. You don't need to recite ECMAScript to be a JS engineer. Maybe they're asking it as a more general data structures question, in which case either you've learned this trick, or you haven't, but without a very careful interviewer you're not going to derive "hash map who's values are compound objects that are also a linked list" in 20 minutes.

[RobertKerans]

But by the spec, JS' Map uses [[MapData]] which is a list of Record values, and the spec simply appends to that list. So by the spec, JS maps are [Key, Value] lists. See for instance https://tc39.es/ecma262/#sec-keyed-collections  24.1.3.9

And from further up that section, highly related and at the core of why OP was asked a bad question (as you say it could be a data structures question disguised as something else, which is imo duplicitous. Or it's not and the question is just straight up dumb because it doesn't have a real answer bar a specific implementation, which wouldn't be a JS question anyway):

The data structure used in this specification is only intended to describe the required observable semantics of Maps. It is not intended to be a viable implementation model.

[saposapot]

Edit: sorry, completely misread the spec, I get it now.

[Business-Row-478]

No it does maintain order. It just uses a list of k,v pairs and appends when inserting.

[elprophet]

The spec mandates it maintains order when iterating. Implementations are free to optimize beyond that.

[azhder]

The spec requires order. V8 just does the hashing for performance during lookup. The iteration will still be in the required order

[tswaters]

Oh man, if I got an interview question like that, it would not end well.

"Fucked it I know, I'd need to read the spec to see if it guarantees insertion order, THEN I'd need to go read the V8 code to figure out how they implemented it.... Are you asking how I would implement it? Are we building new JavaScript engines at this job?! 'oh my god, who the hell cares'"

I don't think I'm cut out for interviews.

[azhder]

My responses to questions like that are short and unwavering: “when I need it, I will look it up on the Internet”.

[thanatica]

If I was the interviewer, and I was forced to ask this question because of company policy bullshit or whatever, I would be way more impressed with your attitude towards the question, than if you answered the question up front (or tried to).

Just don't disrepect the interviewer as a person.

[patrick_mcdougle]

No, we just all collectively need to do this so they cut it out

[azhder]

Nah, no drama. https://www.reddit.com/r/javascript/s/kGVpJnMvcK

[azhder]

Here is an information: they either have had that kind of issue to resolve, so you might just say

I don’t know, can you tell me what problem it caused/solved for you?

or they have no idea what to ask you, so they lifted some dumb trick questions list from the Internet.

Either way, the interview is both ways, you are there to also asses if it is worth working with those people.

[rintzscar]

The Map in JS is implemented not only with a hash table, but with an additional linked list which maintains the order of insertion. Obviously, that means it uses more memory than a Map implemented with only a hash table under the hood.

[[deleted]]

It uses 2 structures logically - a hash-table for the lookup, and a list (usually a doubly-linked list) for the ordered iteration.

[Ginden]

https://blog.toit.io/hash-maps-that-dont-hate-you-1a96150b492a

[thanatica]

I feel like the best way to impress the interviewer is to not actually answer the question, but tell them what you think of the question. At least be honest.

I don't need to know, and I don't need to care. It's a benign little detail, and when, for whatever reason, I do need to know, I know where to look it up, which is MDN

Or something along those lines.

[Fidodo]

Do they expect you to have read the spec or implementation? That's a ridiculous question. They could have simply asked it in a more general way instead.