What is the difference between 1.7 and 1.8?

Difference:

(1) JDK1.7 uses head insertions, while JDK1.8 and later use tail insertions, so why do they do this? Because JDK1.7 is vertical extension with a single list, it is easy to have the problem of reverse order and circular list dead loop when using the head interpolation method. However, after JDK1.8, red-black trees were added to use tail interpolation method, which can avoid the problem of reverse order and linked list endless loop.

(2) After expansion, the calculation method of data storage location is also different:

1. In JDK1.7, the hash value is used directly with the binary number to be expanded (this is why the expansion must be a power of 2, because the last binary digit must be 1 if there is only a power of 2 to the n). This minimizes hash collisions (hash & Length-1).

2. In JDK1.8, we directly use the calculation rule of JDK1.7, that is, the original location before expansion + expansion size =JDK1.8, instead of the xOR method of JDK1.7. However, this method is equivalent to quickly calculating the storage mode after expansion just by determining whether the newly added Hash bit is 0 or 1.

To compute the hash value, JDK1.7 uses 9 perturbations =4 bits +5 xor, whereas JDK1.8 uses only 2 perturbations =1 bit +1 Xor.

Capacity expansion process comparison diagram:

(3) JDK1.7 uses array + single linked list data structure. However, in JDK1.8 and later, the array + list + red-black tree data structure is used (when the list depth reaches 8, which is the default threshold, it will automatically expand the list to red-black tree data structure to change the time complexity from O (n) to O (logN) to improve efficiency).

Here are two additional questions:

(1) In JDK1.7, insert before expansion, and in JDK1.8, insert before expansion.

// If the size of the key pair inserted into the Map is greater than the default threshold (initially 16*0.75=12), expansion will be triggeredif (++size > threshold)
            resize();
Copy the code

When you insert a HashMap, it may be either a normal list node or a red-black tree node. If you insert a HashMap, it may be a red-black tree node. Welcome to the discussion?

In JDK1.7, if the bucket you are inserting is empty, you will need to expand the bucket if the bucket is not empty. If the bucket is not empty, you will need to expand the bucket if the bucket is empty. If no Hash conflict occurs in the future, capacity expansion will not be performed, reducing unnecessary capacity expansion and memory usage.

void addEntry(int hash, K key, V value, int bucketIndex) {// If the value of the money group is greater than or equal to 12 (if), and the current array of entries cannot be empty, the current array is expandedif((size >= threshold) && (null ! = table[bucketIndex])) {resize(2 * table.length);hash= (null ! = key) ?hash(key) : 0; bucketIndex = indexFor(hash, table. Length); } createEntry (hash, the key value, bucketIndex); } void createEntry(inthash, K key, V value, int bucketIndex) {Entry<K,V> e = table[bucketIndex]; Table [bucketIndex] = new Entry<>(bucketIndex = new Entry<>(hash, key, value, e); // suppose it is now new size++; }Copy the code

(2) In JDK1.8, when optimizing HashMap, the threshold for converting linked lists to red-black trees is 8 instead of 7 or 20.

If you choose 6 and 8 (if the list is less than or equal to 6, the tree is restored to the list, and if the list is greater than or equal to 8, the tree is restored to the tree), a difference of 7 in the middle can effectively prevent the list and tree from frequent conversion. For example, if the number of linked lists is more than 8, the linked list will be converted into a tree structure; if the number of linked lists is less than 8, the tree structure will be converted into a linked list. If a HashMap keeps inserting and deleting elements, and the number of linked lists is around 8, it will frequently convert tree to linked list and linked list to tree, and the efficiency will be very low.

It is also important to note that since Treenodes are about twice the size of regular nodes, we use them only when the container contains enough nodes to be usable, and when they become too small (due to removal or resizing), they are converted back to regular node nodes. The frequency with which the nodes in the container are distributed in the Hash bucket follows a Poisson distribution, and the probability of the bucket length exceeding 8 is very, very small. Therefore, the author should choose 8 as the threshold based on probability statistics.

* Because TreeNodes are about twice the size of regular nodes, we * use them only when bins contain enough nodes to warrant use * (see TREEIFY_THRESHOLD). And when they become too small (due to * removal or resizing) they are converted back to plain bins. In * usages with well-distributed userhashCodes, tree bins are
     * rarely used.  Ideally, under random hashCodes, the frequency of
     * nodes inbins follows a Poisson distribution * (http://en.wikipedia.org/wiki/Poisson_distribution) with a * parameter of about 0.5 on business,forThe 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)). The first values are: * * 0: 0.60653066 * 1: 0.30326533 * 2: 0.07581633 * 3: 0.01263606 * 4: 0.00157952 * 5: 0.00015795 * 6: 0.00001316 * 7: 0.00000094 * 8: 0.00000006 * More: less than 1in ten million
Copy the code

How does a Hash table resolve Hash conflicts?

3. Why does HashMap have the following characteristics: key-values are allowed to be null, threads are not safe, order is not guaranteed, and storage location changes with time

Why wrapper classes such as String and Integer are suitable for key functions in HashMap

If the key in HashMap is of Object type, what methods should be implemented?

The last

Welcome to pay attention to the public number: programmer chasing wind, reply 66 to receive a 300 page PDF document Java core knowledge summary!