一文带你深入理解Hashtable( 二 ) _Hashtable

tab[] = table;// 得到key的哈希值int hash = key.hashCode();// 得到该key存在到数组中的下标int index = (hash & 0x7FFFFFFF) % tab.length;@SuppressWarnings("unchecked")// 得到该下标对应的EntryEntry entry = (Entry)tab[index];// 如果该下标的Entry不为null，则进行链表遍历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相等的节点，则执行插入操作addEntry(hash, key, value, index);return null;}private void addEntry(int hash, K key, V value, int index) {// 修改次数+1modCount++;Entry tab[] = table;// 判断是否需要扩容if (count >= threshold) {// 如果count大于等于扩容阈值，则进行扩容rehash();tab = table;// 扩容后，重新计算该key在扩容后table里的下标hash = key.hashCode();index = (hash & 0x7FFFFFFF) % tab.length;}// Creates the new entry.@SuppressWarnings("unchecked")// 采用头插的方式插入，index位置的节点为新节点的next节点// 新节点取代inde位置节点Entry e = (Entry) tab[index];tab[index] = new Entry<>(hash, key, value, e);// count+1count++;}扩容rehash源码如下：
protected void rehash() {// 暂存旧的table和容量int oldCapacity = table.length;Entry<?,?>[] oldMap = table;// 新容量为旧容量的2n+1倍int newCapacity = (oldCapacity << 1) + 1;// 判断新容量是否超过最大容量if (newCapacity - MAX_ARRAY_SIZE > 0) {// 如果旧容量已经是最大容量大话，就不扩容了if (oldCapacity == MAX_ARRAY_SIZE)// Keep running with MAX_ARRAY_SIZE bucketsreturn;// 新容量最大值只能是MAX_ARRAY_SIZEnewCapacity = MAX_ARRAY_SIZE;}// 用新容量创建一个新Entry数组Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];// 模数+1modCount++;// 重新计算下次扩容阈值threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);// 将新Entry数组赋值给tabletable = newMap;// 遍历数组和链表，进行新table赋值操作for (int i = oldCapacity ; i-- > 0 ;) {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;}}}

rehash()方法中我们可以看到容量扩大两倍+1，同时需要将原来HashTable中的元素，重新计算索引位置一一复制到新的Hashtable中，这个过程是比较消耗时间的。
Hashtable的索引求值公式是： hash&0x7FFFFFFF%newCapacity 。hash&0x7FFFFFF是为了保证正数，因为hashCode的值有可能为负值。

get方法

public synchronized V get(Object key) {Entry<?,?> tab[] = table;int hash = key.hashCode();// 根据key哈希得到index，遍历链表取值int index = (hash & 0x7FFFFFFF) % tab.length;for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {if ((e.hash == hash) && e.key.equals(key)) {return (V)e.value;}}return null;}

remove方法

public synchronized V remove(Object key) {Entry<?,?> tab[] = table;int hash = key.hashCode();// 获取key对应的indexint index = (hash & 0x7FFFFFFF) % tab.length;@SuppressWarnings("unchecked")// 遍历链表，如果找到key相等的节点，则改变前继和后继节点的关系，并删除相应引用，让GC回收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 = https://www.isolves.com/it/cxkf/yy/JAVA/2022-09-16/e.value;e.value = null;return oldValue;}}return null;}

总结本文主要讲解了Hashtable的基本功能和源码解析，虽然Hashtable本身不常用了，但是它的直接子类Properties目前还在被大量使用当中，所以学习它还是有一定价值的。下面在总结下Hashtable和HashMap的区别：

线程是否安全：HashMap是线程不安全的，HashTable是线程安全的；HashTable内部的方法基本都经过 synchronized修饰; 如果想要线程安全的Map容器建议使用ConcurrentHashMap,性能更好。
对Null key 和Null value的支持：HashMap中，null可以作为键，这样的键只有一个，可以有一个或多个键所对应的值为null；HashTable中key和value都不能为null，否则抛出空指针异常；