【數據結構】9.java源碼關於HashTable
- 2019 年 10 月 3 日
- 筆記
1.hashtable的內部結構
基礎存儲數據的hash桶由Entry結構的數組存放
而entry數據結構，有hash，key和value，還有一個指向下一個節點的引用next對象
這裡就和hashmap中的數據結構不一樣了，hashmap中的數據結構是node，雖然結構上差不多，但是setvalue的非空判斷和hashcode的散列取值都是和node不一樣的
那麼這些數據在什麼時候用呢？？？
下面來一一了解
2.hashtable的構造函數
這裡需要注意一下了，我們前面提到說hashmap中的構造函數，其實實際上是不對hash桶進行實例化的，但是hashtable不一樣，他會直接實例化大小，並且實例化成你指定的大小
而且這裡默認的初始化容器的大小是11，負載因子代銷默認0.75，負載因子的作用就是規定最大容量：hash桶的大小*負載因子
public TestHashTable(int initialCapacity, float loadFactor) { //非空判斷 if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity); if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal Load: " + loadFactor); //至少設置為1 if (initialCapacity==0) initialCapacity = 1; this.loadFactor = loadFactor; table = new Entry<?,?>[initialCapacity]; threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1); }
3.hashtable的增加元素策略
1.這裡的put方法加了synchronized修飾符，用來標識執行緒安全
2.這裡進行put取索引位置的時候，是直接用的key的hashcode方法，並且對hashcode結果進行取正數(& 0x7FFFFFFF)，然後對hash桶進行取余%
然後就是判斷這個key是否存在於這個hash桶中，如果存在更新舊值，並返回舊值
不存在，那麼就添加一個entry，所以put操作的關鍵就是addEntry
而我們add操作其實就是找到對應的散列位置，然後用頭插法
private void addEntry(int hash, K key, V value, int index) { modCount++; Entry<?,?> tab[] = table; if (count >= threshold) { // Rehash the table if the threshold is exceeded rehash(); tab = table; hash = key.hashCode(); index = (hash & 0x7FFFFFFF) % tab.length; } // Creates the new entry. @SuppressWarnings("unchecked") Entry<K,V> e = (Entry<K,V>) tab[index]; //頭插法 tab[index] = new Entry<>(hash, key, value, e); count++; }
說實話，這裡相比hashmap來說簡單多了，主要是少了樹化的操作
4.hashtable刪除元素策略
刪除就比較簡單了，就是找到對應的索引位置，然後再查找鏈表，如果是頭節點，直接把entry.next設置為索引位置的數據，如果不是，就要獲取到pre節點，然後pre.next = entry.next
public synchronized V remove(Object key) { Entry<?,?> tab[] = table; int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; @SuppressWarnings("unchecked") Entry<K,V> e = (Entry<K,V>)tab[index]; for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) { if ((e.hash == hash) && e.key.equals(key)) { modCount++; if (prev != null) { prev.next = e.next; } else { tab[index] = e.next; } count--; V oldValue = e.value; e.value = null; return oldValue; } } return null; }
主要是for循環這個地方有點意思，其餘的到還好，無非就是返回舊值而已
5.修改元素，查找元素
修改不多做操作了，和添加，刪除操作差不多，只是沒有裡面的多餘操作，就是找到元素就直接返回了
6.hashtable特殊操作
1.hashtable是允許放空鍵值的，也就是鍵和值都可以放null
2.還有hashtable是執行緒安全的
3.hashmap再1.8之後是數組+鏈表+紅黑樹，hashtable還是很光棍-》數組+鏈表
4.擴容需要說一下，hashmap會擴容到比設置值大的最小2次冪，hashtable就群魔亂舞隨意了
5.hashmap和hashtable都是取余，但是有點不同，因為hashmap是2次冪，所以取余的方式不一樣是：(n – 1) & hash,為什麼這樣，請複習hashmap源碼分析。。。
7.hashtable的刷新擴容
protected void rehash() { int oldCapacity = table.length; Entry<?,?>[] oldMap = table; //直接左移一位，也就是擴大2倍然後+1 =》 大小擴為 2n + 1 int newCapacity = (oldCapacity << 1) + 1; if (newCapacity - MAX_ARRAY_SIZE > 0) { //Integer.MAX_VALUE - 8 if (oldCapacity == MAX_ARRAY_SIZE) //如果老的容量已經達到這個值，anemia繼續保持 // Keep running with MAX_ARRAY_SIZE buckets return; newCapacity = MAX_ARRAY_SIZE; //否則設置為允許的最大值 } //創建新的hash桶 Entry<?,?>[] newMap = new Entry<?,?>[newCapacity]; modCount++; //設置新的閾值 threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1); table = newMap; //遍歷hash桶，從後往前 for (int i = oldCapacity ; i-- > 0 ;) { //遍歷所有索引下的鏈表，吧鏈表添加到新的hash桶上 for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) { Entry<K,V> e = old; old = old.next; //先取正，然後取余 int index = (e.hash & 0x7FFFFFFF) % newCapacity; e.next = (Entry<K,V>)newMap[index]; newMap[index] = e; } } }
總結一下吧：
說實話，看完hashtable沒花多久時間，相比較hashmap給人的驚為天人的操作，hashtable相對來說就比較樸實無華了，唯一的幾個亮點就是執行緒安全，然後。。。。
想不出來了，只能說存在即合理，不能說hashtable會比較low，也許是我眼拙，大道至簡，也許沒有那些花里胡哨的才是真正最實用的
參考：
https://juejin.im/post/5a03b258518825188e515d89
https://blog.csdn.net/yyc1023/article/details/80619623
