参考文章：
https://www.cnblogs.com/ysocean/p/8032656.html Java数据结构和算法（十三）——哈希表（强推）
https://www.cnblogs.com/skywang12345/p/3310835.html Java 集合系列10之 HashMap详细介绍(源码解析)和使用示例
https://github.com/liuyubobobo/Play-with-Algorithms
哈希表也是一种重要的数据结构，其核心思想是 “用空间换时间” ，其查询操作基本上能达到 O(1) 级别。哈希表的原理，上面两篇博客应该能够将的明明白白，代码部分参考 波波老师 的代码部分，写的是非常的优雅。
下面不讲原理，直接上代码主体部分：
import java.util.Map; import java.util.TreeMap; public class HashTable<K, V> { private static final int upperTol = 10; private static final int lowerTol = 2; private static final int initCapacity = 7; private TreeMap<K, V>[] hashtable; private int size; private int M; public HashTable(int M){ this.M = M; size = 0; hashtable = new TreeMap[M]; for(int i = 0 ; i < M ; i ++) hashtable[i] = new TreeMap<>(); } public HashTable(){ this(initCapacity); } private int hash(K key){ return (key.hashCode() & 0x7fffffff) % M; } public int getSize(){ return size; } public void add(K key, V value){ TreeMap<K, V> map = hashtable[hash(key)]; if(map.containsKey(key)) map.put(key, value); else{ map.put(key, value); size ++; if(size >= upperTol * M) resize(2 * M); } } public V remove(K key){ V ret = null; TreeMap<K, V> map = hashtable[hash(key)]; if(map.containsKey(key)){ ret = map.remove(key); size --; if(size < lowerTol * M && M / 2 >= initCapacity) resize(M / 2); } return ret; } public void set(K key, V value){ TreeMap<K, V> map = hashtable[hash(key)]; if(!map.containsKey(key)) throw new IllegalArgumentException(key + " doesn't exist!"); map.put(key, value); } public boolean contains(K key){ return hashtable[hash(key)].containsKey(key); } public V get(K key){ return hashtable[hash(key)].get(key); } private void resize(int newM){ TreeMap<K, V>[] newHashTable = new TreeMap[newM]; for(int i = 0 ; i < newM ; i ++) newHashTable[i] = new TreeMap<>(); int oldM = M; this.M = newM; for(int i = 0 ; i < oldM ; i ++){ TreeMap<K, V> map = hashtable[i]; for(K key: map.keySet()) newHashTable[hash(key)].put(key, map.get(key)); } this.hashtable = newHashTable; } }
