instructions

One night at bed, my girlfriend asked what’s inside a HashTable? What is expansion?

Me: This all don’t know??

Girlfriend: I don’t know.

I: then I say with her a meal, first so in is so explain clearly to her…… , say that finish went to sleep (behind is paid content)……

Well, I woke up, it was all a lie.

This chapter does a simple summary of HashTable, is jdK1.8 version.

Inherit the figure

Is mainly to do some simple source code view.

Throw out problem

  1. What is the internal data structure like?
  2. When was the expansion mechanism expanded and by how much?
  3. Whether the key or value can be null.
  4. Is it thread safe?

HashMap collection description

Create a HashTable collection object

Map<String,Integer> map = new HashTable<>();
Copy the code

attribute

// An Entry array for storing data
private transientEntry<? ,? >[] table;// Entry How many elements are in the array
private transient int count;

// The threshold is used to determine whether to expand the capacity. Threshold = Capacity x load factor
private int threshold; // The default for the first time is 8

Load factor = load factor
private float loadFactor;

// The number of changes
private transient int modCount = 0;
Copy the code

The constructor

InitialCapacity: data capacity loadFactor: loadFactor */
public Hashtable(int initialCapacity, float loadFactor) {
  if (initialCapacity < 0) // Determine whether the initial capacity is less than 0
    throw new IllegalArgumentException("Illegal Capacity: "+
                                       initialCapacity);
  if (loadFactor <= 0 || Float.isNaN(loadFactor))// Check whether the load factor is less than or equal to 0 and whether the passed parameter value is valid
    throw new IllegalArgumentException("Illegal Load: "+loadFactor);
  if (initialCapacity==0) // Whether the data capacity is equal to 0
    initialCapacity = 1; // If yes, the value is 1
  this.loadFactor = loadFactor; // Load factor
  table = newEntry<? ,? >[initialCapacity];// The size of the initial array table
  // threshold = capacity * (load factor = load factor)
  threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}
// Construct a custom array capacity
public Hashtable(int initialCapacity) {
  this(initialCapacity, 0.75 f);
}
// No arguments
public Hashtable(a) {
  this(11.0.75 f); // It calls a parameterized construct
}
// Put the data of another map collection into the Hashtable collection
public Hashtable(Map<? extends K, ? extends V> t) {
  this(Math.max(2*t.size(), 11), 0.75 f);
  putAll(t); // All this method does is iterate over the t set and add data by calling the Hashtable PUT method
}
Copy the code

A brief description of the collection CRUD

increase

public synchronized V put(K key, V value) {
    // Make sure the value is not null
    if (value == null) {  // Value cannot be null. Otherwise, an exception is thrown
        throw new NullPointerException();
    }

    // Assign a value already initialized in the construct to TABEntry<? ,? > tab[] = table;// Computes the hash value
    int hash = key.hashCode();
    // Compute the subscript
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    // Find the list of nodes in the subscript
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    // Iterate over the nodes in the list
    for(; entry ! =null ; entry = entry.next) {
        // Check whether the hash value is the same, and whether the content is equal
        if ((entry.hash == hash) && entry.key.equals(key)) {
             V old = entry.value; // Assign the old value to old
             entry.value = value; // Assign the new value to the old value
             return old; // Return the old value}}// If the list is not duplicated, add it to another location
    addEntry(hash, key, value, index); // We'll talk about this method later
    return null;
}
Copy the code

Question:

Get Hash value: int Hash = key.hashcode ();

  1. The Hash value is obtained by executing the hashCode() method of the corresponding type of key. If it is not implemented, the hashCode() method of the object class is called to obtain the Hash value, but the null pointer exception is reported

Int index = (hash & 0x7fffff) % tab.length;

  1. Hash to get a subscript0x7FFFFFFFRepresents the largest number of type int2147483647, hash value and the result of 0x7fffff to mod the length of the TAB array.

delete

public synchronized V remove(Object key) { Entry<? ,? > tab[] = table;// Get an array of elements
    int hash = key.hashCode(); // Compute the Hash value
    int index = (hash & 0x7FFFFFFF) % tab.length; // Calculate the following table
    @SuppressWarnings("unchecked") // Suppress warning
    // Get the linked list in the subscript
    Entry<K,V> e = (Entry<K,V>)tab[index];
    for(Entry<K,V> prev = null; e ! =null ; prev = e, e = e.next) {
        // If hash is only the same and the content is the same
        if ((e.hash == hash) && e.key.equals(key)) {
            modCount++;// Operand ++
            if(prev ! =null) { // this is true if the list is traversed to the last node
                prev.next = e.next;
            } else { 
                tab[index] = e.next;  // Pass the data of the next node to the array
            }
            count--; // The amount of content --
            V oldValue = e.value; // Assign the next node as return
            e.value = null;  // Assign null to the next node
            return oldValue; // Returns the removed element}}return null; // Return null if no
}
Copy the code

change

The hash value of the key is used to find the corresponding position and overwrite the corresponding value

check

public synchronized V get(Object key) { Entry<? ,? > tab[] = table;// Get an array of elements
    int hash = key.hashCode(); // Compute the Hash value
    int index = (hash & 0x7FFFFFFF) % tab.length; // Calculate the following table
    // Iterate over the list
    for(Entry<? ,? > e = tab[index] ; e ! =null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) { // The same hash value is valid
            return (V)e.value; // Get the corresponding value of key and return it}}return null;  // Return null if no
}
Copy the code

The core content expansion mechanism of HashTable

Expansion is an operation performed when an element is added to determine whether the size of the array can fit into the next value

----------------- Add method ------------------public synchronized V put(K key, V value) {
    // Make sure the value is not null
    if (value == null) {  // Value cannot be null. Otherwise, an exception is thrown
        throw new NullPointerException();
    }

    // Assign a value already initialized in the construct to TABEntry<? ,? > tab[] = table;// Computes the hash value
    int hash = key.hashCode();
    // Compute the subscript
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    // Find the list of nodes in the subscript
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    // Iterate over the nodes in the list
    for(; entry ! =null ; entry = entry.next) {
        // Check whether the hash value is the same, and whether the content is equal
        if ((entry.hash == hash) && entry.key.equals(key)) {
             V old = entry.value; // Assign the old value to old
             entry.value = value; // Assign the new value to the old value
             return old; // Return the old value}}// If the list is not duplicated, add it to another location
    addEntry(hash, key, value, index); // We'll talk about this method later
    return null;
}

---------------addEntry()-----------------
private void addEntry(int hash, K key, V value, int index) {
  modCount++; // Number of changes ++Entry<? ,? > tab[] = table;// Expand the capacity when the number of elements is greater than or equal to the threshold threshold is 8 by default
  if (count >= threshold) {
    // Rehash the table if the threshold is exceeded
    rehash();  // The main method of expansion
    tab = table;
    hash = key.hashCode();
    index = (hash & 0x7FFFFFFF) % tab.length; // Recalculate index subscripts after expansion
  }
  // Creates the new entry.
  @SuppressWarnings("unchecked")
  // The first time this object is null
  Entry<K,V> e = (Entry<K,V>) tab[index];
  // Create a new node and assign it to TAB.
  tab[index] = new Entry<>(hash, key, value, e); 
  count++; / / + + length
}

---------------rehash()-----------------
protected void rehash(a) {
  int oldCapacity = table.length;  Get the length of the arrayEntry<? ,? >[] oldMap = table;// Get data
  // overflow-conscious code
  int newCapacity = (oldCapacity << 1) + 1;  // Expand to 2 times +1
  // Check whether the new capacity exceeds the default maximum value
  if (newCapacity - MAX_ARRAY_SIZE > 0) {
    if (oldCapacity == MAX_ARRAY_SIZE)
      // Keep running with MAX_ARRAY_SIZE buckets
      return;
    // If it exceeds, assign the maximum value to the new capacity
    newCapacity = MAX_ARRAY_SIZE;
  }
  // newCapacity creates an array of the latest capacity size after obtaining the newCapacity sizeEntry<? ,? >[] newMap =newEntry<? ,? >[newCapacity]; modCount++;// Number of changes ++
  // Calculate a new threshold and expand the capacity if it exceeds the threshold
  threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
  table = newMap; // Reassign the array
  // Data migration iterates through the data, putting the data from the original array into the new array
  for (int i = oldCapacity ; i-- > 0 ;) {
    for(Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old ! =null;) { Entry<K,V> e = old; old = old.next;int index = (e.hash & 0x7FFFFFFF) % newCapacity; e.next = (Entry<K,V>)newMap[index]; newMap[index] = e; }}}Copy the code

Summary: Expansion conditions Count >= threshold and the number of arrays is greater than or equal to threshold perform expansion operations. Expansion operations change the array capacity and the threshold size.

To solve the problem

To solve the problem

  1. What is the internal data structure like?
    1. Array + linked list
  2. When was the expansion mechanism expanded and by how much?
    1. Judge each time an element is addedcount >= thresholdExpansion is 2 times plus 1
  3. Whether the key or value can be null.
    1. Cannot be null
        // key
    int hash = key.hashCode(); // null.hashcode () throws a null-pointer exception
    // value
    if (value == null) { // Value cannot be null. Otherwise, an exception is thrown
    throw new NullPointerException(); 
    }
Copy the code
  4. Is it thread safe?
    1. It’s thread safe because all the methods are usedsynchronizedmodified

Other information

The initial information includes array size 11, threshold(threshold = (capacity size * loadFactor)) 8, loadFactor(loadFactor) 0.75f,

HashTable adds elements using headers, that is, new elements are added to the header of the element.

On the right is the data memory graph after the element with the second value is added

That’s a brief explanation of HashTable.

If you have any questions, discuss them together.

Throw in chicken soup


The process is always pleasing others, and the end result is what you want. The process is always pleasing others, and the end result is what you want.