Simply implement a HashMap whose underlying data structure is an array + linked list, regardless of the situation that the linked list becomes a red-black tree when the length of the linked list exceeds 8.
1. Example image
2. Analysis requirements
- When putting data:
- There is no element at the index after the key value hash, so it is necessary to create a head node of the linked list and place it in the array space at this position.
- There is an element at the index after the key value hash, indicating that a Hash collision occurs, and the node needs to be mounted at the end of the linked list. If data with the same key is found during the process of traversing the linked list, just perform overwriting and do not continue Next traverse to mount new nodes.
- Suppose the space used by the array exceeds 75% of the total length, then expand the array. Create a new array first, write the old data into the new array (at this time, you need to recalculate the Hash according to the key, because the data length changes, which affects the calculation result), and replace the original old array with the new data.
- When getting data:
- If the element at the index subscript after the key value hash is empty, there is no data.
- If there is a linked list at the index subscript after the key value hash, you need to traverse the linked list to find the value corresponding to the key.
3. Code implementation
-
Node class implementation
package com.zaevn.hashmap; /** * @author: zae * @date: 2023/1/30 * @time: 11:25 */ public class Node { String key; String value; Node next; public Node(String key, String value, Node nextNode) { this.key = key; this.value = value; this.next = nextNode; } } -
LinkNode class implementation
package com.zaevn.hashmap; /** * @author: zae * @date: 2023/1/30 * @time: 11:27 */ public class ListNode { // head node Node head; /** * Add data, mount the node of the linked list * @param key * @param value */ public void addNode(String key,String value){ // end if the head node is empty if(head == null ){return;} // If the head node is not empty, mount the node down Node node = new Node(key,value,null); Node temp = head; while(true){ // Encounter the same key, overwrite the data if(key.equals(temp.key)){ temp.value = value; return; } if(temp. next == null){ break; } temp = temp. next; } // After the loop ends, hang up the data temp.next = node; } /** * retrieve data * @param key * @return */ public String getNode(String key){ if(head == null ){return null;} Node temp = head; while(true){ if(key.equals(temp.key)){ return temp. value; } if(temp. next == null){ break; } temp = temp. next; } return null; } } -
MyHashMap class implementation
package com.zaevn.hashmap; /** * @author: zae * @date: 2023/1/30 * @time: 11:27 */ public class MyHashMap { // Array initialization: 2 to the nth power ListNode[] map = new ListNode[8]; // The number of ListNode int size; // Since a new array is created first when expanding, declare it first ListNode[] mapNew; int sizeNew; /** * put method * @param key * @param value */ public void put(String key,String value){ if(size>map.length * 0.75){ System.out.println("Start expansion, current size=" + size + ", array length: " + map.length); doExtendMap(); System.out.println("The expansion is over, the current size=" + size + ", the array length is: " + map.length); } // 1. Perform a hash algorithm on the key and then take the modulus int index = Math.abs(key.hashCode())%map.length; ListNode listNode = map[index]; // If the element at the index position is empty, add a new element (create a head node) if(listNode == null){ ListNode listNodeNew = new ListNode(); Node node = new Node(key,value,null); listNodeNew.head = node; map[index] = listNodeNew; size + + ; }else{ // If the element at the index position is not empty, mount the data in the linked list listNode.addNode(key,value); } } public String get(String key){ // 1. Perform a hash algorithm on the key and then take the modulo int index = Math.abs(key.hashCode())%map.length; if(map[index] == null){ return null; }else{ return map[index].getNode(key); } } /** * Start expanding after reaching the threshold */ public void doExtendMap(){ sizeNew = 0; // 1. First create a new array with twice the original length mapNew = new ListNode[map. length * 2]; // 2. Map the old data to the new array (because the length of the array changes, the hash rule changes, and all values need to recalculate the hash value) for(int i = 0;i<map.length;i++){ ListNode listNode = map[i]; if(listNode == null){ continue; } Node temp = listNode.head; while (true) { doPutData(mapNew, temp.key, temp.value); if(temp. next == null){ break; } temp = temp. next; } } // 3. Replace the old array with the new one map = mapNew; this.size = sizeNew; } private void doPutData(ListNode[] mapParam,String key,String value){ int index = Math.abs(key.hashCode())%mapParam.length; ListNode listNode = mapParam[index]; if(listNode == null){ ListNode listNodeNew = new ListNode(); Node node = new Node(key,value,null); listNodeNew.head = node; mapParam[index] = listNodeNew; sizeNew++; }else{ listNode.addNode(key,value); } } public static void main(String[] args) { // 1. General verification MyHashMap hashMap0 = new MyHashMap(); hashMap0.put("key1","value1"); System.out.println("General verification: " + hashMap0.get("key1")); System.out.println("------------------------------------------- -"); // 2. Same key coverage verification MyHashMap hashMap1 = new MyHashMap(); hashMap1.put("key2","value00"); hashMap1.put("key2","value01"); System.out.println("Same key coverage verification: " + hashMap1.get("key2")); System.out.println("------------------------------------------- -"); // 3. Hash collision check (the indexes of k1 and k9 after hash calculation are both 6) MyHashMap hashMap2 = new MyHashMap(); hashMap2.put("k1","value_k1"); hashMap2.put("k9","value_k9"); System.out.println("Hash collision check: k1:" + hashMap2.get("k1") + " k9:" + hashMap2.get("k9")); System.out.println("------------------------------------------- -"); // 4. Expansion verification MyHashMap hashMap3 = new MyHashMap(); hashMap3.put("m3","cccccc"); hashMap3.put("c1","kkkkkk"); hashMap3.put("c2","mmmmmmm"); hashMap3.put("b1","bbbbbbb"); hashMap3.put("m1","cccccc"); hashMap3.put("c3","kkkkkk"); hashMap3.put("c4","mmmmmmm"); hashMap3.put("b2","bbbbbbb"); hashMap3.put("m2","cccccc"); hashMap3.put("c5","kkkkkk"); hashMap3.put("c6","mmmmmmm"); hashMap3.put("b3","bbbbbbb"); System.out.println("c4 after expansion:" + hashMap3.get("c4")); System.out.println("b3 after expansion:" + hashMap3.get("b3")); } }
3.Run result
Category: ZAE/Algorithms and Data Structures