数据结构篇 09、哈希表 -- 简化版 HashMap，一线互联网移动架构师 360°全方面性能调优

12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741}; java交流737251827

privatestaticfinalintupperTol=10;

privatestaticfinalintlowerTol=2;

privateintcapacityIndex=0;

privateTreeMap[] hashtable;

privateintsize;

privateintM;

//java学习交流: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;

    }

}

2、往哈希表中添加元素

通过 hash 函数计算元素的数组索引，通过此索引在 hashtable 数组中找到 TreeMap，如果此 key 已存在 map 中，那么直接覆盖，如果不存在，直接添加到 map 中；而此 map 的底层实现是红黑树，所以我们的哈希表的底层实现可以认为是数组加红黑树的实现；

添加完元素检查是否需要扩容，扩容思想就是自增 capacityIndex 索引，然后去 capacity 数组中找对应的素数即可，这样保证了每次扩容后容量都是一个对应哈希表数据规模的素数；

resize 函数也非常简单，新建一个 TreeMap 数组，将原 map 数组中所有值复制到新数组，复制的过程有几个需要注意的点，先保存一下原数组的大小，再将 M 赋值为新数组的大小，为什么需要这么做？因为第一层 for 循环需要遍历的是原数组的大小，而第二层 foreach 循环求元素在新数组的 hash 值时需要使用新数组的大小；最后将 hashtable 引用指向新的数组；

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;

}

3、从哈希表中移除元素

首先通过 hash 函数计算元素在数组中的索引，然后通过此索引去 hashtable 数组中找对应 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;

}

4、从哈希表中查找和修改元素

查找和修改的逻辑基本一致，首先通过 hash 函数计算元素在数组中的索引，然后通过此索引去 hashtable 数组中找对应 map，最后通过 map 的 put 函数去修改元素；通过 map 的 containsKey 或者 get 函数去查找元素；

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);

}

5、哈希表完整代码

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;

}