Handwritten Java HashMap core source code

Last chapter handwritten LinkedList core source code, this chapter we come to handwritten Java HashMap core source code. Let’s take a look at how HashMap works. HashMap literally means hash + map. Map means mapping, and HashMap means mapping using hash. Don’t understand? it doesn’t matter Let’s take a look at how HashMap works.

HashMap usage analysis

HashMap<String,String> map = new HashMap<>(); map.put("name"."tom"); / / 2 take System. Out.println (map) get ("name")); / / output to TomCopy the code

It’s that simple to use.

Analysis of HashMap principle

Class Object has a hashCode() method that returns the hashCode of the Object. It returns the memory address of the Object. We don’t care

The first thing we need to remember is that this function returns a number. The second HashMap uses an array to hold the data inside

1 How does HashMap store name, Tom? Let’s use a picture to illustrate

Note: The size of the array in the figure above is 7, whatever it is, but we have drawn 7 elements here. We use the size of the array as 7 to illustrate the principle of HashMap.

  1. If the size of the array is 7, the index range of the array is [0, 6].
  2. Get the key, which is hashCode for “name”, which is a number, whatever that number is, and take the remainder of 7, the range must be [0, 6], which is exactly the same as the index of the array.
  3. If “name”.hashcode () % 7 is 2, then value (Tom) should be 2
  4. Data [2] = “Tom”, store in array. Isn’t that clever?

2 Now let’s see how to take it? A diagram is also used to illustrate the underlying principle, as follows

According to the figure above,

  1. The first one is also to get the hashCode value of the key which is “name”
  2. Use hashCode to take the remainder of the array size 7, just as we did when we saved it, which must be 2
  3. Fetch value from the second position in the array: String value = data[2]

Note: There are a few caveats

  1. The value returned by the hashCode() method of an object, whenever called, returns the same value
  2. Take the remainder of a number n, range [0, n-1]

Note: There are several problems to be solved

  1. What if the remainder of a hashCode for a different key is mapped to the same location in the array? A: The array contains the data structure of a node, and the node has the next attribute. If the hash conflicts, the single list is stored, and the fetching process is the same, iterating through the list

  2. What if the array is full? A: Like ArrayList, expand and remap

  3. How to use hashCode() to map directly and generate hash conflicts? A: Refer to the implementation of HashMap in the JDK. There is a hash() function that runs the value of hashCode() and then maps it

A HashMap is used to store data in an array. If the location of the map already has a value, it is stored in a linked list in front of the current location. Let’s say we have an array containing QEntry, as shown in the following figure:

594516-20181128085125518-59591486.png

Handwritten HashMap core source code

After analyzing the principles above, let’s give you a hint of how HashMap works with minimal code. We call this class QHashMap, and the elements in the array need to define a class, and we define it inside the QHashMap class. Just call QEntry

The definition of QEntry is as follows:

Public static class QEntry<K, V> {K key; // store key V value; // store value inthash; / / key correspondinghashValue / /hashQEntry<K, V> next; QEntry<K, V> next; QEntry<K, V> next; public QEntry(K key, V value, inthash, QEntry<K, V> next) {
            this.key = key;
            this.value = value;
            this.hash = hash; this.next = next; }}Copy the code

Now that we have the definition of the QEntry class, what attributes do we need in the QHashMap class? The QHashMap class is defined as follows:

Public class QHashMap<K, V> {// Default array size private static final int DEFAULT_INITIAL_CAPACITY = 16; // The default expansion factor, when the number of elements in the data increases,hashCollisions are also common, so you need to start expanding before the array is used up. 0.75 is when the number of elements in the array reaches 75% of its size. Start to expand private static finalfloatDEFAULT_LOAD_FACTOR = 0.75 f; Private QEntry[] table; Private int size; . }Copy the code

All you need is two constants and two variables. Let’s look at the constructors for QHashMap. For simplicity, only one default constructor is implemented

  public QHashMap() {// Create an array, default size 16 table = new QEntry[DEFAULT_INITIAL_CAPACITY]; Size = 0; }Copy the code

Map.put (“name”,” Tom “) put() :

/** * 1 parameter key,value is easy to understand * 2 returns V, we know that HashMap has a feature, * if map.put("name"."tom"); map.put("name"."lilei"); * The following value overwrites the previous value. If this happens, return the old value, which is returned here"tom"*/ public V put(K key, V value) {//1 For simplicity, keys do not support nullif (key == null) {
            throw new RuntimeException("key is null"); } // Instead of using key.hashcode () directly, we perform another operation on key.hashcode ()hash/ / thishashI copied the () method directly from the HashMap source. You don't have to carehash() the algorithm itself // just need to knowhash() Enter a number and return a number. inthash = hash(key.hashCode()); / / use the keyhashInt index = indexFor(int index = indexFor(hash, table.length); QEntry<K, V> e = table[index]; QEntry<K, V> e = table[index];while(e ! = null) {// ComparehashEquals equals equals equals equals equals equals equals equals equals equals equals equals equals equals equalsif (e.hash == hash && (key == e.key || key.equals(e.key))) {
                V oldValue = e.value;
                e.value = value;
                returnoldValue; } e = e.next; QEntry<K, V> next = table[index]; QEntry<K, V> next = table[index]; // Next may or may not be null, Table [index] = new QEntry<>(key, value,hash, next); Table. Length * 0.75 (don't ask why 0.75, experience)if (size++ >= (table.length * DEFAULT_LOAD_FACTOR)) {
            resize();
        }

        return null;
    }
Copy the code

The comments are quite detailed, but there are several functions here, the hash() function, which is copied directly from the HashMap source code, without worrying about the algorithm. IndexFor (), the hash passed in, and the size of the array, to know where we should look for or save these two functions:

/ / forhashStatic int; static int; static inthash(int h) {
        h ^= (h >>> 20) ^ (h >>> 12);
        returnh ^ (h >>> 7) ^ (h >>> 4); } static int indexFor(int h, int length) {//returnH & (length-1); // Select * from table where h = h > 0; // Select * from table where h = h > 0; h : -h; // Prevent negative numbersreturn h % length;
    }
Copy the code

There’s also a capacity expansion function. When the number of elements is greater than table.length * 0.75, resize() will be expanded.

// The number of elements is greater than table.length * 0.75 // The array is doubled in size private voidresizeInt newCapacity = table.length * 2; int newCapacity = table.length * 2; QEntry[] newTable = new QEntry[newCapacity]; QEntry[] src = table; // Iterate over the old array and remap to the new arrayfor(int j = 0; j < src.length; QEntry<K, V> e = SRC [j]; SRC [j] = null; // Since e is a linked list, it is possible to have multiple nodeswhile(e ! QEntry<K, V> next = e.next; Int I = indexFor(e.hash, newCapacity); E.next = newTable[I]; e.next = newTable[I]; e.next = newTable[I]; NewTable [I] = e; newTable[I] = e; // Continue with the same processing for the next node e = next; } // All nodes are mapped to the new array, don't forget to assign the new array to table = newTable; }Copy the code

Get () is much simpler than put(). You just hash out the location of the array and iterate through the list to find an element that has the same key as the passed key. The put() method looks like this:

Public V get(K key) {// Also for simplicity, keys do not support NULLif (key == null) {
            throw new RuntimeException("key is null"); } // select keyhashValue of the inthash = hash(key.hashCode()); / / usehashInt index = indexFor(int index = indexFor(hash, table.length); QEntry<K, V> e = table[index]; QEntry<K, V> e = table[index];while(e ! = null) {// comparehashAre the values equalif (hash == e.hash && (key == e.key || key.equals(e.key))) {
                returne.value; } // If not, proceed to the next e = e.next; }return null;
    }
Copy the code

Above is the core source of QHashMap, we did not implement deletion. Here is the source code for the entire QHashMap class

QHashMap complete source code is as follows:

Public class QHashMap<K, V> {// Default array size private static final int DEFAULT_INITIAL_CAPACITY = 16; // The default capacity expansion factor starts capacity expansion when the array size is greater than or equal to the current capacity * 0.75floatDEFAULT_LOAD_FACTOR = 0.75 f; Private QEntry[] table; Private int size; Public static class QEntry<K, V> {K key; V value; inthash;
        QEntry<K, V> next;

        public QEntry(K key, V value, int hash, QEntry<K, V> next) {
            this.key = key;
            this.value = value;
            this.hash = hash;
            this.next = next;
        }
    }

    public QHashMap() { table = new QEntry[DEFAULT_INITIAL_CAPACITY]; size = 0; } public V get(K key) {// Also for simplicity, keys do not support NULLif (key == null) {
            throw new RuntimeException("key is null"); } // select keyhashValue of the inthash = hash(key.hashCode()); / / usehashInt index = indexFor(int index = indexFor(hash, table.length); QEntry<K, V> e = table[index]; QEntry<K, V> e = table[index];while(e ! = null) {// comparehashAre the values equalif (hash == e.hash && (key == e.key || key.equals(e.key))) {
                returne.value; } // If not, proceed to the next e = e.next; }returnnull; } /** * 1 parameter key,value is easy to understand * 2 returns V, we know that HashMap has a feature, * if map.put("name"."tom"); map.put("name"."lilei"); * The following value overwrites the previous value. If this happens, return the old value, which is returned here"tom"*/ public V put(K key, V value) {//1 For simplicity, keys do not support nullif (key == null) {
            throw new RuntimeException("key is null"); } // Instead of using key.hashcode () directly, we perform another operation on key.hashcode ()hash/ / thishashI copied the () method directly from the HashMap source. You don't have to carehash() the algorithm itself // just need to knowhash() Enter a number and return a number. inthash = hash(key.hashCode()); / / use the keyhashInt index = indexFor(int index = indexFor(hash, table.length); QEntry<K, V> e = table[index]; QEntry<K, V> e = table[index];while(e ! = null) {// ComparehashEquals equals equals equals equals equals equals equals equals equals equals equals equals equals equals equalsif (e.hash == hash && (key == e.key || key.equals(e.key))) {
                V oldValue = e.value;
                e.value = value;
                returnoldValue; } e = e.next; QEntry<K, V> next = table[index]; QEntry<K, V> next = table[index]; // Next may or may not be null, Table [index] = new QEntry<>(key, value,hash, next); Table. Length * 0.75 (don't ask why 0.75, experience)if (size++ >= (table.length * DEFAULT_LOAD_FACTOR)) {
            resize();
        }

        returnnull; } // The number of elements is greater than table.length * 0.75 // The number of elements is twice the original size private voidresizeInt newCapacity = table.length * 2; int newCapacity = table.length * 2; QEntry[] newTable = new QEntry[newCapacity]; QEntry[] src = table; // Iterate over the old array and remap to the new arrayfor(int j = 0; j < src.length; QEntry<K, V> e = SRC [j]; SRC [j] = null; // Since e is a linked list, it is possible to have multiple nodeswhile(e ! QEntry<K, V> next = e.next; Int I = indexFor(e.hash, newCapacity); E.next = newTable[I]; e.next = newTable[I]; e.next = newTable[I]; NewTable [I] = e; newTable[I] = e; // Continue with the same processing for the next node e = next; } // All nodes are mapped to the new array, don't forget to assign the new array to table = newTable; } / / tohashStatic int; static int; static inthash(int h) {
        h ^= (h >>> 20) ^ (h >>> 12);
        returnh ^ (h >>> 7) ^ (h >>> 4); } static int indexFor(int h, int length) {//returnH & (length-1); // Select * from table where h = h > 0; // Select * from table where h = h > 0; h : -h; // Prevent negative numbersreturnh % length; }}Copy the code

That’s how QHashMap works. Let’s write some test code to see if our QHashMap works. The test code is as follows:

 public static void main(String[] args) {
        QHashMap<String, String> map = new QHashMap<>();
        map.put("name"."tom");
        map.put("age"."23");
        map.put("address"."beijing");
        String oldValue = map.put("address"."shanghai"); System.out.println(map.get());"name"));
        System.out.println(map.get("age"));

        System.out.println("Old value =" + oldValue);
        System.out.println("New value =" + map.get("address"));
    }
Copy the code

The output is as follows:

Tom 23 Old = Beijing New = ShanghaiCopy the code

Through the above simple implementation of QHashMap, there are a lot of functions are not implemented, compare remove,clear,containsKey(), and traversal related, interested readers can implement their own