摘要:代碼實現表的長度,即具體有多少個位置選擇一個合適的素數取的絕對值修改添加即除以由于在方法中有對進行操作,在往新哈希表中存數據時應該用計算相應的值哈希表的均攤復雜度為,有這么好的性能其中一個原因是它犧牲了順序性。
哈希沖突的解決方法 鏈地址法
在Java8開始,當哈希沖突達到一定的程度,每一個位置從鏈表轉化為紅黑樹。
時間復雜度分析 哈希表的動態空間處理平均每個地址承載的元素多過一定程度,即擴容(N/M >= upperTol)
平均每個地址承載的元素少過一定程度,即縮容(N/M <= lowerTol)
哈希表復雜度分析剛開始我們在擴容的時候直接是2*M,它可能造成擴容后的哈希表分布不均勻,可以按著下面這個表格來設置M值。
代碼實現public class HashTable{ private final int[] 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 }; private static final int upperTol = 10; private static final int lowerTol = 2; private static final int initCapacity = 7; private int CapacityIndex = 0; private TreeMap [] hashtable; private int size; private int M; //hash表的長度,即具體有多少個位置(選擇一個合適的素數) public HashTable(){ //this.M = M; this.M = capacity[CapacityIndex]; size = 0; hashtable = new TreeMap[M]; for(int i = 0 ; i < M ; i ++) hashtable[i] = new TreeMap<>(); } /*public HashTable(){ this(initCapacity); }*/ private int hash(K key){ //key.hashCode() & 0x7fffffff 取key.hashCode()的絕對值 return (key.hashCode() & 0x7fffffff) % M; } public int getSize(){ return size; } public void add(K key, V value){ TreeMap 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) //即size除以M >=upperTol //resize(2 * M); CapacityIndex ++; resize(capacity[CapacityIndex]); } } public V remove(K key){ V ret = null; TreeMap map = hashtable[hash(key)]; if(map.containsKey(key)){ ret = map.remove(key); size --; if(size < lowerTol * M && CapacityIndex-1 >= 0) CapacityIndex --; //resize(M / 2); resize(capacity[CapacityIndex]); } return ret; } public void set(K key, V value){ TreeMap 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)].containsKey(key); } public V get(K key){ return hashtable[hash(key)].get(key); } private void resize(int newM){ TreeMap [] newHashTable = new TreeMap[newM]; for(int i = 0 ; i < newM ; i ++) newHashTable[i] = new TreeMap<>(); //由于在hash()方法中有對M進行操作,在往新哈希表中存數據時應該用newM計算hash相應的hash值 int oldM = M; this.M = newM; for(int i = 0 ; i < oldM ; i ++){ TreeMap map = hashtable[i]; for(K key: map.keySet()) newHashTable[hash(key)].put(key, map.get(key)); } this.hashtable = newHashTable; } }
哈希表的均攤復雜度為O(1),有這么好的性能其中一個原因是它犧牲了順序性。
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/74733.html
摘要:屬性記錄了哈希表目前已有節點鍵值對的數量。字典字典的結構類型特定函數私有數據哈希表兩個記錄進度的標志。此外,字典在進行時,刪除查找更新等操作會在兩個哈希表上進行。在對哈希表進行擴容或收縮操作時,使用漸進式完成。 字典,是一種用于保存鍵值對的抽象數據結構。由于 C 語言沒有內置字典這種數據結構,因此 Redis 構建了自己的字典實現。 在 Redis 中,就是使用字典來實現數據庫底層的。...
摘要:現在使用的各種哈希函數基本上只能保證較小概率出現兩個不同的其相同的情況。而出現兩個值對應的相同的情況,稱為哈希沖突。中的哈希表需要指出的是,中自造的哈希表屬于內部使用的數據結構,因此,并不是一個通用的哈希表。 源文件路徑 版本:1.8.0 csrccoreNgx_hash.h srccoreNgx_hash.c 關于hash表 Nginx實現的hash表和常見的hash表大體...
閱讀 733·2021-11-23 09:51
閱讀 2430·2021-10-11 11:10
閱讀 1299·2021-09-23 11:21
閱讀 1091·2021-09-10 10:50
閱讀 882·2019-08-30 15:54
閱讀 3326·2019-08-30 15:53
閱讀 3287·2019-08-30 15:53
閱讀 3186·2019-08-29 17:23