Thought record:

1. The body of a HashMap is an array of entries. If multiple keys have the same hash index, hash conflicts will occur.

2. When deleting, it should be considered that if the target object is in the linked list and there are child nodes, the deletion method of the linked list should be followed to prevent the loss of subsequent objects. Assume father is the first nodule of the target. The father. The next = father. Next, next

3. For the expansion of the old and new arrays and indexes, we need to clarify the ideas, and distinguish value passing from reference passing in the code of PUT, GET and remove, so as to prevent ourselves from thinking that objects are appended to the linked list when they are not.

4. The code has comments at each key point, so you need to have a general understanding of the basic features of HashMap before reading.

Code implementation:

Interface class

For each operation, the hashConfictIndex parameter is appended because hash collisions are hard to find. Passing -1, we call the hash method as normal to scale the array to compute the index. If we want to append an object to index 5 to mimic hash collisions, I need to pass in 5 to simulate. This simulated object also requires us to pass in the same index manually during get and remove, because normal hash computations don’t necessarily get the index we set when inserting based on the given key.

package com.lx.myhashmap; public interface MyHashMapInter { public String get(String key,int hashConfictIndex); public void put(String key,String value,int hashConfictIndex); public void remove(String key,int hashConfictIndex); interface MyEntryInter{ public String get(); public void set(); }}Copy the code
The implementation class

There are comments and console output at each key point. If you can’t see clearly, copy the code to run and follow the breakpoint. Remember to change the package name com.xx.xxx

package com.lx.myhashmap; import java.util.Map; Public class MyHashMap implements MyHashMapInter {private int initCapacity; Public int counts; //Entry array MyEntry[] table; Private double loadFactory = 0.75; public MyHashMap(int initCapacity, double loadFactory) { this.initCapacity = initCapacity; this.loadFactory = loadFactory; table = new MyEntry[initCapacity]; } @Override public String get(String key, int hashConflictIndex) { int index; if (-1 == hashConflictIndex) { index = hash(key) % initCapacity; } else { index = hashConflictIndex; If (table[index] == null) {return null; } if (table[index].key.equals(key)) {return table[index]. Value; } MyEntry temp = table[index]; while (temp.next ! = null) { temp = temp.next; if (temp.key.equals(key)) { return temp.value; } } return null; } @Override public void put(String key, String value, int hashConflictIndex) { int index; If (-1 == hashConflictIndex) {index = hash(key) % initCapacity; } else { index = hashConflictIndex; } system.out. println(" calculate index to "+ index); If (null == table[index]) {// If there is no object on the index table[index] = new MyEntry(key, value, null); counts++; reLoad(); System.out.println("put: add to array "); } else {if (table[index].key.equals(key)) {table[index].value = value; System.out.println("put: overwrite array object "); } else {// iterate over the list system.out.println ("put: enter the list "); MyEntry temp = table[index]; MyEntry father = temp; while (temp.next ! = null) { father = temp; temp = temp.next; if (temp.key.equals(key)) { temp.value = value; System.out.println("put: list object overwrite "); return; } } temp.next = new MyEntry(key, value, null); counts++; reLoad(); System.out.println("put: appended to the end of the list "); } } } @Override public void remove(String key, int hashConflictIndex) { int index; if (-1 == hashConflictIndex) { index = hash(key) % initCapacity; } else { index = hashConflictIndex; } if (table[index] == null) {system.out.println ("remove: no value "); } if (table[index].key.equals(key)) { if (table[index].next == null) { table[index] = null; System.out.println("remove: array found delete "); return; } else { table[index] = table[index].next; System.out.println("remove: found remove next element complement "); return; } } MyEntry temp = table[index]; while (temp.next ! = null) { MyEntry father = temp; temp = temp.next; if (temp.key.equals(key)) { if (temp.next == null) { father.next = null; System.out.println("remove: found in list, delete "); } else { father.next = father.next.next; System.out.println("remove: found in list, delete and link both ends "); } return; }} system.out. println("remove: completed list, no such value "); } /* Hash method */ private int hash(String key) {int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } private void reLoad() { double top = initCapacity * loadFactory; If (counts >= top) {system.out.println ("reload: hit the threshold "); initCapacity = 2 * initCapacity; MyEntry[] oldTable = table; table = new MyEntry[initCapacity]; counts = 0; for(int i = 0; i < oldTable.length; i++) { MyEntry entry = oldTable[i]; while (entry ! = null) { put(entry.key, entry.value, -1); entry = entry.next; } } } } class MyEntry implements MyEntryInter { public String key; public String value; public MyEntry next; public MyEntry(String key, String value, MyEntry next) { this.key = key; this.value = value; this.next = next; } @Override public String get() { return value; } @Override public void set() { this.value = value; }}}Copy the code

The test case

1. Array overwrite

Code:

package com.lx.myhashmap; import java.util.HashMap; Public class Demo {public static void main(String[] args) {MyHashMap map = new MyHashMap(8,0.75); map.put("1","hello",-1); System.out.println("------------------------------"); System. The out. Println (" value is: "+ map. Get (" 1", 1) + "\ n -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -"); map.put("1","world",-1); System.out.println("------------------------------"); System. The out. Println (" value is: "+ map. Get (" 1", 1) + "\ n -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -"); }}Copy the code

Output:

In the array index is calculated as 1 put: add -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - value is: hello -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - to calculate the index to 1 put: Cover an array of objects -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- value is: world -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -Copy the code
2. List append

Instead of passing -1, we pass index 1 to simulate hash collisions (assuming 1 is also computed)

Code:

package com.lx.myhashmap; import java.util.HashMap; Public class Demo {public static void main(String[] args) {MyHashMap map = new MyHashMap(8,0.75); map.put("1","hello",-1); System.out.println("------------------------------"); System. The out. Println (" value is: "+ map. Get (" 1", 1) + "\ n -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -"); map.put("3","world",1); System.out.println("------------------------------"); System. The out. Println (" value is: "+ map. Get (" 3", 1) + "\ n -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -"); }}Copy the code

Output:

In the array index is calculated as 1 put: add -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - value is: hello -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - to calculate the index to 1 put: enter the put on the list: Additional list end -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- value is: world -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -Copy the code
Expansion and 3.

Code:

package com.lx.myhashmap; import java.util.HashMap; Public class Demo {public static void main(String[] args) {MyHashMap map = new MyHashMap(8,0.75); map.put("1","hello",-1); map.put("2","hello",-1); map.put("3","hello",1); map.put("4","hello",1); map.put("5","hello",-1); map.put("6","hello",-1); map.put("7","hello",-1); }}Copy the code

Output:

Put: Evaluates to an array and evaluates to an index of 2. Put: Evaluates to an array and evaluates to an index of 1. Put: enters the linked list. Reload: the threshold is reached and the index is 1. Put: The index is 3. Put: The index is 4. Put: The index is 4. Put: Adds a calculation to the array and the index is 2. Put: Adds a calculation to the array and the index is 5. Put: Adds a calculation to the array and the index is 6Copy the code
4. The deletion of an element in the middle of the list

This is the most special place, delete cannot simply set null, need to consider whether the chain will break.

Code:

package com.lx.myhashmap; import java.util.HashMap; Public class Demo {public static void main(String[] args) {MyHashMap map = new MyHashMap(8,0.75); map.put("1","hello",-1); map.put("3","hello",1); map.put("4","hello",1); System.out.println(map.get("3",1)); map.remove("3",1); System.out.println(map.get("3",1)); }}Copy the code

Output:

Put: adds the index to the array. Put: enters the linked list. Put: adds the index to the end of the listCopy the code

Conclusion:

At present, the function of the remaining linked list whose size is larger than 8 turns to red-black tree needs to be realized. Because the tree system is relatively complex, it is not practical to jump to learn red-black tree. Later, we can write red-black tree and then go back to improve it.