I. Overview of HashMap HashMap can be said to be one of the most commonly used collection class frameworks in Java, and it is also a very typical data structure in Java language.

HashMap is implemented based on the Map interface of hash table, which provides all optional mapping operations.

Gansu computer training/discovery storage pair mapping, allowing multiple null values and a null key.

However, this class does not guarantee the order of mapping, especially the order is unchanged.

The HashMap class is roughly the same as Hashtable, except that HashMap is asynchronous and allows null.

This implementation assumes that the hash function properly distributes elements in the bucket, which can provide stable performance for basic operations (get and put).

The time required to iterate the collection view is directly proportional to the "capacity" (the number of buckets) and the size (the number of key-value mapping relationships) of the HashMap instance.

Therefore, if iterative performance is important, don't set the initial capacity too high (or set the loading factor too low).

An example of HashMap has two parameters that affect its performance: initial capacity and load factor.

Capacity is the number of buckets in the hash table, and the initial capacity is only the capacity when the hash table is created.

The load factor is an index to measure how full the hash table can be before the capacity is automatically increased.

When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table will be hashed again (that is, the internal data structure will be rebuilt), so that the hash table will have about twice the number of buckets.

Generally, the default loading factor (0.75) seeks a compromise between time and space costs.

Although the high load factor reduces the space overhead, it also increases the query overhead (which is reflected in most HashMap class operations, including get and put operations).

When setting the initial capacity, the number of entries required in the mapping and their loading factors should be considered in order to minimize the number of rehash operations.

If the initial capacity is greater than the maximum number of entries divided by the load factor, the rehash operation will not occur.

Note that this implementation is not synchronous.

If multiple threads access a HashMap instance at the same time, and at least one of them has modified the list structurally, then it must keep external synchronization.

This is usually achieved by synchronizing the objects used to encapsulate the list.

However, if there is no such object, you should use {@ linkcollections # SynchronizedMapCollections. SynchronizedMap} is "wrapped", which is best done at the time of creation to avoid unexpected asynchronous operations on the map.

mapm = collections . synchronized map(new hashmap(...)); Second, the constructor HashMap provides three constructors: HashMap (): an empty HashMap is constructed, with default initial capacity (16) and default loading factor (0.75).

HashMap(intinitialCapacity): Construct an empty HashMap with the specified initial capacity and the default loading factor (0.75).

HashMap(intinalpacity, float load factor): Construct an empty HashMap with the specified initial capacity and load factor.

Two parameters are mentioned here: initial capacity and loading factor.

These two parameters are important parameters that affect the performance of HashMap, in which the capacity represents the number of buckets in the hash table, the initial capacity is the capacity when the hash table is created, and the load factor is an index to measure how full the hash table can be before the capacity is automatically increased, which measures the space usage of the hash table. The larger the loading factor, the higher the filling degree of the hash table, and vice versa.

For the hash table using the linked list method, the average time to find an element is O( 1+a), so if the loading factor is large, the space will be fully utilized, but the search efficiency will decrease. If the load factor is too small, the data of hash table will be too sparse, which will cause serious space waste.

The default load factor of the system is 0.75. Generally, we don't need to modify it.

HashMap is a data structure that supports fast access. To understand its performance, we must understand its data structure.