First introduction to Hashmap

As the main implementation class for the collection Map; Threads are unsafe and efficient; Store null keys and values.

Implementation of HashMap in Jdk7

1, HashMap map = new HashMap()

After instantiation, a one-dimensional array Entry[] table of length 16 is created underneath.

2, the map. The put (key1, value1)

Call the class hashCode() of Key1 to calculate the hash value of Key1 and get the location of the Entry array. * This location is not empty (in case one or more data exists for this location (in the form of a linked list), compare the hash value of key1 with the existing data: If the hash value of key1 is different from that of existing data, key1-value1 is added successfully * Case 2, add successfully * If the hash value of key1 is the same as that of existing data (key2, value2), If equals() returns false, then key1-value1 was added successfully * Case 3, it was added successfully * If equals() returns true, In case 4, value1 replaces value2 * and updates the value of the original key * In case 2 and case 3, key1-Value1 and the original data are stored in a linked list. Capacity expansion is required during the adding process. If the storage space exceeds the threshold, capacity expansion is required. Default capacity expansion: Double the original capacity and copy the original data.Copy the code

Implementation of HashMap after Jdk8

1, HashMap map = new HashMap()

Instead of creating an array of length 16, the bottom layer creates an array of length 16 the first time put() is called.

2, the map. The put (key1, value1)

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; If ((p = TAB [I = (n-1) & hash]) == null)// The data position to be inserted is empty. TAB [I] = newNode(hash, key, value, null); Else {Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key ! = null &&key. equals(k))))//* 4* e = p; else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); Else {for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); If (binCount >= treeify_threshold-1) // -1 for 1st treeifyBin(TAB, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key ! = null &&key. equals(k))))//* 4* break; p = e; } } if (e ! = null) { // existing mapping for key V oldValue = e.value; if (! onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }Copy the code

3, map. EntrySet ()

Returns a Set

public Set<Map.Entry<K,V>> entrySet() {
    Set<Map.Entry<K,V>> es;
    return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}
Copy the code

4, the map. The get (ket)

Return the value of the key.

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
Copy the code

5. Common parameters:

DEFAULT_INITIAL_CAPACITY: the default capacity of the HashMap, 16

DEFAULT_LOAD_FACTOR: The default load factor for HashMap: 0.75

Threshold: indicates the threshold for expansion. = Capacity x padding factor: 16 x 0.75 => 12

TREEIFY_THRESHOLD: if the length of the Bucket list is greater than the default value, the Bucket is converted to a red-black tree :8

MIN_TREEIFY_CAPACITY: specifies the minimum hash table capacity for nodes in the bucket to be treed. The value is 64

4. Basic knowledge involved

1.An operator:

Bitwise operators are used to operate on binary bits. Java provides bitwise operators as follows: All bitwise operators except ~ are binary operators.

Operands can only be integer and character data.

There are six bit operators in C:

< < shift to the left

> > moves to the right

| or by location

& click with

To take the

^ Bitwise xOR

meaning The operator example
Left shift (see below) << 0011 = > 0110
Right shift (see below) >> 0110 = > 0011
Bitwise or (if one of them is 1, the resulting bit is 1) ︳ 0011

— — — — — — — = > 1011

1011
Bitwise and (corresponding to all 1, result 1) & 0011

— — — — — — — = > 0011

1011
Transposition (transposition) ~ 0011 = > 1100
Bitwise xOR (equal to zero, different to one) ^ 0011

— — — — — — — = > 1000

1011

To move left to move right:

Left shift symbol << : move several bits to the left, discard the high bits, add zero to the low bits, for N bits to the left, it is equal to multiply by 2^ N

Sign right shift operation >> : move several bits to the right, discard the low bits, fill the high bits according to the sign bits, for the positive number right shift operation, add 0 to the high bits; When negative numbers move to the right, the high value is added by 1

Unsigned right shift operation >>> : similar to the right shift operation, high fill zero, low discard, positive numbers conform to the rule, negative numbers do not conform to the rule

2,Hash conflict

The result of the hash function for a key is used as the address to store the current key-value pair (this is the way to store the value of a Hashmap), but it is found that the address has already been accessed. This conflict is called a hash conflict.

To put it simply: Two different objects have the same hashCode, a phenomenon called hash collision.

HashMap’s Put method causes hash conflicts before cases 2 and 3 are added. HashMap uses the chained address method (all hash addresses with the same hash address are linked in the same linked list, so the search, insertion and deletion are mainly carried out in the synonym chain. Chained address method is suitable for frequent inserts and deletions) resolve hash conflicts.

5. Interview questions

1. How does HashMap work?

See above

When HashMap is initialized, the default threshold is 12(load factor is 0.75), which causes HashMap to be expanded in advance. Why not expand HashMap when HashMap is full?

The larger the loading factor is, the more elements are filled. The advantage is that the space utilization is higher, but the chance of conflicts is greater. The list length will get longer and longer, and the search efficiency will decrease. Conversely, the smaller the loading factor, the fewer elements are filled, with the benefit of less collision but more wasted space. The data in the table will be too sparse (a lot of space is already expanding before it is used) and the greater the chance of conflicts, the higher the cost of lookups. Therefore, a balance and compromise must be found between “opportunities for conflict” and “space utilization”. This balance and tradeoff is essentially the tradeoff of the famous time-space contradiction in data structures. If the machine has enough memory and you want to speed up the query, you can set the load factor to be smaller. On the contrary, if the machine is short of memory and there is no requirement for query speed, you can set the load factor to be larger. However, we don’t need to set it. The default value is 0.75.

3. What is the Hashish conflict? How to solve it?

4. Concurrent collections

HashMap principle, Hash collision, synchronous collection, concurrent collection

The following are all synchronous collections in the Java.util.concurrent-Java concurrency toolkit

4.1,ConcurrentHashMapSupports fully concurrent retrieval and updates, and hopefully adjustable concurrent hash tables. This class follows the same functional specification as Hashtable and includes a method version corresponding to each method of Hashtable. However, while all operations are thread-safe, retrieval operations do not have to be locked, and there is no support for locking the entire table in a way that prevents all access. This class can programmatically fully interoperate with Hashtable, depending on its thread-safety and not its synchronization details.

4.2,ConcurrentSkipListMapConcurrentSkipListMap is based on an optimistic lock to achieve high concurrency. ConcurrentSkipListMap is based on an optimistic lock to achieve high concurrency. ConcurrentSkipListMap is based on an optimistic lock to achieve high concurrency.

4.3,ConCurrentSkipListSet(added in JavaSE 6) provides functionality similar to That of TreeSet, with the ability to access ordered sets concurrently. Because ConcurrentSkipListSet is based on a skip list, as long as multiple threads are not modifying the same part of the collection at the same time, there is no contention in normal reading and writing of the collection.

4.4,CopyOnWriteArrayListIs a thread-safe variant of ArrayList, where all mutable operations (add, set, and so on) are performed by making a new copy of the underlying array. This is generally expensive, but it can be more efficient than other alternatives when the number of traversal operations greatly exceeds the number of mutable operations. It is also useful when synchronous traversal is not possible or desirable, but conflicts need to be eliminated from concurrent threads. The snapshot-style iterator method uses a reference to array state when creating iterators. This array in the iterator survival period will not change, so there is no possible conflicts, and iterators ensure ConcurrentModificationException. Iterators do not reflect additions, removals, or changes to the list after they are created. Operations to change elements (remove, set, and add) on iterators are not supported. These methods will throw UnsupportedOperationException.

4.5,CopyOnWriteArraySetA thread-safe, unordered collection that can be thought of as a thread-safe HashSet. Interestingly, both CopyOnWriteArraySet and HashSet inherit from a common parent, AbstractSet; However, a HashSet is implemented through a HashMap, whereas a CopyOnWriteArraySet is implemented through a dynamic array (CopyOnWriteArrayList), not a hash.

4.6,ConcurrentLinkedQueueIs an unbounded, thread-safe queue based on linked nodes. This queue sorts elements according to FIFO (first in, first out), and the head of the queue is the oldest element in the queue. The tail of the queue is the element with the shortest time in the queue. The new element is inserted into the tail of the queue, and the queue retrieval operation retrieves the element from the head of the queue. ConcurrentLinkedQueue is an appropriate choice when many threads share access to a common collection, which does not allow null elements.

Note: ArrayList and HashMap are non-concurrent collections and cannot be modified or deleted during iteration

Note: CopyOnWriteArrayList and CopyOnWriteArraySet are best suited for situations where reads often vastly outnumber writes

5, Thread-safe collection and implementation principle?

Thread-safe collection

5.1 Early thread-safe collection

Vector: an ancient implementation class that acts as a Collection->List interface; Thread-safe, inefficient; The bottom layer uses Object[] elementData for storage

HashTable: as Map’s ancient implementation class; Thread-safe, inefficient; Cannot store null keys and values. Key and value are strings.)

5.2 Collections packaging method

When Vector and HashTable were deprecated, they were replaced by ArrayList and HashMap, but they were not thread-safe, so the Collections utility class provided a wrapper to wrap them as thread-safe Collections

List<E> synArrayList = Collections.synchronizedList(new ArrayList<E>()); Set<E> synHashSet = Collections.synchronizedSet(new HashSet<E>()); Map<K,V> synHashMap = Collections.synchronizedMap(new HashMap<K,V>()); .Copy the code

5.3 Collections in the java.util.concurrent package

ConcurrentHashMap and HashTable are thread-safe collections that differ mainly in locking granularity. Lock a HashTable by adding the synchronized keyword to each method, which locks the entire Table. Before JDK1.8, ConcurrentHashMap used Segment locks. Each Segment contains a portion of the entire table. In this way, concurrent operations between different segments are not affected by each other. JDK1.8 improves this by eliminating the Segment field and directly locking the table element, which further reduces the probability of concurrent conflicts

CopyOnWriteArrayList and CopyOnWriteArraySet are arrayLists and ArraySets with write locks that hold the entire object, but read operations can be performed concurrently

ConcurrentSkipListMap, ConcurrentSkipListSet, ConcurrentLinkedQueue, ConcurrentLinkedDeque, etc. As for why there is no ConcurrentArrayList, it is impossible to design a generic thread-safe collection class that can circumvent the concurrency bottlenecks of ArrayLists, except to lock the entire list, which can be done with the wrapper classes in Collections

6. What is the difference between HashMap and hashTable?

HashMap: as the main implementation class of Map; Threads are unsafe and efficient; Store null keys and values

Hashtable: as an ancient implementation class; Thread-safe, inefficient; Cannot store null keys and values

7. What does hashCode do? How do I override the hashCode method?

The existence of hashCode is mainly used for quick lookup, such as Hashtable, HashMap, etc. HashCode is used to determine the storage address of the object in the hash storage structure. If two objects are the same, then the equals(java.lang.object) method applies, then the hashCode of the two objects must be the same; If the equals method of an object is overridden, then the hashCode of the object should be overridden as well, and the resulting hashCode must be the same as that used in the equals method, otherwise it will violate point 2 above. The fact that two objects have the same hashCode does not necessarily mean that they are the same, and does not necessarily apply to equals(java.lang.object), except that they are stored “in the same basket” in a hash storage structure such as Hashtable.

HashCode is used for lookups and equals is used to compare whether two objects are equal. HashCode functions and overloads

8. What is the difference between hashCode and equals?

Interviewers like to ask about equals and hashCode