JDK源码学习之HashTable(附带面试题)的学习笔记

其他好文&＃xff1a;

什么是 HashTable &＃xff1f;它的数据类型是什么&＃xff1f;和 HashMap 有什么关系&＃xff1f;又和 HashMap 有什么区别&＃xff1f;

老样子&＃xff0c;老铁们系好安全带&＃xff01;发车—&＃xff08;深入了解 HashTable &＃xff09;。

由于 HashTable 现在使用的并不多&＃xff0c;本文并没有长篇大论&＃xff0c;只有干货&＃xff01;&＃xff01;&＃xff01;

1、什么是HashTable&＃xff1f;

Hashtable 和 HashMap 一样是一个集合&＃xff0c;不过不同于 HashMap 的是&＃xff0c;HashMap 允许 null 键与 null 值&＃xff0c;而 Hashtable 不允许&＃xff0c;HashMap 是线程不安全的&＃xff0c;而Hashtable 是线程安全的&＃xff0c;由于线程安全性问题&＃xff0c;HashMap 相对于 Hashtable 效率会更高一些。

&＃x1f339; HashTable 的使用&＃xff1a;

Hashtable<Object, Object> hashtable &＃61; new Hashtable<>();


通过上述我们能知道 HashTable 是 KV 的数据结构。那接下来让我们看看其的底层源码吧。

源码&＃xff1a;

public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable {
...
}


继承图&＃xff1a;

在这里&＃xff0c;我们看到 Hashtable 继承自 Dictionary 这个字典类&＃xff0c;并实现了 Map、Cloneable和Serializable 接口&＃xff0c;具体的这些接口作用以及 Map 接口里的方法已在之前的 HashMap 解析中介绍过&＃xff0c;没看过的同学可以参考上面的推荐文章嗷。下面着重看下Dictionary这个抽象类中的方法。

Dictionary&＃xff1a;

public abstract
class Dictionary<K,V> {
/**
* 一个空的构造方法
*/
public Dictionary() {
}
/**
* 一个用于计算长度的抽象方法
*/
abstract public int size();
/**
* 一个用于判断是否为空的抽象方法
*/
abstract public boolean isEmpty();
/**
* 一个用于取出key的抽象方法&＃xff0c;取出类型为枚举
*/
abstract public Enumeration<K> keys();
/**
* 一个用于取出value的抽象方法&＃xff0c;取出类型为枚举
*/
abstract public Enumeration<V> elements();
/**
* 根据key值取出value
*/
abstract public V get(Object key);
/**
* 以key对应value的形式存放值
*/
abstract public V put(K key, V value);
/**
* 根据key值移除某个元素
*/
abstract public V remove(Object key);
}


我们可以通过看上面的注释和方法来理解这个 Dictionary 。因为其是 抽象类 除了构造函数都是抽象方法&＃xff0c;当 HashTable 继承 Dictionary 的时候则需要实现其的所有 抽象方法 。

2、HashTable中常用的变量、构造函数和方法

2.1 HashTalbe 中常用的变量

源码&＃xff1a;

/**
* The hash table data.
*/
private transient Entry<?,?>[] table;
/**
* The total number of entries in the hash table.
*/
private transient int count;
/**
* The table is rehashed when its size exceeds this threshold. (The
* value of this field is (int)(capacity * loadFactor).)
*
* &＃64;serial
*/
private int threshold;
/**
* The load factor for the hashtable.
*
* &＃64;serial
*/
private float loadFactor;
/**
* The number of times this Hashtable has been structurally modified
* Structural modifications are those that change the number of entries in
* the Hashtable or otherwise modify its internal structure (e.g.,
* rehash). This field is used to make iterators on Collection-views of
* the Hashtable fail-fast. (See ConcurrentModificationException).
*/
private transient int modCount &＃61; 0;
/** use serialVersionUID from JDK 1.0.2 for interoperability */
private static final long serialVersionUID &＃61; 1421746759512286392L;


• table &＃xff1a;存储数据的table数组。
• count &＃xff1a;Hashtable中元素的总数。
• threshold &＃xff1a;阈值。
• loadFactor &＃xff1a;加载因子。
• modCount &＃xff1a;修改次数。
• serialVersionUID &＃xff1a;版本ID号。

2.2 HashTable 中的构造函数

源码&＃xff1a;

/**
* Constructs a new, empty hashtable with the specified initial
* capacity and the specified load factor.
*
* &＃64;param initialCapacity the initial capacity of the hashtable.
* &＃64;param loadFactor the load factor of the hashtable.
* &＃64;exception IllegalArgumentException if the initial capacity is less
* than zero, or if the load factor is nonpositive.
*/
// inialCapacity 为初始值
public Hashtable(int initialCapacity, float loadFactor) {
// 判断是否小于零&＃xff0c;如果小于零则抛出 IllegalArgumentException 异常。
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "&＃43;
initialCapacity);
// 判断负载因子是否合法&＃xff0c;如果不合法则抛出异常
if (loadFactor <&＃61; 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal Load: "&＃43;loadFactor);
// 如果传入的初始值为0&＃xff0c;则自动设置为1
if (initialCapacity&＃61;&＃61;0)
initialCapacity &＃61; 1;
this.loadFactor &＃61; loadFactor;
table &＃61; new Entry<?,?>[initialCapacity];
// 设置阀值
threshold &＃61; (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE &＃43; 1);
}
/**
* Constructs a new, empty hashtable with the specified initial capacity
* and default load factor (0.75).
*
* &＃64;param initialCapacity the initial capacity of the hashtable.
* &＃64;exception IllegalArgumentException if the initial capacity is less
* than zero.
*/
// 定义初始值&＃xff0c;因子为0.75
public Hashtable(int initialCapacity) {
this(initialCapacity, 0.75f);
}
/**
* Constructs a new, empty hashtable with a default initial capacity (11)
* and load factor (0.75).
*/
// 设置初始容量为11&＃xff0c;负载因子为0.75
public Hashtable() {
this(11, 0.75f);
}
/**
* Constructs a new hashtable with the same mappings as the given
* Map. The hashtable is created with an initial capacity sufficient to
* hold the mappings in the given Map and a default load factor (0.75).
*
* &＃64;param t the map whose mappings are to be placed in this map.
* &＃64;throws NullPointerException if the specified map is null.
* &＃64;since 1.2
*/
public Hashtable(Map<? extends K, ? extends V> t) {
// 比较两倍的Map长度和11谁大&＃xff0c;不免不必要的空间浪费
this(Math.max(2*t.size(), 11), 0.75f);
putAll(t);
}


通过源码我们能知道 HashTable 有四种构造函数&＃xff1a;

• Hashtable()
• Hashtable(Map t)
• Hashtable(int initialCapacity)
• public Hashtable(int initialCapacity, float loadFactor)

2.3 HashTable 中常用的方法

♣️ 2.3.1 方法

源码&＃xff1a;

// 加锁
public synchronized V put(K key, V value) {
// Make sure the value is not null
// 如果value为null&＃xff0c;则抛出 NullPointerException 异常
if (value &＃61;&＃61; null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] &＃61; table;
// 这里注意如果key空则也会抛出异常
int hash &＃61; key.hashCode();
// 寻址法来进行寻找地址
int index &＃61; (hash & 0x7FFFFFFF) % tab.length;
&＃64;SuppressWarnings("unchecked")
Entry<K,V> entry &＃61; (Entry<K,V>)tab[index];
// 遍历table[index]所连接的链表&＃xff0c;查找是否已经存在key与需要插入的key值相同的节点&＃xff0c;如果存在则直接更新value&＃xff0c;并返回旧的value。
for(; entry !&＃61; null ; entry &＃61; entry.next) {
if ((entry.hash &＃61;&＃61; hash) && entry.key.equals(key)) {
V old &＃61; entry.value;
entry.value &＃61; value;
return old;
}
}
// 如果table[index]所连接的链表上不存在相同的key,则通过addEntry()方法将新节点加载链表的开头。
addEntry(hash, key, value, index);
return null;
}


通过上述代码我们能知道 HashTable 有一下几个特点&＃xff1a;

• 因为加了 synchronized &＃xff0c;所以是线程安全的&＃xff0c;但是效率是比较低的。
• 源码中首先判断了 value 是否为 null 是否为空&＃xff0c;如果为空则就抛出 NullPointerException 异常。同时也使用了 key.hashCode() &＃xff0c;如果 key 为 null 的时候则也会抛出异常。这就是为什么HashTable中KV不能为null的原因。
• 在使用 put() 方法时&＃xff0c;首先会先循环判断是否已经存在 key &＃xff0c;如果存在则直接替换&＃xff0c;反之添加。

补充 addEntry 方法

private void addEntry(int hash, K key, V value, int index) {
modCount&＃43;&＃43;; // 操作次数加一
Entry<?,?> tab[] &＃61; table;
// 首先判断容量是否充足&＃xff0c;如果不充足则扩容
if (count >&＃61; threshold) {
// Rehash the table if the threshold is exceeded
rehash();
tab &＃61; table;
hash &＃61; key.hashCode();
index &＃61; (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
&＃64;SuppressWarnings("unchecked")
// 创建新的entry
Entry<K,V> e &＃61; (Entry<K,V>) tab[index];
// 放入数组中
tab[index] &＃61; new Entry<>(hash, key, value, e);
// hashtable长度加1
count&＃43;&＃43;;
}


♣️ 2.3.2 rehash 方法

此放在也在上面的 addEntry 中使用过&＃xff0c;用于扩容。就让我们深入的看看它的具体实现方式吧。

源码&＃xff1a;

protected void rehash() {
// 获取旧的容量
int oldCapacity &＃61; table.length;
Entry<?,?>[] oldMap &＃61; table;
// overflow-conscious code
// 扩容&＃xff0c;长度为两倍加1
int newCapacity &＃61; (oldCapacity << 1) &＃43; 1;
//判断新容量是否超出的最大值&＃xff0c;如超出了更改为最大值
if (newCapacity - MAX_ARRAY_SIZE > 0) {
// 判断原来的容量是否就是最大值&＃xff0c;如果是的就直接返回
if (oldCapacity &＃61;&＃61; MAX_ARRAY_SIZE)
// Keep running with MAX_ARRAY_SIZE buckets
return;
newCapacity &＃61; MAX_ARRAY_SIZE;
}
// 创建新的entry数组
Entry<?,?>[] newMap &＃61; new Entry<?,?>[newCapacity];

// 操作数加1
modCount&＃43;&＃43;;
// 计算阀值
threshold &＃61; (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE &＃43; 1);
// 把新的entry赋值给table
table &＃61; newMap;
// //循环遍历旧的元素并重新hash
for (int i &＃61; oldCapacity ; i-- > 0 ;) {
for (Entry<K,V> old &＃61; (Entry<K,V>)oldMap[i] ; old !&＃61; null ; ) {
Entry<K,V> e &＃61; old;
old &＃61; old.next;
int index &＃61; (e.hash & 0x7FFFFFFF) % newCapacity;
e.next &＃61; (Entry<K,V>)newMap[index];
newMap[index] &＃61; e;
}
}
}


具体流程已经在上方的注释中写过了&＃xff0c;这里就不再具体赘述了。

♣️ 2.2.3 get 方法

源码&＃xff1a;

// 加synchronized锁访问
public synchronized V get(Object key) {
Entry<?,?> tab[] &＃61; table;
// 哈希 key 的值
int hash &＃61; key.hashCode();
// 重新获取下标加索引
int index &＃61; (hash & 0x7FFFFFFF) % tab.length;
// 循环遍历
for (Entry<?,?> e &＃61; tab[index] ; e !&＃61; null ; e &＃61; e.next) {
// 判断 hash值equals是否相等
if ((e.hash &＃61;&＃61; hash) && e.key.equals(key)) {
return (V)e.value;
}
}
return null;
}


♣️ 2.2.4 remove 方法

源码&＃xff1a;

public synchronized V remove(Object key) { // 加锁&＃xff0c;即线程安全
Entry<?,?> tab[] &＃61; table;
// 获取hash值
int hash &＃61; key.hashCode();
// 查找下标值
int index &＃61; (hash & 0x7FFFFFFF) % tab.length;
&＃64;SuppressWarnings("unchecked")
Entry<K,V> e &＃61; (Entry<K,V>)tab[index];
// 循环遍历
for(Entry<K,V> prev &＃61; null ; e !&＃61; null ; prev &＃61; e, e &＃61; e.next) {
// 判断是否存在key
if ((e.hash &＃61;&＃61; hash) && e.key.equals(key)) {
// 操作数加一
modCount&＃43;&＃43;;
// 进行链表删除操作
if (prev !&＃61; null) {
prev.next &＃61; e.next;
} else {
tab[index] &＃61; e.next;
}
// 总长度减1
count--;
V oldValue &＃61; e.value;
e.value &＃61; null;
return oldValue;
}
}
return null;
}


3、HashTable常见面试题

1、HashTable 中的默认值是多少?

2、HashTable 的底层数据结构是什么&＃xff1f;

3、HashTable是否是线程安全的&＃xff1f;

4、HashTable 每次扩容的容量是多大&＃xff1f;

5、HashTable又和HashMap有什么区别呢&＃xff1f;

参考答案地址&＃xff1a; 地址