Shulou(Shulou.com)06/02 Report--

This article mainly explains why the HashMap loading factor is 0.75. Interested friends may wish to have a look at it. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn why the HashMap loading factor is 0.75.

Loading factor is a measure of how full a hash table can be before its capacity increases automatically. it measures the use of space in a hash table. the higher the load factor is, the higher the loading degree of the hash table is, and vice versa.

For hash tables that use linked lists, the average time to find an element is O (1 percent a). Therefore, if the load factor is larger, the space is more fully utilized, but the consequence is the decrease of search efficiency; if the load factor is too small, then the hash table data will be too sparse, resulting in a serious waste of space.

If you look at the source code, you will find that under the initial conditions, HashMap chose 0.75 between time and space.

/ * The load factor used when none specified in constructor. * / static final float DEFAULT_LOAD_FACTOR = 0.75f

But why must it be 0.75? Instead of 0.8 pm 0.6, there is a very important concept: Poisson distribution.

I believe everyone has studied the theory of probability, and the feeling of this famous law should be both familiar and unfamiliar. The focus of this article is not to popularize the knowledge of probability theory for everyone, here is a brief introduction.

Poisson distribution is one of the most important discrete distributions, which often occurs when X represents the number of events in a certain time or space.

To take a simple example, if a boss opens a new hotel, how should you prepare the ingredients for the day?

If you prepare too much, you can only waste and throw away if you can't sell so many vegetables in the end; if you don't have enough preparation, you can't take over the business. But you have a lot of colleagues and friends who will tell you a lot of experience.

For example, divide the day into several time periods, how many guests will come in each time period in the morning, afternoon and evening, and how many dishes will be ordered at each table. Taken together, you can roughly estimate the amount of food that needs to be prepared over the course of the day.

Let's take a look at the original words of the HashMap source code comments:

Ideally, under random hashCodes, the frequency of nodes in bins follows a Poisson distribution with a parameter of about 0.5 on average for the default resizing threshold of 0.75, although with a large variance because of resizing granularity. Ignoring variance, the expected occurrences of list size k are (exp (- 0.5) * pow (0.5, k) / factorial (k)).

0: 0.606530661: 0.303265332: 0.075816333: 0.012636064: 0.00157952

5: 0.0001579

6: 0.00001316

7: 0.00000094

8: 0.00000006

More: less than 1 in ten million

Ideally, using random hash codes, the frequency of node occurrence follows the Poisson distribution in the hash bucket.

Compared with the table of the number and probability of elements in the bucket, we can see that when 0.75 is used as the loading factor, when the number of elements in the bucket reaches 8, the probability has become very small, so it is almost impossible to have more than 8 linked lists at each collision position. so the list node begins to convert to a red-black tree when the linked list node reaches 8.

At this point, I believe you have a deeper understanding of why the HashMap loading factor is 0.75, so you might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.