Detailed explanation of hashtable in Java
an introduction to
Hashtable is a legacy class. The common functions of many mappings are similar to HashMap. The difference is that it inherits from the dictionary class and is thread safe. The concurrency is not as good as concurrenthashmap because concurrenthashmap introduces segmentation lock.
Hashtable is not recommended to be used in new code. It can be replaced with HashMap when thread safety is not required, and with concurrenthashmap when thread safety is required.
Compare the initial capacity of HashMap
Default 11 initial capacity
It should be noted that the default initial capacity of hashtable is 11, while that of HashMap is 16, but their load factor is 0.75f
/**
* Constructs a new,empty hashtable with a default initial capacity (11)
* and load factor (0.75).
*/
public Hashtable() {
this(11,0.75f);
}
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
Specify any nonnegative capacity
Another point is that the initial capacity of hashtable can be any non negative integer you specify, that is, you can set it to 0
public Hashtable(int initialCapacity) {
this(initialCapacity,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 Entry<?,?>[initialCapacity];
threshold = (int)Math.min(initialCapacity * loadFactor,MAX_ARRAY_SIZE + 1);
}
However, if you look at the initial capacity of HashMap, it is not so obedient. By default, when we set the initialization capacity of HashMap, in fact, HashMap will use the first power greater than 2 of this value as the initialization capacity (except 0 and 1)
public HashMap(int initialCapacity,float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
Compare HashMap's support for null values
Hashtable key value does not support null
First of all, HashMap supports null values as keys and values, but hashtable does not support, neither key nor value
public synchronized V put(K key,V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash,key,value,index);
return null;
}
Smart, did you find it? If the above value detects value = = null, NPE will be thrown, but key is not said, because if the key is null, key Hashcode () will throw an exception. There is no need to judge, but value will not be thrown
However, it should be noted that although the real HashMap supports null values, it can be seen from the calculation method of hash values that the key value pairs of < null, value > will be overwritten by value.
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
Upgrade hashtable to support null as value
Most of the code is the hashtable of direct copy, and only the null value detection of value is removed
public class BuerHashTable<K,V> extends Hashtable<K,V> {
// ..... 省略了部分代码，直接copy HashTable 的即可，主要是BuerHashTable.Entry 的定义和构造方法
public synchronized V put(K key,V value) {
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash,index);
return null;
}
private void addEntry(int hash,K key,V value,int index) {
modCount++;
BuerHashTable.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")
BuerHashTable.Entry<K,V> e = (BuerHashTable.Entry<K,V>) tab[index];
tab[index] = new BuerHashTable.Entry<>(hash,e);
count++;
}
}
Next, you can store the null value as value in buerhashtable
BuerHashTable<String,String> buerHashTable = new BuerHashTable<>();
buerHashTable.put("a",null);
Compare the inheritance relationship of hashtable
Dictionary
This class is inherited by hashtable and HashMap does not inherit, but this abstract class is of little significance because its methods are in the map interface. In fact, this is a historical problem, because the map interface is in Java 1 2, and the dictionary abstract class is in Java 1 It exists in 0
public abstract
class Dictionary<K,V> {
public Dictionary() {
}
abstract public int size();
abstract public boolean isEmpty();
abstract public Enumeration<K> keys();
abstract public Enumeration<V> elements();
abstract public V get(Object key);
/**
* @exception NullPointerException if the <code>key</code> or
*/
abstract public V put(K key,V value);
abstract public V remove(Object key);
}
The NullPointerException in this place corresponds to the null value detection in the put method in hashtable
The last point is the annotation on the abstract dictionary class. The new implementation should implement the map interface instead of the abstract class
NOTE: This class is obsolete. New implementations should implement the Map interface,rather than extending this class
In fact, HashMap more accurately inherits from the abstractmap class rather than directly implements the map interface. Therefore, if the abstract class dictionary implements the real map interface, the inheritance relationship between HashMap and hashtable will be consistent
Hashtable
Thread safety
In fact, hashtable doesn't have so much to say. The more important thing is thread safety, but the implementation method of thread safety is to add the synchronized keyword to all operations, ha ha! We'll talk about synchronized later
public synchronized int size() {}
public synchronized boolean isEmpty() {}
public synchronized boolean contains(Object value) {}
public synchronized boolean containsKey(Object key) {}
public synchronized V get(Object key) {}
public synchronized V put(K key,V value) {}
public synchronized V remove(Object key) {}
HashMap is thread unsafe
Contains method
There is no contains method in hashtable in HashMap, only containsvalue and containskey, because the contains method is easy to be misunderstood.
Hashtable retains three methods: contains, containsvalue and containskey. The functions of contains and containsvalue are the same.
Debug source code put method
public synchronized V put(K key,V value) {
// Make sure the value is not null 确保value 不是null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
// 这里的英文注释很有意思啊，就是告诉你确保key 不存在，存在咋地，覆盖又咋地
Entry<?,?> tab[] = table;
// 哈希值的计算不同，HashTable直接使用对象的hashCode。而HashMap重新计算hash值(高16位异或低16位)
int hash = key.hashCode();
// 计算下标 HashMap 是计算key的hash再与tab.length-1进行与运算；
// HashTable则是key的hash值与0x7FFFFFFF进行与运算，然后再对tab.length取模
// 先hash&0x7FFFFFFF后，再对length取模，与0x7FFFFFFF的目的是为了将负的hash值转化为正值，因为hash值有可能为负数，而&0x7FFFFFFF后，只有符号外改变，而后面的位都不变
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
// 确定 index 位置上的链表头，这里主要是遍历链表找到key 值相等的节点，然后返回old value，这样的话就不用添加新值
// 也就是不用调用addEntry 方法
Entry<K,V>)tab[index];
// 存在key
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
// 链表中不存在，则添加新值
addEntry(hash,index);
// 返回null
return null;
}
private void addEntry(int hash,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];
// e 也就是 tab[index] 是这个链表的头结点， tab[index] = new Entry<>(hash,e); 也就是将元素添加到链表的头部，e 做为new Entry<>(hash,e)的next 节点
tab[index] = new Entry<>(hash,e);
count++;
}
Here we compare the addition methods of HashMap. It is obvious that others add the tail of the linked list, because hashtable is thread safe. On this premise, the performance of using the header query method is better. Otherwise, there is the insertion of traversing to the tail of the linked list
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash,null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab,hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
Finally, let's look at the expansion method
@SuppressWarnings("unchecked")
protected void rehash() {
int oldCapacity = table.length;
Entry<?,?>[] oldMap = table;
// overflow-conscIoUs code
// 扩容成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;
// 最大容量 MAX_ARRAY_SIZE
newCapacity = MAX_ARRAY_SIZE;
}
// 创建新的数组
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
modCount++;
// 更新 threshold
threshold = (int)Math.min(newCapacity * loadFactor,MAX_ARRAY_SIZE + 1);
table = newMap;
// 数据迁移，遍历数组
for (int i = oldCapacity ; i-- > 0 ;) {
// for 循环的方式遍历链表
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;
}
}
}