1
$\begingroup$

I admit I didn't know much before what a Map is living with just the terminology Hash Tables, even when I first Google it I found this https://www.mathworks.com/help/matlab/matlab_prog/overview-of-the-map-data-structure.html#:~:text=A%20Map%20is%20a%20type,indexing%20into%20its%20individual%20elements.&text=These%20keys%2C%20along%20with%20the,key%20and%20its%20corresponding%20value. and thought it's just specific to MATLAB syntax

Then I found https://www.quora.com/What-is-a-map-data-structure-How-does-it-store-data and knew it is a terminology for probably a hash table (they say or a binary search tree, I'm not sure how as an implementation)

& There is a library in C++ for them https://www.udacity.com/blog/2020/03/c-maps-explained.html

https://www.geeksforgeeks.org/map-associative-containers-the-c-standard-template-library-stl/

Now my question how they are actually stored in memory to achieve such a fast indexing on the key as a hash value???

I mean if it's just stored as a 1D array of struct (N* sum of fields size), then it will not function as a hash table in access time. It must add an extra book keeping space( trading space with time) in addition to the user data to add the hash table fast access time

If possible, give me a fn of N, no of elements, say for

type myStruct struct {.
data myData.
myPointer *myStruct }

map[uint64] *myStruct

I mean it's kind of "not best choice" to use a map to help in traversing a tree, this way I'm allocating a space for 2 trees, and I'm not sure the running time requirements will follow my tree kind that I worked so hard to think of, or the kind of tree the C++ implementation used???

Improve this question
$\endgroup$
4
  • $\begingroup$ if [a map is] just stored as a 1D array of struct (N* sum of fields size), then it will not function as a hash table in access time Please elaborate: What in an implementation of a hash table makes that not a 1D array? $\endgroup$
    – greybeard
    Sep 21, 2021 at 5:30
  • $\begingroup$ I meant in general before I knew how they're implemented in C++, any hash table trade space with time; ie have to use extra space either thru buckets/extra empty slots/.... unless the data specifies previously known values of a collision free hash function. I didn't dig more than written here into the details of unordered maps in C++. And of course by Sum of fields size I mean the user original data fields $\endgroup$
    – ShAr
    Sep 21, 2021 at 6:06
  • $\begingroup$ What is N? What is "sum of fields size"? Why do you think "it will not function as a hash table in access time"? $\endgroup$
    – xskxzr
    Sep 23, 2021 at 1:44
  • $\begingroup$ I just wrote in the comment above u, N is the number of data items and by some of data fields I mean user original data. So, basically I was asking about the space overhead of maps, and how exactly they're Structured in memory at runtime $\endgroup$
    – ShAr
    Sep 23, 2021 at 5:12

2 Answers 2

Reset to default
2
$\begingroup$

In C++, std::map is an ordered map. It requires that keys are comparable with a less-than operator (C++ calls this strict weak ordering), and can traverse all entries in the map in order, in linear time. The requirements were written in such a way that they essentially dictate that the implementation uses some kind of ordered search tree.

All of the implementations that I am aware of use red-black trees, although there's no reason why it needs to be that balancing scheme specifically.

Hash tables do not preserve key order, but they do support constant-time access. For that reason, C++ also supported unordered maps, imaginatively called std::unordered_map. Keys in an unordered map no not need to be comparable with a less-than operator; an equality operator and a hash function are (unsurprisingly) sufficient.

Once again, the C++ standard is written in such a way that it essentially dictates a hash table with buckets and some kind of separate chaining, but does not dictate any details beyond that. (EDIT: Thanks to @rici for correcting an earlier version on this point.)

Improve this answer
$\endgroup$
12
  • $\begingroup$ I mean how it's physically stored in RAM? If it is stored as Red-Black trees as I understand from your answer, then it uses (2N-1)*[size of(myStruct)+2*pointerSize] that's too much memory even if we omit the 2N null/nil pointers for the leaves? that's too much space $\endgroup$
    – ShAr
    Sep 19, 2021 at 12:06
  • $\begingroup$ @ShAr Maps do have some space overhead over traditional arrays. Doesn't matter how you implement it (hashtables/trees/...). If you just store integer/integers as key/values, then you have some big overhead (e.g. double the space because of pointers), but if you store some very big objects the overhead is mostly neglectable. $\endgroup$
    – Jakube
    Sep 19, 2021 at 12:22
  • $\begingroup$ Still it's kind of "not best choice" to use a map to help me reference my tree, this way I'm allocating a space for 2 trees, and I'm not sure the running time requirements will follow my kind of tree I worked so hard to think of or the kind of tree the C++ implementation used? $\endgroup$
    – ShAr
    Sep 19, 2021 at 12:27
  • 1
    $\begingroup$ @Pseud: The C++ standard does effectively require an unordered_map to be separately chained. See [unord.req] (22.2.7 in the version I'm looking at) para. 7: "The elements of an unordered associative container are organized into buckets. Keys with the same hash code appear in the same bucket. The number of buckets is automatically increased as elements are added to an unordered associative container, so that the average number of elements per bucket is kept below a bound...." $\endgroup$
    – rici
    Sep 20, 2021 at 3:10
  • 1
    $\begingroup$ Also, look at the bucket interface, including b.bucket_size(n), b.begin(n), b.end(n), etc., which allow iterating through an individual bucket. $\endgroup$
    – rici
    Sep 20, 2021 at 3:15
-1
$\begingroup$

I found in this reference

https://www.tutorialspoint.com/cpp_standard_library/map.htm

That maps are implemented as Binary Search Trees, unordered maps as hash tables

To clarify things, I am not trying to implement my own map like this site https://codeforces.com/blog/entry/70947

I was asking how C++ do it.

Anyways, whether it is a Binary Search Tree or a Red Black Tree it is 2N more pointers (for left&right of the tree) + the pointer already in the struct = 3N pointers.

(It's also worth clarifying that Red Black Trees have a ≥ right subtree condition, they just handle insertion & deletion in a different way hoping to achieve a more balanced tree: https://en.m.wikipedia.org/wiki/Red%E2%80%93black_tree, https://www.geeksforgeeks.org/red-black-tree-set-1-introduction-2/)

I was asking for a specific problem where the original designer worked so hard to find & design & prove a certain tree strucutre is better to use than RBT or BST, then come those developers implementing the theoritical idea by adding a map to the original design tree; that's even worse than before we get back to all the problems that motivated the original design (of why not using BST or RBT and design this), + doubling the space of older methods the original design were trying to optimize.

(because developers have already implemented another tree structure in their code; this way the program when running will allocate a space in memory for their coded tree and for the C++ map tree.

Anyways, this is their problem & has nothing to do with the group. I hope this question has informed/reminded of the fact that a map is implemented as a tree, unordered map as a hash table, and rang a bell to software developers to check how language library data structures are really implemented in memory to be aware of the consequences when using them.

Thank you all

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Alexander Stepanov has done several interviews about his design of the STL (which became part of the C++ standard library). He designed map, but not unordered_map. In the Slashdot interview linked, he noted that if he had his time over, he would do some things differently. "Cache misses are very costly [...] If I were designing STL today, [...] an in-memory B*-tree is a far better choice than a red-black tree for implementing an associative container." interviews.slashdot.org/story/15/01/19/159242/… $\endgroup$
    – Pseudonym
    Sep 20, 2021 at 3:20
  • $\begingroup$ A BST doesn't require 2N-1 nodes. You don't need leaf nodes (except in the sense that a leaf has no children.) Each node contains both a value and two child pointers. It's true that there are a lot of nullptr's, and a smaller (but not simpler) data structure could be used. I don't think any major implementations attempt that (although I admit that I haven't looked at the implementations in detail for many years now), but I'm pretty sure you won't find an implementation that allocates twice as many nodes as data values. $\endgroup$
    – rici
    Sep 20, 2021 at 3:29

Your Answer

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

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