Detailed introduction to Java collection class Hashmap (code example)

This article brings you a detailed introduction (code example) about the Java collection class Hashmap. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you. helped.

1. Introduction to HashMap

HashMap is a very commonly used collection class in the development process of programmers. It is a collection class that exists in the form of key-value pairs,

In development, we can take advantage of its feature of replacing a key when it exists to implement an updated deduplication operation.

In another convenience, we can use map and fastJson to quickly form the json data format we need.

Before jdk1.8, HashMap existed in the form of an array linked list. The hashCode of the put key was calculated by the perturbation function to obtain the hash value, and then the value was calculated by (n-1)&hash. Go to the corresponding position (n represents the length of the array),

If a hash conflict occurs, first determine whether the key exists, and if it exists, overwrite it, otherwise use the "zipper method" to resolve the conflict, and then form linked list.

But after jdk1.8, HashMap has changed. If the length of the current linked list is greater than the threshold (the default is 8), then the linked list will be converted into a red-black tree, speeding up the search.

2. HashMap attribute

//The default initial capacity of HashMap is 2^4=16
static final int DEFAULT_INITIAL_CAPACITY = 1

//The maximum capacity of HashMap
static final int MAXIMUM_CAPACITY = 1

// The default load factor is when the array length is
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// When the number of nodes on the bucket is greater than this value, it will be converted into a red-black tree
static final int TREEIFY_THRESHOLD = 8;

// When the number of nodes on the bucket is less than this value, the tree will be converted to a linked list
static final int UNTREEIFY_THRESHOLD = 6;

// Structure in the bucket Convert to the minimum size of the table corresponding to the red-black tree
static final int MIN_TREEIFY_CAPACITY = 64;

// An array to store elements, always a power of 2
transient Node

//Set that stores specific elements
transient Set> entrySet;

//Stores the number of elements, Note that this is not equal to the length of the array.
transient int size;

// Counter for each expansion and change of map structure
transient int modCount;

//The critical value is the actual size (capacity * fill factor) When the critical value is exceeded, expansion will be performed (*When size is greater than or equal to threshold, the expansion mechanism will not necessarily be triggered, but it will most likely be triggered. As long as there is a If a hash conflict occurs in the newly created Entry, immediately resize)
int threshold;

// fill factor When Size>=threshold, then It is necessary to consider the expansion of the array, that is to say, this means a standard to measure whether the array needs to be expanded
final float loadFactor;

3. HashMap expansion mechanism

 public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

The code for tableSizeFor is:

static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

>>> is a bit-right shift symbol that ignores the sign bit |= is the & operation between the left and right numbers

This method will Turn the initialization capacity you passed in into a number that is the power of the square of 2, so it is fixed here that the capacity of the HashMap must be the power of the square of 2

As for why it is a number that is the power of the square of 2 The reasons are as follows:

1.put method source code:

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)
            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))))
                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))))
                        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;
    }

See the sentence p = tab[i = (n - 1) & hash]) == null (n - 1) & hash is calculated to a position. If the position in the tab is empty, the insertion operation is performed directly.

As an example, suppose there are 16 positions and 4 students have their own student numbers

##李四2王五3老李4

 

 

 

 

此时我们分配位置的时候可以采用  1%16 = 1；2%16=2；3%16 = 3；4%16=4；给他们分配位置,但是考虑到性能问题。由于%操作比&慢10倍左右，因此采用&运算会提高性能。

通过限制length是一个2的幂数， (n - 1) & hash和hash%n结果是一致的。这就是为什么要限制容量必须是一个2的幂的原因。

比如2的hashCode是2   那么它对应的二进制是 （0000 0010）

假设n=16

那么n-1=15对应的二进制是  1111 1111 & 0000 0010 = 1111 1111 = 0010 = 2

2%16=2

得到(n - 1) & hash和hash%n结果是一致的,考虑到性能所以每次的扩容都是以2的幂次方扩容。

四.HashMap的简单应用

public  static void mapMethod() {
		HashMap<String, Object> map = new HashMap<>();
		map.put("zhangsan", 11);
		map.put("lisi", 11);
		//重复key会覆盖
		map.put("zhangsan", 22);
		//便利
		for(String key:map.keySet()) {
			//根据key获取value
			System.out.println(key+"=======value:"+map.get(key));
		}
		//containsKey方法判断当前map是否包含该方法
		System.out.println(map.containsKey("zhangsan"));
		//size打印map的长度
		System.out.println(map.size());
		//移除key
		map.remove("zhangsan");
		//判断是否存在value
		System.out.println(map.containsValue("22"));
	}

Name	Student ID
张三	1

The above is the detailed content of Detailed introduction to Java collection class Hashmap (code example). For more information, please follow other related articles on the PHP Chinese website!