你真的了解Hashtable吗？
我们知道Hashtable与HashMap 的区别主要是线程安全，那除了这个区别还有什么区别吗？接下来我们带着这个问题一起去探究一下。Hashtable 采用的是 数组+链表 形式存储数据，例如的：
Hashtable数据结构
Hashtable 是绝对线程安全，所以每个方法都会使用同步串，
put实现
/**
* Maps the specified <code>key</code> to the specified
* <code>value</code> in this hashtable. Neither the key nor the
* value can be <code>null</code>. <p>
*
* The value can be retrieved by calling the <code>get</code> method
* with a key that is equal to the original key.
*
* @param key the hashtable key
* @param value the value
* @return the previous value of the specified key in this hashtable,
* or <code>null</code> if it did not have one
* @exception NullPointerException if the key or value is
* <code>null</code>
* @see Object#equals(Object)
* @see #get(Object)
*/
public synchronized V put(K key, V value) {
// 进来的第一步是校验 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;
// 直接使用key.hashCode(),表明key 也不能为空，不然也会报NPE的
int hash = key.hashCode();
// 这里的index 算法是，hash --> 去除最高位，然后和长度取余
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;
}
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 值 和 index 位置
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++;
}
接下来我们来看一下get的实现
get
/**
* Returns the value to which the specified key is mapped,
* or {@code null} if this map contains no mapping for the key.
*
* <p>More formally, if this map contains a mapping from a key
* {@code k} to a value {@code v} such that {@code (key.equals(k))},
* then this method returns {@code v}; otherwise it returns
* {@code null}. (There can be at most one such mapping.)
*
* @param key the key whose associated value is to be returned
* @return the value to which the specified key is mapped, or
* {@code null} if this map contains no mapping for the key
* @throws NullPointerException if the specified key is null
* @see #put(Object, Object)
*/
@SuppressWarnings("unchecked")
public synchronized V get(Object key) {
Entry<?,?> tab[] = table;
int hash = key.hashCode();
// hash 去除最高位，对数组长度取余
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实现
/**
* Removes the key (and its corresponding value) from this
* hashtable. This method does nothing if the key is not in the hashtable.
*
* @param key the key that needs to be removed
* @return the value to which the key had been mapped in this hashtable,
* or <code>null</code> if the key did not have a mapping
* @throws NullPointerException if the key is <code>null</code>
*/
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++;
// 修改链式节点 next 指向删除数据
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
count--;
V oldValue = e.value;
e.value = null;
return oldValue;
}
}
return null;
}
再来看一下rehash的实现
rehash实现
/**
* Increases the capacity of and internally reorganizes this
* hashtable, in order to accommodate and access its entries more
* efficiently. This method is called automatically when the
* number of keys in the hashtable exceeds this hashtable's capacity
* and load factor.
*/
@SuppressWarnings("unchecked")
protected void rehash() {
int oldCapacity = table.length;
Entry<?,?>[] oldMap = table;
// overflow-conscious code
// 扩容算法：直接扩大2倍 + 1
int newCapacity = (oldCapacity << 1) + 1;
// 为了避免 oom 对超过最大值进行重新赋值
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (oldCapacity == MAX_ARRAY_SIZE)
// Keep running with MAX_ARRAY_SIZE buckets
return;
newCapacity = MAX_ARRAY_SIZE;
}
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
modCount++;
// 最大容量 为：（数组长度 * 扩容因子 ， 最大的数组长度 + 1 ）最小值
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
table = newMap;
for (int i = oldCapacity ; i-- > 0 ;) {
// 对 数组链表数据 进行重新 hash index 计算，rehash 之后 会使得 最早插入的数据 回到 链表的 第一位
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;
}
}
}
好了，就到这里了。
网友评论