1
$\begingroup$

To what extent is the MAP data type implementation language dependant???

If we know that C++ implements maps as Red Black Trees, unordered maps as hash tables, How C++ and alike maps are actually stored in memory? what about other languages?

Go as an example?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ "If we know that C++ implements maps as Red Black Trees, unordered maps as hash tables" – But we don't know that. There was a question about this just yesterday, and the answer was that the C++ language specification does not prescribe any particular implementation strategy (although the restrictions the standard specifies heavily suggest some form of search tree, there is absolutely nothing whatsoever that would force an implementor to choose an RB tree). For example, the original author of the STL has said that he would use a B* tree. $\endgroup$
    – Jörg W Mittag
    Sep 20, 2021 at 21:07
  • 1
    $\begingroup$ Hint: the name of the language is Go, not GO. It is not an acronym. $\endgroup$
    – Jörg W Mittag
    Sep 20, 2021 at 21:09
  • $\begingroup$ 1-Corrected GO to Go, & added a link to the previous question.2-from previous question the designer said he"would have changed" meaning he did not, quora said some kind of key ordered binary tree but all other references deep into coding details said RBT, if u have a ref saying otherwise pls add it there. 3-For Go, yes some links who didn't want to get in detail said it's implementation dependant; however this ref summarizes the presentation conference (as written in it) if u have a newer link that announces another varient or a change in design add it as a comment or a separate answer $\endgroup$
    – ShAr
    Sep 21, 2021 at 2:01

1 Answer 1

Reset to default
1
$\begingroup$

The Go language implements MAPS as hash tables using 8 buckets https://dave.cheney.net/2018/05/29/how-the-go-runtime-implements-maps-efficiently-without-generics

The bucket represents 3 bits mask of the key value, and each bucket points to a space of size 8; the numbers are doubled with the increase of size (always power of 2) enter image description here

enter image description here

The details of the bucket struct is as follows enter image description here Where the _type is: enter image description here

The designers describe their Go map as a compromise between C++ unordered maps and JAVA hashmap

Unlike Java, you can use scalar values like characters and integers without the overhead of boxing. Unlike C++, instead of N runtime.hashmap implementations in the final binary, there are only N runtime.maptype values, a substantial saving in program space and compile time

I found another helpful, and newer, reference too https://www.fatalerrors.org/a/a-comprehensive-analysis-of-golang-s-map-design.html enter image description here

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ Does this apply to all implementations of Go? Your answer makes it sound like this implementation were part of the language specification, but to my knowledge, there are or were at least 4 separate independent implementations of Go, and I highly doubt that all of them are identical. $\endgroup$
    – Jörg W Mittag
    Sep 20, 2021 at 21:08
  • $\begingroup$ So, not always with 8 buckets then? $\endgroup$
    – user253751
    Sep 21, 2021 at 11:11
  • $\begingroup$ I didn't say they're always 8, It's written in the answer that when the size increase the numbers are doubled. Exact words from ref Once the number of entries across each bucket passes some percentage of their total size, known as the load factor, then the map will grow by doubling the number of buckets and redistributing the entries across them. $\endgroup$
    – ShAr
    Sep 21, 2021 at 12:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.