Preface:

To meet the needs of our readers, Pei has brought you a new issue of dry goods!

BTree, red black tree, hash algorithm analysis, hash table source code analysis

If IT helps you and your friends, pay attention. Thumb up! Thumb up! Comment! Collection! Share it with more friends to learn and communicate, and keep digging gold every day without your support!

Chapter 1 BTree, red black tree

1.1 BTree

  • A binary tree is an ordered tree whose nodes are not more than two.

Simple understanding, is a similar to our life of the tree structure, but each node can only have a maximum of two children.

A binary tree is a tree structure with at most two subtrees per node. The top one is called the root, and the two sides are called the left and right subtrees.

As shown in figure:

1.2 the red-black tree

We’re going to talk about an interesting kind of binary tree called a red-black tree, and a red-black tree is itself a binary lookup tree, and after the node is inserted, the tree is still a binary lookup tree.

As shown in figure:

Red-black tree can ensure the balance of binary tree as much as possible through red nodes and black nodes, so as to improve efficiency.

Constraints on red-black trees:

  1. Nodes can be red or black.
  2. The root node is black.
  3. Leaf nodes (specifically empty nodes) are black.
  4. The children of each red node are black.
  5. The number of black nodes on all paths from any node to each of its leaf nodes is the same.

Red black tree features:

Very fast, approaching the equilibrium tree.

Chapter two hash algorithm analysis, hash table source analysis

2.1 Hash values of objects

The java.lang.object class defines methods: public int hashCode() returns the hash value of an Object, and any class that inherits Object will have this method.

Define the Person class and, without adding any members, call the Person Object’s hashCode() method directly and execute the Object class hashCode() :

public class Person{}
Copy the code

The test class

public static void main(String[] args){
	Person person = new Person();
	int code = person.hashCode();
}
Copy the code

And when you see the result, it’s an integer of type int, and if you convert that integer into hexadecimal you see what’s called the address value of the object, but it’s not the address value, we call it the hash value of the object.

The Person class overrides the hashCode() method: return 0 directly

public int hashCode(a){
	return 0;
}
Copy the code

When run, the method executes the override method of the Person class with a result of 0, which is the hash value of the Person class’s custom Object, without using the parent Object class method hashCode().

2.2 Hash value of String

public static void main(String[] args){
    String s1 = new String("abc");
    String s2 = new String("abc");
    System.out.println(s1.hashCode());
    System.out.println(s2.hashCode());
}
Copy the code

(s1==s2) (s1==s2) (s1==s2) (s1==s2) (s1==s2) (s1==s2)

String class hashCode method source analysis

The underlying implementation of a string is an array of characters, modified by final, which cannot be modified once created.

private final char value[];
Copy the code

Defining a String “ABC” or a new String(” ABC “) is converted to a char value[] array of length 3.

/* * String class override method hashCode() * returns a custom hash value */
public int hashCode(a) {
    int h = hash;
    if (h == 0 && value.length > 0) {
    	char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
    	hash = h;
    }
    return h;
}
Copy the code

String hash algorithm analysis

  • Int h = hash, hash is a member variable, default is 0, int h = 0.
  • H ==0 = true && value.length>0, array value = 3, save three characters ABC, judge the result is true.
  • Char val[] = value, assign value array to val array.
  • Loop for 3 times, iterate through the value array, and fetch ABC.
  • The first cycle: h = 31 * h + val[0], h = 31 * 0 + 97 Result: H = 97.
  • Second cycle: H = 31 * 97 + Val [1], H = 31 * 97 + 98 Result: H = 3105.
  • The third cycle: h = 31 * 3105 + Val [2], H = 31 * 3105 + 99 Result: H = 96354.
  • The return of 96354.
  • Algorithm: 31 * the last hash value + the ASCII code value of the character. 31 is a prime number.

2.3 a hash table

What is a hash table?

Before JDK1.8, hash table is implemented by array + linked list, that is, using array to deal with conflicts, linked lists with the same hash value are stored in an array. However, when there are many elements in a bucket, that is, there are many elements with the same hash value, searching by key value is inefficient. In JDK1.8, hash table storage is realized by array + linked list + red-black tree. When the length of the linked list exceeds the threshold value (8), the linked list is converted to red-black tree, which greatly reduces the search time.

  • Hash table initialization capacity, array length is 16
    • When the size of the array is insufficient, it is twice the size of the original array
  • The loading factor is 0.75
    • Indicates that an array is expanded when its capacity has reached 75% of its length.

In simple terms, hash tables are implemented by an array + a linked list + a red-black tree (red-black tree has been added to JDK1.8), as shown below.

2.4 Process diagram of storing character objects in hash table

To sum up, the introduction of red-black trees in JDK1.8 greatly optimizes the performance of hashMaps, so for us to ensure that the elements of a HashSet are unique is based on the object’s hashCode and equals methods. If we store custom objects in the collection to make them unique, we must override the hashCode and equals methods to set up comparisons that belong to the current object.

2.5 Source code analysis of hash table

A HashMap object is created in the constructor of a HashSet:

map = new HashMap<>();
Copy the code

So source code analysis is analyzing the source code of the HashMap collection, and the Add method in the HashSet collection investigates the PUT method in the HashMap collection.

Analysis of HashMap parameterless constructor

// Static member variables in HashMap
static final float DEFAULT_LOAD_FACTOR = 0.75 f;
public HashMap(a) {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
Copy the code

Create a HashMap object using the no-argument constructor. Set the loadFactor to the default loadFactor, loadFactor= 0.75f.

HashMap has parameter constructor analysis

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);
}
Copy the code

Parse with parameter constructors that pass the initial capacity and load factor of the hash table

  • If initialCapacity is less than 0, an exception is thrown.
  • If initialCapacity is greater than the maximum container, initialCapacity directly equals the maximum container
    • MAXIMUM_CAPACITY = 1 << 30 Yes Maximum capacity (1073741824)
  • If loadFactor is less than or equal to 0, an exception is thrown
  • TableSizeFor (initialCapacity) method calculates the initialCapacity of a hash table.
    • Note: The hash table is the calculated capacity, and the initial capacity is not directly equal to the parameter we passed.

TableSizeFor method analysis

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;
}
Copy the code

The analytic method carries out displacement operation on the initialization capacity we passed, and the displacement result is 8, 4, 2, 1 yards

  • For example, if you pass a 2, you still get a 2, if you pass a 4, you still get a 4.
  • For example, pass 3, the result is 4, pass 5, the result is 8, pass 20, the result is 32.

Node internal class analysis

Hash tables are implemented using arrays + linked lists, and the inner class Node in HashMap is very important

 static class Node<K.V> implements Map.Entry<K.V> {
     final int hash;
     final K key;
     V value;
     Node<K,V> next;
 Node(int hash, K key, V value, Node<K,V> next) {
     this.hash = hash;
     this.key = key;
     this.value = value;
     this.next = next;
}
Copy the code

The parse inner class Node has four member variables

  • Hash, the hash value of an object
  • Key, the object that acts as a key
  • Value, as a value object.
  • Next, next node object

Store element put method source

public V put(K key, V value) {
	return putVal(hash(key), key, value, false.true);
}
Copy the code

Parses the put method to investigate the putVal method, which calls the hash method.

  • Hash (key) method: Passes the element to be stored and obtains the hash value of the object
  • PutVal method that passes an object hash and the key of the object to store

PutVal method source

Node<K,V>[] tab; Node<K,V> p; int n, i;
	if ((tab = table) == null || (n = tab.length) == 0)
		n = (tab = resize()).length;
Copy the code

If the array is null or has a length equal to 0, the resize() method will be used to expand the array.

Resize method for capacity expansion calculation

 if (oldCap > 0) {
     if (oldCap >= MAXIMUM_CAPACITY) {
         threshold = Integer.MAX_VALUE;
         return oldTab;
     }
     else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
              oldCap >= DEFAULT_INITIAL_CAPACITY)
         newThr = oldThr << 1; // double threshold
}
Copy the code

The new array size is equal to the original array size <<1, which is multiplied by 2.

Determines the index of the element store

if ((p = tab[i = (n - 1) & hash]) == null)
	 tab[i] = newNode(hash, key, value, null);
Copy the code

If I = (array length -1) &the hash value of the object, an index will be obtained, and then TAB [I] will be created on this index.

It is also possible to store objects with different hash values under the same array index.

An object with a duplicate hash value is encountered

Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key ! = null && key.equals(k)))) e = p;Copy the code

If the hash values of the objects are the same, the equals method returns true, determines that the object is an object, and overwrites it.

 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;
 }
Copy the code

If the hash values of the objects are the same, but the equals method of the objects returns false, the list is iterated, and when there is no next node in the list, the next node storage object is created.

Follow-up serialized articles, please watch:

  • This guide will show you the Stream you will use at 🔥
  • Take you to solve the big factory will use Lambda expressions, functional interface 🔥

Watch more articles, please move to dachang must use technology summary! 🔥

If IT helps you and your friends, pay attention. Thumb up! Thumb up! Comment! Collection! Share it with more friends to learn and exchange, and keep updating every day without your support!

Welcome to pay attention to my B station, the future will publish articles synchronous video ~~~