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 的底層實(shí)現(xiàn)是紅黑樹迟赃，所以我們的哈希表的底層實(shí)現(xiàn)可以認(rèn)為是數(shù)組加紅黑樹的實(shí)現(xiàn)；
添加完元素檢查是否需要擴(kuò)容厂镇，擴(kuò)容思想就是自增 capacityIndex 索引纤壁，然后去 capacity 數(shù)組中找對應(yīng)的素數(shù)即可，這樣保證了每次擴(kuò)容后容量都是一個對應(yīng)哈希表數(shù)據(jù)規(guī)模的素數(shù)捺信；
resize 函數(shù)也非常簡單酌媒，新建一個 TreeMap 數(shù)組，將原 map 數(shù)組中所有值復(fù)制到新數(shù)組迄靠，復(fù)制的過程有幾個需要注意的點(diǎn)秒咨，先保存一下原數(shù)組的大小，再將 M 賦值為新數(shù)組的大小掌挚，為什么需要這么做雨席？因?yàn)榈谝粚?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 中刪除元素即可；最后檢查一下是否需要縮容查辩，原理跟擴(kuò)容是完全相同的胖笛；
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;
}
