0

I recently learned about hash table implementation and I am really interested in how Typescript implements it. I found that differnt languages might use different implementations for hashing. Does Typescript use methods like quadratic probing, double hashing, or seperate chaining?

I tried to search about implementations used by Javascript/Typescript but could not find the answer I want.

Jin Zihang
  • 41
  • 1
  • 3
  • You should ask: How JavaScript implementing it? TypeScript is just an extension for javascript. Any TS code is getting erased after compilation. In other words, when you compile TS, it compiles to JS. And hashing is a part of JS engine, not a TS – captain-yossarian from Ukraine Oct 30 '22 at 09:08
  • For instance, you can check how it is implemented in V8 engine, see [here](https://v8.dev/blog/hash-code). Also, I don't know whether hashing algorithm is a part of ECMA script specification. @T.J. Crowder might help you, here is his [twitter](https://twitter.com/tjcrowder?lang=en) account – captain-yossarian from Ukraine Oct 30 '22 at 09:10

1 Answers1

1

JS/TS is generally running on Chromium JS engine calledV8

Here's an ansver that answers your question

es6 Map and Set complexity, v8 implementation

Is it a fair assumption that in v8 implementation retrieval / lookup is O(1)?

Yes. V8 uses a variant of hash tables that generally have O(1) complexity for these operations.

For details, you might want to have a look at https://codereview.chromium.org/220293002/ where OrderedHashTable is implemented based on https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables.

Dimava
  • 7,654
  • 1
  • 9
  • 24