编程知识 cdmana.com

Two high frequency design interview questions: how to design HashMap and thread pool

I've been collecting interview questions recently , But the version I wrote is not a recitation version , It's not a rote answer .

My original intention is to throw a brick to attract jade , Give my own understanding and explanatory answers to each question , Then reciting the version requires you to summarize and memorize by yourself .

Because eight part essay is a must in an interview , That is to say, we still need to know what we should know , And on the basis of understanding, memory will be more profound , And can deal with some variant problems .

But it's not clear if this form is popular , So for the time being, I'll take two topics and send them out first to see the repercussions .

So if you think this kind of form is not good , If it needs to be improved , Please leave a message .

1. If you were to design a HashMap How to design ?

I think this problem can be solved from HashMap Some of the key points to start with , for example hash function 、 How to deal with conflicts 、 How to expand .

Let's say you're right HashMap The understanding of the .

such as :HashMap It's just a storage <key,value> Set of formats , Made by key stay O(1) You can find it in a complicated time value.

The basic principle is to key after hash Hash function to get the hash value , Then the hash value is used to modulate the array to get the corresponding index .

therefore hash Functions are key , It's not just fast , It also needs to be evenly distributed , Reduce hash Collision .

And because the input value is infinite , And the size of the array is limited, so there must be collisions , So we can use zipper method to deal with conflicts .

To avoid malicious hash attack , When the zipper exceeds a certain length, it can turn into a red black tree structure .

Of course, more than a certain number of nodes still need to be expanded , Otherwise, the collision would be too serious .

The common expansion will lead to a certain failure put The delay is large , especially HashMap When there is a lot of data stored , So we can consider and redis Two like that table Delay movement , You can move only part of it at a time .

But this memory is tight , So it's also the scene trade off 了 .

also , It's best to estimate the data size before using it , Avoid frequent expansion .

Basically, this is the answer ,HashMap There are several key elements , Next, it depends on how the interviewer asks .

It may extend to issues like thread safety , Anyway, just follow currentHashMap My design answers .

In fact, some questions seem to ask how to design , In fact, you just answer how you understand this thing , Let's talk about its principle and some key points. This topic is over .

For example, the size of the estimated data I mentioned above , It doesn't seem to have anything to do with design , But it's enough to let the interviewer know that you are sensitive to this aspect .

So sometimes “ give an irrelevant answer ” yes OK Of , If the interviewer thinks you're going in the wrong direction , Naturally, it will remind you , You'll take the call then .

In short , A lot of questions don't really need to be answered rigidly to the interview questions , Because the interviewer just asked in general .

2. If you want to design a thread pool, how to design it ?

This kind of design problem is still the same , Let's talk about understanding first , Show that you know the use and principle of this thing , And then start BB. Basically, according to the existing design , Add some personal insights .

The thread pool is a container for storing threads , Save the previously established thread in the pool to repeat the task , Reduce the overhead of creating and destroying threads , Improve the response speed of the task , And convenient for thread management .

I personally think that if we want to design a thread pool, we have to consider the management of working threads in the pool 、 Task choreography execution 、 Thread pool overload solution 、 Monitoring, etc .

To initialize the number of threads 、 Number of core threads 、 Maximum thread pools are exposed and configurable , Including the configuration of thread idle death exceeding the number of core threads .

Then the storage structure of the task has to be configurable , It can be unbounded or bounded , Or according to the configuration , Multiple queues are used to assign tasks with different priorities , You can also use stealing To improve the utilization of threads .

Then provide configuration to indicate that the thread pool is IO Intensive or CPU Intensive to change the execution strategy of the task .

There are many options for overload , Including dropping tasks 、 Reject the task and throw an exception 、 Discard the oldest tasks or customizations, etc .

As for monitoring , The design of thread pool should be better , Expose the interface for monitoring , Such as the number of tasks processed 、 Number of tasks to be processed 、 Number of running threads 、 The number of rejected tasks and so on .

I think that's basically the answer , Just wait for the interviewer to ask .

Note that you don't need to explain to the interviewer what the number of core threads is , You know, it's not necessary .

Of course, different people have different opinions on this kind of open-ended problem , This is not the standard answer , For reference only .

All the related keywords of the thread pool should be mentioned , On the surface, your understanding of the internal principles of thread pooling is thorough .

This article is from WeChat official account. - High performance server development (easyserverdev)

The source and reprint of the original text are detailed in the text , If there is any infringement , Please contact the yunjia_community@tencent.com Delete .

Original publication time : 2021-04-02

Participation of this paper Tencent cloud media sharing plan , You are welcome to join us , share .

版权声明
本文为[Fan Li]所创,转载请带上原文链接,感谢
https://cdmana.com/2021/04/20210408111750813v.html

Scroll to Top