unordered map data structure

Question

Hi

As map has underlying data structure as RB tree and it's search is hence O(log N).

What is data structure for unordered map? It's search is O(1) due to hash function, but where does it stores data? Tree has node and I can understand for map, but where actually data is stored in unordered map?

Answer 1

Hash map is a data structure in which value of key is hashed you can read more about hashing from google now this hashed value is unique(not always) for different keys now we use hashed value and store data at that index now if some value have same hash values then they both are inserted in same index so by this worst complexity of search is O(n) but average is O(1)

Answer 2

Unordered map is dictionary like data structure. It is a sequence of (key, value) pair, where only single value is associated with each unique key.internally unordered_map is implemented using Hash Table, the key provided to map are hashed into indices of hash table that is why performance of data structure depends on hash function a lot but on an average the cost of search, insert and delete from hash table is O(1)
Hope it helps!!

Answer 3

We define some size for table then after calculating hash we take modulo with tha value and store that at tha index now if two or more value have same hash they all are inserted there like linked list that's why it has worst time complexity of O(n) cause it may be happen that all value have same hash

Answer 4

We fix the size of initial array and if any hash value exceeds that size we just take modulo by the size to put that in range so no need for reallocation cause it always fit in size.
I don't know how much size is used to declare these
But it's space complexity is O(n)

Answer 5

Thanks ChillPill [Nezuko] .. it cleared many things.... Best case is O(1) but drawback is vector data assigned and allocated memory as soon as constructor is called. So , just for two data in current case, 13 data space is reserved.

Could you please throw so light on what happens when 14 element is added ? I just changed capacity to 2 instead of 13, added new insert in between hello and world and code does not work.... I know you have not coded this scenario , but what should be idea way to handle this situation? Or this should never happen ?

Answer 6

Thank you Srishti nd YUGRAJ

I have a question... Does same value of index for more data would not result into loss of earlier data ? Or it maintains all records ?

And another question is on hash table. What is it ? We are taking about indexes also so does it nothing but a vector ? If so, what is size of this table in terms of memory ? Does it expands like vector or other data structures ?

Answer 7

So does it mean hash table is like vector of linked list such a deque ?

Here, each linked list is defined or considered as hash index.

How many such indexes are allocated at start and what happens to reallocation case ? It is avg time complexity of insertion and find as O(1) but what about space complexity?

Sorry I am asking too much question but still hash is not clear and wanna understand it better. Thank you for your time and effort.