哈希表是一种比较高级的数据结构，java标准库中的HashMap的底层实现就是哈希表，具体来说是数组结合链表和红黑树；而本文实现的哈希表是简化版的HashMap，通过数组和红黑树实现的，但基本思想是一致的；
由于哈希表的数组加链表和红黑树的底层实现太过复杂，我们本文中哈希表的实现是简化版的底层实现，但哈希表的底层思路基本一致；
本文哈希表是借助java标准库中的TreeMap实现的，因为TreeMap的底层实现是红黑树，本文使用的TreeMap[]数组，所以可以认为本文底层实现是数组加红黑树；
哈希冲突是指不同元素计算出的数组索引值相同，此时就需要在一个数组索引上存放多个值，解决方法就是可以让数组的每个位置都是一个链表或者二叉树，这种解决方法也称之为链地址法；本文哈希冲突的处理方式就是链地址法；
求数组索引时模一个与数据规模相近的素数，为什么在求数组索引时模一个与数据规模相近的素数，这是因为数学研究发现这样产生哈希冲突的概率更小，这些底层实现后面会讲解；
1、哈希表基本属性与方法
int型的capacity数组是一组素数，当哈希表数据规模不断增大时，我们只需要取capacity中对应规模的素数即可；
upperTol和lowerTol是用于扩容和缩容的系数，我们后边扩容缩容时会讲解；
capacityIndex是capacity数组的索引，当哈希表数据规模不断增大，我们只需要增加此索引值，然后通过此索引值去capacity数组中取值即可；
hashtable是TreeMap类型的数组，用于存放数据；
size表示哈希表中数据个数；
M表示hashtable数组的大小；
在构造函数中通过capacity数组和capacityIndex索引给M赋值，初始化hashtable数组；
hash函数就是求元素在数组中的索引，先通过hashcode求哈希值，然后模上M，此时M就是对应哈希表数据规模的素数；
getSize返回哈希表中数据个数；
public class HashTable<K extends Comparable<K>, V> {
private final int[] capacity
= {53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469,
12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741};
private static final int upperTol = 10;
private static final int lowerTol = 2;
private int capacityIndex = 0;
private TreeMap<K, V>[] hashtable;
private int size;
private int M;
public HashTable(){
this.M = capacity[capacityIndex];
size = 0;
hashtable = new TreeMap[M];
for(int i = 0 ; i < M ; i ++)
hashtable[i] = new TreeMap<>();
}
private int hash(K key){
return (key.hashCode() & 0x7fffffff) % M;
}
public int getSize(){
return size;
}
、、、
}
复制代码2、往哈希表中添加元素
通过hash函数计算元素的数组索引，通过此索引在hashtable数组中找到TreeMap，如果此key已存在map中，那么直接覆盖，如果不存在，直接添加到map中；而此map的底层实现是红黑树，所以我们的哈希表的底层实现可以认为是数组加红黑树的实现；
添加完元素检查是否需要扩容，扩容思想就是自增capacityIndex索引，然后去capacity数组中找对应的素数即可，这样保证了每次扩容后容量都是一个对应哈希表数据规模的素数；
resize函数也非常简单，新建一个TreeMap数组，将原map数组中所有值复制到新数组，复制的过程有几个需要注意的点，先保存一下原数组的大小，再将M赋值为新数组的大小，为什么需要这么做？因为第一层for循环需要遍历的是原数组的大小，而第二层foreach循环求元素在新数组的hash值时需要使用新数组的大小；最后将hashtable引用指向新的数组；
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 && capacityIndex + 1 < capacity.length){
capacityIndex ++;
resize(capacity[capacityIndex]);
}
}
}
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;
}
复制代码3、从哈希表中移除元素
首先通过hash函数计算元素在数组中的索引，然后通过此索引去hashtable数组中找对应map，如果map包含此元素，直接从map中删除元素即可；最后检查一下是否需要缩容，原理跟扩容是完全相同的；
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 && capacityIndex - 1 >= 0){
capacityIndex --;
resize(capacity[capacityIndex]);
}
}
return ret;
}
复制代码4、从哈希表中查找和修改元素
查找和修改的逻辑基本一致，首先通过hash函数计算元素在数组中的索引，然后通过此索引去hashtable数组中找对应map，最后通过map的put函数去修改元素；通过map的containsKey或者get函数去查找元素；
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);
}
复制代码5、哈希表完整代码
import java.util.TreeMap;
public class HashTable<K extends Comparable<K>, V> {
private final int[] capacity
= {53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469,
12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741};
private static final int upperTol = 10;
private static final int lowerTol = 2;
private int capacityIndex = 0;
private TreeMap<K, V>[] hashtable;
private int size;
private int M;
public HashTable(){
this.M = capacity[capacityIndex];
size = 0;
hashtable = new TreeMap[M];
for(int i = 0 ; i < M ; i ++)
hashtable[i] = new TreeMap<>();
}
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 && capacityIndex + 1 < capacity.length){
capacityIndex ++;
resize(capacity[capacityIndex]);
}
}
}
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 && capacityIndex - 1 >= 0){
capacityIndex --;
resize(capacity[capacityIndex]);
}
}
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;
}
}
复制代码
![[02/27][官改] Simplicity@MIX2 ROM更新-一一网](https://www.proyy.com/wp-content/uploads/2020/02/3168457341.jpg)
![[桜井宁宁]COS和泉纱雾超可爱写真福利集-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/4d3cf227a85d7e79f5d6b4efb6bde3e8.jpg)
![[桜井宁宁] 爆乳奶牛少女cos写真-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/d40483e126fcf567894e89c65eaca655.jpg)
