public class HashTable<K,V>{
private final int upperTol = 10;
private final int lowerTol = 2;
private static final int defaultCapacity = 7;
private TreeMap<K,V>[] hashTable;
private int m;
private int size;
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(defaultCapacity);
}
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);
}
}
}
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;
}
public V remove(K key){
TreeMap<K,V> map = hashTable[hash(key)];
V result = null;
if(map.containsKey(key)){
result = map.remove(key);
size --;
if(size < lowerTol*m&&m/2>=defaultCapacity){
resize(m/2);
}
}
return result;
}
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)].contains(key);
}
public V get(K key){
return hashTable[hash(key)].get(key);
}
}
