MyHashMap：

/* 手動實現(xiàn)一個HashMap(根據(jù)JDK 1.7, 數(shù)組 + 鏈表)規(guī)定key和value都不能是null，但是JDK 1.7允許key和value為null。*/public class MyHashMap<K, V> {// 屬性private static final int MAX_CAPACITY = 1 << 30; // 即最大容量為2^30private static final int DEFAULT_CAPACITY = 1 << 4; // 初始默認容量為16private static final double DEFAULT_LOAD_FACTOR = 0.75; // 默認加載因子為0.75private Node<K, V>[] table; // 哈希表底層數(shù)組private int size; // 元素個數(shù)private double loadFactor; // 加載因子// 閾值 = 數(shù)組長度 * 加載因子(如果調(diào)用無參構(gòu)造，則閾值=16*0.75=12。如果傳遞了初始容量，則這個等式不一定成立，例如initialCapacity=30，則底層數(shù)組長度為32，閾值也等于30)private int threshold;// 節(jié)點內(nèi)部類private static class Node<K, V> {int hash;K key;V value;Node<K, V> next;Node(int hash, K key, V value, Node<K, V> next) {this.hash = hash;this.key = key;this.value = value;this.next = next;}@Overridepublic String toString() {return key + "=" + value;}}// 構(gòu)造方法public MyHashMap() {this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);}public MyHashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);}@SuppressWarnings("unchecked")public MyHashMap(int initialCapacity, double loadFactor) {if (initialCapacity < 0 || initialCapacity > MAX_CAPACITY) {throw new IllegalArgumentException("initialCapacity=" + initialCapacity);}if (loadFactor <= 0 || Double.isNaN(loadFactor)) {// Double.isNaN()：如果參數(shù)不是一個double類型的數(shù)字，則返回true，否則返回falsethrow new IllegalArgumentException("loadFactor=" + loadFactor);}// 參數(shù)都合法this.loadFactor = loadFactor;int length = tableSizeFor(initialCapacity); // 計算哈希表底層數(shù)組的長度// table = new Node<K, V>[length]; // 此行代碼錯誤，沒有"泛型數(shù)組"這個概念，不能newtable = (Node<K, V>[]) new Node[length]; // 注意這種寫法。方法最上面加一個注解，就不再有警告this.threshold = initialCapacity;}// 求大于等于cap的最小的2的n次冪private int tableSizeFor(int cap) {int n = cap - 1;n |= n >>> 1;n |= n >>> 2;n |= n >>> 4;n |= n >>> 8;n |= n >>> 16;return n < 0 ? 1 : (n >= MAX_CAPACITY ? MAX_CAPACITY : n + 1);}/*** 根據(jù)指定的key來獲取對應的value* @param key 指定的key* @return 對應的value* 時間復雜度為O(1)*/public V get(K key) {int hash = hash(key);int index = indexFor(hash, table.length);for (Node<K, V> node = table[index]; node != null; node = node.next) {if (hash == node.hash && (key == node.key) || key.equals(node.key)) {return node.value;}}return null;}private int hash(K key) {// 這就是JDK 1.8源碼int h;return key == null ? 0 : (h = key.hashCode()) ^ (h >>> 16);}private int indexFor(int hash, int length) {// returnn hash % length;return hash & (length - 1); //位運算，效率高}/*** 向HashMap中添加元素對* @param key 待添加的key* @param value 待添加的value* @return 返回oldValue* 時間復雜度為O(1)*/public V put(K key, V value) {if (key == null) throw new NullPointerException();int hash = hash(key);int index = indexFor(hash, table.length);for (Node<K, V> node = table[index]; node != null; node = node.next) {if (hash == node.hash && (key == node.key || key.equals(node.key))) {// 有相同的元素，不添加，只更新valueV oldValue = node.value;node.value = value;return oldValue;}}// 沒有相同元素，開始添加addNode(hash, key, value, index);return null;}private void addNode(int hash, K key, V value, int index) {if (size >= threshold) {// 需要擴容resize(table.length << 1); // 擴容為原來的2倍}Node<K, V> node = new Node<>(hash, key, value, table[index]); // 泛型類，等號右邊的泛型可以不寫table[index] = node;size++; // Caution!!!}@SuppressWarnings("unchecked")private void resize(int newLength) {if (table.length == MAX_CAPACITY) {// 達到最大，不再擴容threshold = Integer.MAX_VALUE; // size不會超過Integer.MAX_VALUE，即addNode()方法中的if永遠為false，不再擴容。return;}// 進行擴容Node<K, V>[] newTable = (Node<K, V>[]) new Node[newLength];threshold = (int) (newLength * loadFactor);for (int i = 0; i < table.length; i++) {for (Node<K, V> node = table[i]; node != null;) {int hash = node.hash;int index = indexFor(hash, newLength); // 在新數(shù)組中的索引位置/*Node<K, V> newNode = new Node<>(hash, node.key, node.value, newTable[index]); // 相當于把節(jié)點重新復制了，需要額外空間，不推薦newTable[index] = newNode;*/Node<K, V> nextNode = node.next; // 記錄下一個元素, Caution!!!node.next = newTable[index];newTable[index] = node;node = nextNode; // Caution!!!}}table = newTable;}/*** 根據(jù)指定的key刪除元素，并返回value* @param key 指定的key* @return 對應的value* 時間復雜度為O(1)*/public V remove(K key) {if (key == null) return null; // 為了簡單起見，假設key和value都不能為nullint hash = hash(key);int index = indexFor(hash, table.length);Node<K, V> prev = null;for (Node<K, V> node = table[index]; node != null; node = node.next) {if (hash == node.hash && (key == node.key || key.equals(node.key))) {if (prev == null) {// 第一個節(jié)點就是要刪除的節(jié)點table[index] = node.next;} else {prev.next = node.next;}size--;return node.value;}prev = node;}return null;}/*** 獲取HashMap元素的個數(shù)* @return HashMap元素的個數(shù)*/public int size() {return size;}/*** 判斷HashMap是否為空* @return 如果為空，返回true；如果不空，返回false*/public boolean isEmpty() {return size == 0;}/*** 是否包含指定的key* @param key 指定的key* @return 如果包含指定的key，返回true；否則返回false*/public boolean containsKey(K key) {return get(key) != null;}/*** 清空哈希表*/public void clear() {for (int i = 0; i < table.length; i++) {table[i] = null;}size = 0; // Caution!!!}/*** 打印HashMap，需要重寫toString()方法* @return HashMap的字符串形式*/@Overridepublic String toString() {if (size == 0) return "{}";StringBuffer sb = new StringBuffer();sb.append("{");for (int i = 0; i < table.length; i++) {for (Node<K, V> node = table[i]; node != null; node = node.next) {sb.append(node).append(", ");// append參數(shù)是String類型，說明這里node是String類型，所以要重寫Node類的toString()方法}}sb.delete(sb.length() - 2, sb.length()); // 包左不包右return sb.append("}").toString();} }

MyHashMapTest：

public class MyHashMapTest {public static void main(String[] args) {MyHashMap<String, String> map = new MyHashMap<>(2);map.put("劉強東", "章澤天");map.put("王寶強", "馬蓉");map.put("文章", "馬伊琍");map.put("賈乃亮", "李小璐");System.out.println(map); // {賈乃亮=李小璐, 劉強東=章澤天, 王寶強=馬蓉, 文章=馬伊琍}System.out.println(map.size()); // 4 擴容正常// V remove(K key)System.out.println(map.remove("henson_z")); // nullSystem.out.println(map.remove("文章")); // 馬伊琍System.out.println(map); // {賈乃亮=李小璐, 劉強東=章澤天, 王寶強=馬蓉}System.out.println(map.size()); // 3// V get(K key)// boolean containsKey(K key)System.out.println(map.get("劉強東")); // 章澤天System.out.println(map.get("鄧超")); // nullSystem.out.println(map.containsKey("劉強東")); // trueSystem.out.println(map.containsKey("鄧超")); // false// V put(K key, V value)System.out.println(map.put("鄧超", "孫儷")); // nullSystem.out.println(map.put("王寶強", "")); // 馬蓉System.out.println(map); // {鄧超=孫儷, 賈乃亮=李小璐, 劉強東=章澤天, 王寶強=}System.out.println(map.size()); // 4// 判空System.out.println(map.isEmpty()); // falsemap.clear();System.out.println(map.isEmpty()); // true} }

以上結(jié)果都經(jīng)過本人實際測試，結(jié)果都正確。

---

結(jié)束語：如果本篇博客對您有幫助，請點贊、收藏或關注，您的鼓勵是博主進步的動力，感謝支持，共同進步。

總結(jié)

以上是生活随笔為你收集整理的手写HashMap及测试的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。