12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741}; java交流737251827
privatestaticfinalintupperTol=10;
privatestaticfinalintlowerTol=2;
privateintcapacityIndex=0;
privateTreeMap[] hashtable;
privateintsize;
privateintM;
//java學(xué)習(xí)交流:737251827
publicHashTable(){this.M = capacity[capacityIndex];
size =0;hashtable =newTreeMap[M];
for(inti=0; i < M ; i ++)
hashtable[i] =newTreeMap<>();
? ? }
privateinthash(K key){
return(key.hashCode() &0x7fffffff) % M;
? ? }
publicintgetSize(){
returnsize;
? ? }
}
通過 hash 函數(shù)計算元素的數(shù)組索引，通過此索引在 hashtable 數(shù)組中找到 TreeMap，如果此 key 已存在 map 中，那么直接覆蓋，如果不存在，直接添加到 map 中；而此 map 的底層實現(xiàn)是紅黑樹，所以我們的哈希表的底層實現(xiàn)可以認為是數(shù)組加紅黑樹的實現(xiàn)；
添加完元素檢查是否需要擴容，擴容思想就是自增 capacityIndex 索引，然后去 capacity 數(shù)組中找對應(yīng)的素數(shù)即可，這樣保證了每次擴容后容量都是一個對應(yīng)哈希表數(shù)據(jù)規(guī)模的素數(shù)；
resize 函數(shù)也非常簡單，新建一個 TreeMap 數(shù)組，將原 map 數(shù)組中所有值復(fù)制到新數(shù)組，復(fù)制的過程有幾個需要注意的點，先保存一下原數(shù)組的大小，再將 M 賦值為新數(shù)組的大小，為什么需要這么做？因為第一層 for 循環(huán)需要遍歷的是原數(shù)組的大小，而第二層 foreach 循環(huán)求元素在新數(shù)組的 hash 值時需要使用新數(shù)組的大??；最后將 hashtable 引用指向新的數(shù)組；
publicvoidadd(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]);
? ? ? ? }
? ? }
}
privatevoidresize(intnewM){
TreeMap[]newHashTable=newTreeMap[newM];
for(inti=0; i < newM ; i ++)
newHashTable[i] =newTreeMap<>();
intoldM=M;
this.M = newM;
for(inti=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;
}
首先通過 hash 函數(shù)計算元素在數(shù)組中的索引，然后通過此索引去 hashtable 數(shù)組中找對應(yīng) map，如果 map 包含此元素，直接從 map 中刪除元素即可；最后檢查一下是否需要縮容，原理跟擴容是完全相同的；
publicVremove(K key){
Vret=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]);? ?
? ? ? ? }}
returnret;
}
查找和修改的邏輯基本一致，首先通過 hash 函數(shù)計算元素在數(shù)組中的索引，然后通過此索引去 hashtable 數(shù)組中找對應(yīng) map，最后通過 map 的 put 函數(shù)去修改元素；通過 map 的 containsKey 或者 get 函數(shù)去查找元素；
publicvoidset(K key, V value){TreeMap map = hashtable[hash(key)];if(!map.containsKey(key))thrownewIllegalArgumentException(key +" doesn't exist!");
map.put(key, value);}
publicbooleancontains(K key){returnhashtable[hash(key)].containsKey(key);}
publicVget(K key){returnhash
table[hash(key)].get(key);
}
importjava.util.TreeMap;
publicclassHashTable, V> {
privatefinalint[] 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};
privatestaticfinalintupperTol=10;privatestaticfinalintlowerTol=2;privateintcapacityIndex=0;
privateTreeMap[]
hashtable;privateintsize;
privateintM;
publicHashTable(){
this.M = capacity[capacityIndex];size =0;
hashtable =newTreeMap[M];
for(inti=0; i < M ; i ++)
hashtable[i] =newTreeMap<>();
}
privateinthash(K key){return(
key.hashCode() &0x7fffffff) % M;
}
publicintgetSize(){
returnsize;
}
