1

It seems like java is doing something smart with its HashMap by oscillating between linked list vs. red-black tree based on the size in the same bucket.

What is the underlying data structure of std::unordered_map? Is it also doing something smart?

Baiyan Huang
  • 6,463
  • 8
  • 45
  • 72
  • 1
    Rule of thumb: anything Java does we can do better. (I've upvoted both question and answer but I do think you ought to make the answer more comprehensive.) – Bathsheba Dec 11 '20 at 09:28
  • 1
    Before looking at how "smart" this is, perhaps it would be a good idea to actually measure the performance. Especially if it uses linked lists, which are particularly slow on modern CPUs. I have seen countless "smart" optimizations performing 10 times slower than the "not smart" approach. – spectras Dec 11 '20 at 09:54
  • 1
    Even as a self-answered Q&A, you still need a standalone good question, as in: you would upvote your own question by itself. What are the specific goals you have in mind? Why do you care about "smartness"? Have you measured anything? – Passer By Dec 11 '20 at 10:31

1 Answers1

-2

I don't think this is specified as part of the standard, but from g++9 implementation we could see:

# grep -A 3 hashtable.*aggregation /usr/include/c++/9/bits/hashtable.h
   *  In terms of Standard containers the hashtable is like the aggregation of:
   *
   *  - std::forward_list<_Node> containing the elements
   *  - std::vector<std::forward_list<_Node>::iterator> representing the buckets

It is just a vector of forward_list, not as "smart" as Java HashMap

Bathsheba
  • 231,907
  • 34
  • 361
  • 483
Baiyan Huang
  • 6,463
  • 8
  • 45
  • 72
  • 1
    That is just one implementation. This is the point of not defining it in the standard, each implementation is free to use whatever algorithms or optimizations it wants, as long as it meets the requirements. – spectras Dec 11 '20 at 09:49
  • Sorry but on further reflection I think this is a pretty poor answer. There's no detail, and no justification given to why you think it's not as smart as the Java version. – Bathsheba Dec 11 '20 at 10:47