## Java之HashMap的實現 基于java.util.Map接口實現的簡單版HashMap； ~~~ /** * HashMap實現 * @Author: mango * @Date: 2022/5/21 10:53 上午 * @Desc: 數組加鏈表 */ public class HashMap<K,V> implements Map<K,V> { private Node<K,V>[] array; // 容量 private int capacity; // 大小 private int size; // 默認容量 private int DEFAULT_CAPACITY = 8; // 負載因子 private float LOAD_FACTOR = 0.75f; public HashMap(){ this.size = 0; } // hash函數 static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } @Override public int size() { return size; } @Override public boolean isEmpty() { return size == 0; } @Override public boolean containsKey(Object key) { return getNode(hash(key), (K) key) != null ? true : false; } private Node<K,V> getNode(int hash,K key){ int index = hash % capacity; if(array[index] == null){ return null; }else{ Node<K,V> node = array[index]; while (node != null && !node.key.equals(key)){ node = node.next; } if(node != null){ return node; } } return null; } private Node<K,V> getNodeByVal(int hash,V val){ int index = hash % capacity; if(array[index] == null){ return null; }else{ Node<K,V> node = array[index]; while (node != null && !node.val.equals(val)){ node = node.next; } if(node != null){ return node; } } return null; } @Override public boolean containsValue(Object value) { return getNodeByVal(hash(value),(V)value) == null ? true : false; } @Override public V get(Object key) { if(containsKey(key)){ return getNode(hash(key), (K) key).val; } return null; } // 擴容,縮容 private void resize(int flag){ int oldCapacity = capacity; Node<K,V>[] oldArray = this.array; if(flag == 1) { this.capacity = this.capacity << 1; }else{ this.capacity = this.capacity >> 1; } this.array = new Node[capacity]; this.size = 0; for(int i=0;i<oldCapacity;i++){ Node<K, V> node = oldArray[i]; if(node != null){ putVal(node.key,node.val); while (node.next != null){ putVal(node.next.key,node.next.val); node = node.next; } } } } private void resize(){ int m = (int) (capacity * LOAD_FACTOR / 2); // 超過負載，則擴容 if(size / capacity > LOAD_FACTOR){ resize(1); System.out.println("擴容"); } // 低于負載的一半，且縮減后的容量不小于默認容量，則縮容 else if(size < m && m >= (DEFAULT_CAPACITY / 2) ){ resize(0); System.out.println("縮容"); } } @Override public V put(K key, V value) { // 如果為空，則先創建默認容量大小的數組 if(array == null){ this.array = new Node[DEFAULT_CAPACITY]; this.capacity = DEFAULT_CAPACITY; } // 設置值 putVal(key,value); // 容量控制 resize(); return value; } private void putVal(K key,V value){ int index = hash(key) % capacity; Node<K,V> node = array[index]; // 如果key已經存在，則替換value的值 if(containsKey(key)){ getNode(hash(key),key).val = value; return ; } // 不存在，則加入 if(node == null){ array[index] = new Node(key,value); }else{ while (node.next != null){ node = node.next; } node.next = new Node(key,value); } size++; } @Override public V remove(Object key) { if(containsKey(key)){ int index = hash(key) % capacity; if(array[index] != null){ Node<K,V> node = array[index]; if(node.next == null){ array[index] = null; }else{ while (node.next != null && !node.next.key.equals(key)){ node = node.next; } node.next = node.next.next; } size--; // 容量控制 resize(); } } return null; } @Override public void putAll(Map m) { for(Object k : m.keySet()){ K key = (K) k; putVal(key, (V) m.get(k)); } } @Override public void clear() { this.size = 0; this.capacity = 0; this.array = null; } @Override public Set<K> keySet() { HashSet set = new HashSet(); for(int i=0;i<capacity;i++){ Node<K, V> node = this.array[i]; if(node != null){ set.add(node.key); while (node.next != null){ set.add(node.next.key); node = node.next; } } } return set; } @Override public Collection values() { List<V> result = new ArrayList<>(); for(int i=0;i<capacity;i++){ Node<K, V> node = this.array[i]; if(node != null){ result.add(node.val); while (node.next != null){ result.add(node.next.val); node = node.next; } } } return result; } @Override public Set<Entry<K, V>> entrySet() { HashSet<Entry<K,V>> set = new HashSet(); for(int i=0;i<capacity;i++){ Node<K, V> node = this.array[i]; if(node != null){ set.add(node); while (node.next != null){ set.add(node.next); node = node.next; } } } return set; } /** * 鏈表節點 */ final class Node<K,V> implements Entry<K,V>{ public K key; public V val; public Node<K,V> next; public Node(K key, V val) { this.val = val; this.key = key; } @Override public String toString() { return "Node{" + "key=" + key + ", val=" + val + ", next=" + next + '}'; } @Override public K getKey() { return key; } @Override public V getValue() { return val; } @Override public V setValue(V value) { this.val = value; return value; } } @Override public String toString() { return "HashMap{" + "array=" + Arrays.toString(array) + ", capacity=" + capacity + ", size=" + size + '}'; } } ~~~