About how HashMap works, in principle, everything is clear. What is the bundle, the complexity of the search and so on. All this is in Google.

The question is how, according to the hash already received, is the desired element in the array.

As I understand it, the only way to get the access time is O (1) is an array, addressing by index. So, having a hash of an object, you need to somehow bring it to this index in order to get the same O (1) according to the hash.

A simple variant comes to mind that HashMap simply reserves an array of maximum size where elements are stored under indices equal to the object’s hash itself, but this requires a lot of memory and this option seems unrealistic

  • 2
    Not this by accident? habr.com/ru/post/421179 - andreymal pm
  • @andreymal, yes. Thank. I do not use Google so well) Now I don’t even know what to do with the question - Serhii Dikobrazko pm
  • Well, since Stack Overflow strives to be a self-sufficient knowledge base and the answers-links here are not really approved, maybe someone else will write a full answer here) - andreymal

1 answer 1

There are a couple of important points:

  • every bundle is a collection;
  • The number of these bundles is always a 2-degree.

When an item is placed in a HashMap, an additional operation is performed to calculate the remainder of dividing the hash by the number of bundles . This result will be the index of the bundle in which the item falls. Also, he will never be more than the number of bundles (the remainder of the division because! )

And given that the number of bundles is always a degree of 2-ki, for optimization, the division operation is replaced by the logical AND operation (hash) and (the number of bundles is 1)