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

This article mainly introduces "the usage of HashMap in java". In daily operation, I believe many people have doubts about the usage of HashMap in java. Xiaobian consulted all kinds of information and sorted out simple and easy to use operation methods. I hope to help you answer the doubts about "the usage of HashMap in java"! Next, please follow the small series to learn together!

HashMap data structure and how to store data?

Several important parameters of HashMap:

transient int size: Indicates the number of key-value pairs contained in the current HashMap

transient int modCount: Indicates the number of times the current HashMap has been modified

int threshold: indicates the maximum number of key-value pairs that the current HashMap can support. Once this number is exceeded, HashMap will expand.

final float loadFactor: Load factor, used for capacity expansion

static final int DEFAULT_INITIAL_CAPACITY = 1 >> 16) is the second high-order participation operation //When the length of the array table is relatively small, it can also be guaranteed that both high and low bits are involved in the calculation of the Hash, and there will not be too much overhead. return (key == null) ? 0 : (h = key.hashCode()) ^ (h >> 16);} Method 2: static int indexFor(int h, int length) { //jdk1.7 source code, jdk1.8 does not have this method, but the implementation principle is the same return h & (length-1); //The third step modulo faster}

The Hash algorithm here is essentially three steps: taking the hashCode value of the key, high-order operation, and modulo operation.

Hashmaps are most efficient when their initial array size is all powers of two.

Look at the image below. The two groups on the left are arrays of length 16 (2 to the fourth power), and the two groups on the right are arrays of length 15. The hashcodes of both groups are 8 and 9, but obviously, when they are "AND" with 1110, they produce the same result, that is, they will be located in the same position in the array, which produces a collision, 8 and 9 will be placed on the same linked list, then the query needs to traverse the linked list to get 8 or 9, which reduces the efficiency of the query. At the same time, we can also find that when the array length is 15, the value of hashcode will be "AND" with 14 (1110), so the last bit will always be 0, and 0001, 0011, 0101, 1001, 1011, 0111, 1101 will never be able to store elements. The waste of space is quite large. Worse, in this case, the array can be used in positions much smaller than the array length. This means further increasing the probability of collisions and slowing down query efficiency!

Therefore, when the array length is the nth power of 2, the probability that different keys are the same index is small, so the data is distributed evenly on the array, that is to say, the probability of collision is small, and the query does not have to traverse the linked list at a certain position, so the query efficiency is also high.

The default array size in hashmap is 16

Because 16 is an integer power of 2, 16 can reduce collisions between keys better than 15 and 20 in the case of small data volume, and speed up query efficiency.

Therefore, when storing large-capacity data, it is best to specify in advance that the size of the hashmap is an integer power of 2. Even if not specified, it will be initialized to the power of 2 that is greater than and closest to the specified value. The code is as follows (in the construction method of HashMap):

// Find a power of 2 >= initialCapacity int capacity = 1; while (capacity < initialCapacity) capacity

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.