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;

//java学习交流:737251827

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>[] new HashTable = 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 hash

table[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;
}