java实现数据结构14（哈希表详解代码之自定义哈希表）

阳光穿透心脏的1/2处 2023-06-25 03:06 2阅读 0赞

## 自定义哈希表 ##

import java.util.TreeMap;
    
    /** * @description: 自定义动态哈希表 * @author: liangrui * @create: 2019-12-24 18:30 **/
    public class HashTable<K,V> { 
    
        //最大冲突数
        private static final int upperTol=10;
        //最小冲突数
        private static final int lowerTol=2;
        //初始容器大小
        private static final int initCapacity=7;
    
        //使用TreeMap创建哈希表
        private TreeMap<K,V>[] hashtable;
        //元素个数
        private int size;
        //哈希表大小
        private int M;
    
        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(initCapacity);
        }
    
        /** * 获取哈希值 * @param key * @return */
        private int hash(K key){ 
            return (key.hashCode()&0x7fffffff)%M;
        }
    
        public int getSize(){ 
            return size;
        }
    
        /** * 重新设置容器大小 * @param newM */
        private void resize(int newM) { 
            TreeMap<K,V>[] newHashTable=new TreeMap[newM];
            for (int i = 0; i < newM; i++) { 
                newHashTable[i]=new TreeMap<>();
            }
    
            for (int i = 0; i < M; i++) { 
                for (K key:hashtable[i].keySet()){ 
                    newHashTable[hash(key)].put(key,hashtable[i].get(key));
                }
            }
    
            this.M=newM;
            this.hashtable=newHashTable;
        }
    
        /** * 添加新的元素 * @param key * @param value */
        public void add(K key,V value){ 
            TreeMap<K,V> map=hashtable[hash(key)];
            if (!map.containsKey(key)){ 
                map.put(key, value);
                size++;
                if (size>=upperTol*M){ 
                    resize(2*M);
                }
            }
        }
    
        /** * 删除元素 * @param key * @return */
        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&&M>initCapacity){ 
                    resize(M/2);
                }
            }
            return ret;
        }
    
        /** * 修改指定键对应的值 * @param key * @param value */
        public void set(K key,V value){ 
            TreeMap<K,V> map=hashtable[hash(key)];
            if (map.containsKey(key)){ 
                map.put(key,value);
            }else { 
                throw new IllegalArgumentException(key+" doesn't exist.");
            }
        }
    
        /** * 查看是否存在指定键对应的元素 * @param key * @return */
        public boolean contains(K key){ 
            return hashtable[hash(key)].containsKey(key);
        }
    
        /** * 获取指定键对应的元素值 * @param key * @return */
        public V get(K key){ 
            return hashtable[hash(key)].get(key);
        }
    
    }