HashTable原理和源码分析详解编程语言

上一篇文章《HashMap原理和源码分析》介绍了HashMap。比对着HashMap，来看一下HashTable的特性.

参数：

private transient HashtableEntry ?,? [] table;// 数组存储 

private transient int count; // 结点的总数 

private int threshold; // 扩容的临界值 

private float loadFactor; // 默认是0.75，到达需要扩容的比例 

private transient int modCount = 0; // 修改的次数，例如put、remove、clear等 

从参数就可以看出跟HashMap大同小异，而且简洁了许多。

构造函数

public Hashtable() {

 this(11, 0.75f); // 默认构造函数，直接设定初始容量 

public Hashtable(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); 

 if (initialCapacity==0) 

 initialCapacity = 1; 

 this.loadFactor = loadFactor; 

 table = new HashtableEntry ?,? [initialCapacity];// 直接使用初始容量 

 // 原本 threhold = initialCapacity * loadFactor 

 // 但是这里实际上设置threshold 为initialCapacity 

 threshold = (int)Math.min(initialCapacity, MAX_ARRAY_SIZE + 1); 

从上面构造函数可以看到，默认初始容量 = threshold = 11; 加载因子 = 0.75

put
增加或者修改一个节点

public synchronized V put(K key, V value) {

 if (value == null) {

 // 不支持value为null 

 throw new NullPointerException(); 

 // Makes sure the key is not already in the hashtable. 

 HashtableEntry ?,? tab[] = table; 

 int hash = key.hashCode(); 

 // 直接hash求余 得到hash桶位置 

 int index = (hash 0x7FFFFFFF) % tab.length; 

 @SuppressWarnings("unchecked") 

 HashtableEntry K,V entry = (HashtableEntry K,V )tab[index]; 

 // 遍历hash桶 

 for(; entry != null ; entry = entry.next) {

 // 找到对应key的节点 

 if ((entry.hash == hash) entry.key.equals(key)) {

 V old = entry.value; 

 entry.value = value; 

 return old; 

 // 没有存在key，增加节点到一个新的hash桶 

 addEntry(hash, key, value, index); 

 return null; 

 // 没有存在key，增加节点到一个新的hash桶 

 private void addEntry(int hash, K key, V value, int index) {

 modCount++; // 操作数 + 1 

 HashtableEntry ?,? tab[] = table; 

 if (count = threshold) {

 // 大于等于扩容临界值 

 // Rehash the table if the threshold is exceeded 

 rehash();// 需要扩容 

 tab = table; 

 hash = key.hashCode(); 

 // 同样 直接hash求余 得到hash桶位置 

 index = (hash 0x7FFFFFFF) % tab.length; 

 // Creates the new entry. 

 @SuppressWarnings("unchecked") 

 HashtableEntry K,V e = (HashtableEntry K,V ) tab[index]; 

 // 添加节点到一个新的桶中 

 tab[index] = new HashtableEntry (hash, key, value, e); 

 count++; 

remove
移除节点

 public synchronized V remove(Object key) {

 HashtableEntry ?,? tab[] = table; 

 int hash = key.hashCode(); 

 // 同样 直接hash求余 得到hash桶位置 

 int index = (hash 0x7FFFFFFF) % tab.length; 

 @SuppressWarnings("unchecked") 

 HashtableEntry K,V e = (HashtableEntry K,V )tab[index]; 

 // 遍历hash桶内的链表 

 for(HashtableEntry 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; 

hashTable的扩容

 protected void rehash() {

 int oldCapacity = table.length; 

 HashtableEntry ?,? [] oldMap = table; 

 //新容量 = 旧容量 × 2 +1 

 int newCapacity = (oldCapacity 1) + 1; 

 // 容量超过最大值 

 if (newCapacity - MAX_ARRAY_SIZE 0) {

 if (oldCapacity == MAX_ARRAY_SIZE) 

 // Keep running with MAX_ARRAY_SIZE buckets 

 return; 

 newCapacity = MAX_ARRAY_SIZE; 

 HashtableEntry ?,? [] newMap = new HashtableEntry ?,? [newCapacity]; 

 modCount++;// 操作数 +1 

 // 这里是符合预期的，threhold = initialCapacity * loadFactor 

 threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1); 

 table = newMap; 

 // 迁移所有旧的节点到新的hash桶中 

 for (int i = oldCapacity ; i-- 0 ;) {

 for (HashtableEntry K,V old = (HashtableEntry K,V )oldMap[i] ; old != null ; ) {

 // 遍历每个节点 

 HashtableEntry K,V e = old; 

 old = old.next; 

 // 计算出新的位置，插入到桶的首个节点 

 int index = (e.hash 0x7FFFFFFF) % newCapacity; 

 e.next = (HashtableEntry K,V )newMap[index]; 

 newMap[index] = e; 

扩容：
容量增加为原来2倍+1; 将每个结点重新hash迁移到对应的新的hash桶中
这里的增加节点跟HashMap的链表有点不一样，hashTable是直接插入到链表的头部，hashMap是在尾部。

原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/19399.html