Before you figure out the HashMap, answer the following questions

1. Is HashMap thread safe?

2. What is the HashMap data structure?

  • Arrays, linked lists, red-black trees

3. Which blocks of HashMap are optimized for JDK8, and why?

Step by step, get to know HashMap

1, the array

Public class Array {/** * delete insert low O(n) * find subscript search O(1) * java.util.ArrayList * @param args */ public static void main(String[] args) { Integer[] integers = new Integer[10]; integers[0] = 0; integers[1] = 1; integers[2] = 2; integers[3] = 3; integers[4] = 4; }}Copy the code

Array: A contiguous array of storage cells to store data. For the search of the specified subscript, the time complexity is O(1); For ordinary insert and delete operations, which involve moving array elements, the average complexity is O(n).

2. Linear lists

public class Node { public Node next; private Object data; public Node(Object data){ this.data = data; } public static void main(String[] args) {public static void main(String[] args) {public static void main(String[] args) { Node node = new Node(1); node.next = new Node(2); node.next.next = new Node(3); }}Copy the code

Linear linked list: For operations such as addition and deletion of linked list (after finding the specified operation location), only references between nodes need to be processed, and the time complexity is O(1), while search operations need to traverse the linked list for comparison, and the complexity is O(n).

Hash hash

A hash algorithm (also called a hash) is a data structure that hashes a value of any length (key) into a fixed-length key address.

It accesses records by mapping key values to a location in the table to speed up lookups.

The mapping function is also called a hash function, and the array of records is called a hash table.

4. Understand the nature of HashMap technology

public class App {

    public static void main(String[] args) {
        //Map<String,String> map = new HashMap();
        App map = new App();
        map.put("That"."That");
        map.put("Chen 2"."Chen 2");
        map.put("Zhang"."Zhang");
        map.put("Bill"."Bill");
        map.put("Fifty"."1");
        map.put("The wu is empty"."The wu is empty"); } / * * *hash* @param key * @param value */ public void put(String key, String value){//"Key :%s,hash value :%s, store location :%s\r\n",key,key.hashCode(),Math.abs(key.hashCode() % 6));
    }
Copy the code

Output result:

Key: that,hashValue :671464, Storage location :4 Key: Chen Er,hashValue :1212740, Storage location :5 Key: Zhang SAN,hashValue :774889, Storage location :4 Key: Li Si,hashValue :842061, Storage location :6 key: Wang Wu,hashValue :937065, storage location :0 Key: Wukong,hashValue :798139, storage location :4Copy the code

Analyzing the essence of HashMap technology:

5, handwritten implementation

Define the interface:

@param <K> @param <V> */ public interface Map<K,V> {public V put(K K,V V); public V get(K k); public int size(); public interface Entry<K,V>{ public K getKey(); public V getValue(); }}Copy the code

Interface implementation:

/** * <p> ** implement HashMap * </p> ** @author: [email protected] * @create: Public class HashMap<K, V> implements Map<K, V> {private Entry<K, V>[] tables = null; private static int defaultLengh = 16; private int size = 0; publicHashMap() {
        this.tables = new Entry[defaultLengh];
    }

    public V put(K k, V v) {

        // hashOut of thehashThe value of the int index =hash(k); // Array length index index position Entry = tables[index];if (entry == null) {
            tables[index] = new Entry<>(k, v, null, index);
            size++;
        } else{ tables[index] = new Entry<>(k, v, entry, index); } // Find the corresponding Entry of our table by positionreturn tables[index].getValue();
    }

    public V get(K k) {
        if (size == 0)
            return null;
        // hashInt index =hash(k);

        Entry<K, V> entry = getEntry(k, index);
        return entry == null ? null : entry.getValue();

    }


    public int size() {
        return size;
    }

    class Entry<K, V> implements Map.Entry<K, V> {
        private K k;
        private V v;
        private Entry next;
        private int hash;

        public Entry(K k, V v, Entry next, int hash) {
            this.k = k;
            this.v = v;
            this.next = next;
            this.hash = hash;
        }

        public K getKey() {
            return k;
        }

        public V getValue() {
            return v;
        }
    }

    private int hash(K k) {
        int index = k.hashCode() & (defaultLengh - 1);
        return Math.abs(index);
    }

    private Entry<K, V> getEntry(K k, int index) {
        for(Entry e = tables[index]; e ! = null; e = e.next) {if (e.hash == index && (e.getKey() == k || e.getKey().equals(k))) {
                returne; }}returnnull; }}Copy the code

Test verification:

public static void main(String[] args) {
    //Map<String,String> map = new HashMap();
    //App map = new App();
    com.nuih.map.Map map = new com.nuih.map.HashMap();
    map.put("That"."That");
    map.put("Chen 2"."Chen 2");
    map.put("Zhang"."Zhang");
    map.put("Bill"."Bill");
    map.put("Fifty"."1");
    map.put("The wu is empty"."The wu is empty");
    System.out.println(map.get("The wu is empty"));
}
Copy the code

6. Which section of HashMap is optimized for JDK8, and why?

  • JDK8 introduces red black tree to solve the problem of list lookup speed, but also introduces a problem: insert slow, it has a default threshold of 8 will be converted to red black tree, source: