文章可以白嫖，老铁们顺便关注一下我的公众号，手动滑稽🤣🤣
欢迎大家关注：武哥聊编程、Java开发宝典、Java秃头哥，您的支持，是我创作的持续动力！
Hashtable 是一个散列表，它存储的内容是 键值对(key-value)映射。
# hashtable 声明
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable {
......
}
- Hashtable继承于Dictionary抽象类，Dictionary中定义了对于容器操作的多种抽象方法。
- 实现Map接口，Hashtable实现了Map接口中定义的方法。
- 实现Cloneable接口。
- 实现Serializable接口，可序列化。
/**
* 键值对/Entry数组，每个Entry本质上是一个单向链表的表头
*/
private transient Entry<?,?>[] table;
/**
* 1. 内部静态类Entry，Entry为存储的节点
* 2. Entry本质为链表
*/
private static class Entry<K,V> implements Map.Entry<K,V> {
// 哈希值
final int hash;
// 键
final K key;
// 值
V value;
// 指向下一个节点
Entry<K,V> next;
// 构造方法
protected Entry(int hash, K key, V value, Entry<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
// 克隆操作
@SuppressWarnings("unchecked")
protected Object clone() {
return new Entry<>(hash, key, value,
(next==null ? null : (Entry<K,V>) next.clone()));
}
// Map.Entry Ops
// 获取 key
public K getKey() {
return key;
}
// 获取 value
public V getValue() {
return value;
}
// 设置 value
public V setValue(V value) {
if (value == null) /** 由此可知，hashtable value不可能为null **/
throw new NullPointerException();
V oldValue = this.value;
this.value = value;
return oldValue;
}
// 判断两个 Entry是否相等
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
/** 由此可知，key与value都相等才算相等 **/
return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
(value==null ? e.getValue()==null : value.equals(e.getValue()));
}
// 计算 hashcode
public int hashCode() {
return hash ^ Objects.hashCode(value);
}
// 重写 toString 方法
public String toString() {
return key.toString()+"="+value.toString();
}
}
由上可知
- HashTable 就是
一个存储Entry的数组 - Entry中包含
存储的键值对以及下一个节点 - Entry中
value是不可为空的
- 成员属性
/**
* 1. 保存 k-v 的数组,支持泛型
* 2. Entry 采用链表解决冲突，本质上是一个单向链表
*/
private transient Entry<?,?>[] table;
/**
* Entry中键值对的数量
*/
private transient int count;
/**
* 阈值，用于判断是否需要调整 Entry 的容量（threshold = 容量*加载因子）
*/
private int threshold;
/**
* 负载因子，当元素个数 count 大于总容量 * 负载因子时，扩容
*/
private float loadFactor;
/**
* Entry 被改变的次数，用于fail-fast机制的实现
*/
private transient int modCount = 0;
- 构造方法
/**
* 带有初始化容量大小和负载因子的构造方法.
*/
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);
}
/**
* 带有初始化容量大小的构造方法
*/
public Hashtable(int initialCapacity) {
// 注意：默认负载因子设置为 0.75
this(initialCapacity, 0.75f);
}
/**
* 默认无参构造方法
*/
public Hashtable() {
// 默认容量大小为 11，负载因子设置为 0.75
this(11, 0.75f);
}
/**
* 使用Map集合初始化构造方法
*/
public Hashtable(Map<? extends K, ? extends V> t) {
// 若集合t元素大于 5，则初始化容量为集合 t 中元素数目的 2倍，否则初始化容量为 11
// 负载因子设置为 0.75
this(Math.max(2*t.size(), 11), 0.75f);
//将集合t中元素全部存储
putAll(t);
}
由此可知，我们不指定数组容量和加载因子，HashTable 默认初始化容量为 11，默认负载因子为 0.75（与HashMap是相同的）。
- 存取方法
- put 方法
/**
* put 操作
*/
public synchronized V put(K key, V value) {
// 检验数据值的合法性,确保 value值不能为空
if (value == null) {
throw new NullPointerException();
}
Entry<?,?> tab[] = table;
// 根据键值获取索引index
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)) { // 若 key已存在
V old = entry.value;
// 则覆盖掉原来的值
entry.value = value;
return old; // 并返回原来的值
}
}
// 若 key不存在，则将 key 和 value 添加链表末尾
addEntry(hash, key, value, index);
return null;
}
/**
* 增加 entry
*/
private void addEntry(int hash, K key, V value, int index) {
modCount++;
Entry<?,?> tab[] = table;
// 判断当前数目是否超过阈值
if (count >= threshold) {
// 超过阈值进行扩容
rehash();
// 更新扩容后的数组信息
tab = table;
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;
}
// 没有超过阈值，则新增 entry 添加到数组中
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>) tab[index];
tab[index] = new Entry<>(hash, key, value, e);
// 同时元素总数量得加 1
count++;
}
/**
* 扩容
*/
protected void rehash() {
// 获取旧数组大小
int oldCapacity = table.length;
Entry<?,?>[] oldMap = table;
// 创建新容量大小的 Entry 数组，数组容量大小为原数组的 2 倍 + 1
int newCapacity = (oldCapacity << 1) + 1;
// 不能超出最大值
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (oldCapacity == MAX_ARRAY_SIZE)
return;
newCapacity = MAX_ARRAY_SIZE;
}
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
modCount++;
// 重新计算阈值
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
table = newMap;
// 将原数组中元素拷贝至新数组
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;
}
}
}
- get 方法
/**
* 获取 value
*/
public synchronized V get(Object key) {
Entry<?,?> tab[] = table;
// 获取 key的哈希值
int hash = key.hashCode();
// 根据哈希值计算索引值
int index = (hash & 0x7FFFFFFF) % tab.length;
// 根据index找到key对应Entry链表，遍历链表找到哈希值与键值均与key相同的元素
for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return (V)e.value;
}
}
// 找不到，则返回null
return null;
}
- 其他常用方法
/** -----------包含相关方法----------- */
// 判断是否含有 value
public boolean containsValue(Object value) {
return contains(value);
}
public synchronized boolean contains(Object value) {
// 检查参数的合法性
if (value == null) {
throw new NullPointerException();
}
// 双重for循环，外循环遍历数组，内循环遍历链表
Entry<?,?> tab[] = table;
for (int i = tab.length ; i-- > 0 ;) {
for (Entry<?,?> e = tab[i] ; e != null ; e = e.next) {
if (e.value.equals(value)) {
return true;
}
}
}
return false;
}
// 判断是否包含键值 key
public synchronized boolean containsKey(Object key) {
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
// index定位数组位置，for遍历链表查找元素
for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return true;
}
}
return false;
}
/** -----------替换方法----------- */
// 替换指定 key 的值
public synchronized V replace(K key, V value) {
Objects.requireNonNull(value);
// 根据键值查找元素
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 (; e != null; e = e.next) {
// 查找成功，替换元素值
if ((e.hash == hash) && e.key.equals(key)) {
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
return null;
}
/** -----------移除方法----------- */
// 根据键值删除元素，返回被删除元素值
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遍历链表查找元素
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 = e.value;
// 清空值
e.value = null;
// 返回值
return oldValue;
}
}
return null;
}
/** -----------elements()方法----------- */
public synchronized Enumeration<V> elements() {
return this.<V>getEnumeration(VALUES);
}
// 获取Hashtable的枚举类对象
// 若Hashtable的实际大小为0,则返回“空枚举类”对象；
// 否则，返回正常的Enumerator的对象。
private <T> Enumeration<T> getEnumeration(int type) {
if (count == 0) {
return Collections.emptyEnumeration();
} else {
return new Enumerator<>(type, false);
}
}
// 获取Hashtable的迭代器
// 若Hashtable的实际大小为0,则返回“空迭代器”对象；
// 否则，返回正常的Enumerator的对象。(Enumerator实现了迭代器和枚举两个接口)
private <T> Iterator<T> getIterator(int type) {
if (count == 0) {
return Collections.emptyIterator();
} else {
return new Enumerator<>(type, true);
}
}
// Enumerator的作用是提供了“通过elements()遍历Hashtable的接口” 和 “通过entrySet()遍历Hashtable的接口”。
private class Enumerator<T> implements Enumeration<T>, Iterator<T> {
// 指向Hashtable的table
Entry<?,?>[] table = Hashtable.this.table;
// Hashtable的总的大小
int index = table.length;
Entry<?,?> entry;
Entry<?,?> lastReturned;
int type;
// Enumerator是 “迭代器(Iterator)” 还是 “枚举类(Enumeration)”的标志
// iterator为true，表示它是迭代器；否则，是枚举类。
boolean iterator;
// 在将Enumerator当作迭代器使用时会用到，用来实现fail-fast机制
protected int expectedModCount = modCount;
Enumerator(int type, boolean iterator) {
this.type = type;
this.iterator = iterator;
}
// 从遍历table的数组的末尾向前查找，直到找到不为null的Entry。
public boolean hasMoreElements() {
Entry<?,?> e = entry;
int i = index;
Entry<?,?>[] t = table;
/* Use locals for faster loop iteration */
while (e == null && i > 0) {
e = t[--i];
}
entry = e;
index = i;
return e != null;
}
// 获取下一个元素
// 注意：从hasMoreElements() 和nextElement() 可以看出“Hashtable的elements()遍历方式”
// 首先，<span style="color:#ff0000;">从后向前的遍历table数组</span>。table数组的每个节点都是一个单向链表(Entry)。
// 然后，依次向后遍历单向链表Entry。
@SuppressWarnings("unchecked")
public T nextElement() {
Entry<?,?> et = entry;
int i = index;
Entry<?,?>[] t = table;
/* Use locals for faster loop iteration */
while (et == null && i > 0) {
et = t[--i];
}
entry = et;
index = i;
if (et != null) {
Entry<?,?> e = lastReturned = entry;
entry = e.next;
return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e);
}
throw new NoSuchElementException("Hashtable Enumerator");
}
// Iterator methods
public boolean hasNext() {
return hasMoreElements();
}
public T next() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
return nextElement();
}
public void remove() {
if (!iterator)
throw new UnsupportedOperationException();
if (lastReturned == null)
throw new IllegalStateException("Hashtable Enumerator");
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
synchronized(Hashtable.this) {
Entry<?,?>[] tab = Hashtable.this.table;
int index = (lastReturned.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 == lastReturned) {
modCount++;
expectedModCount++;
if (prev == null)
tab[index] = e.next;
else
prev.next = e.next;
count--;
lastReturned = null;
return;
}
}
throw new ConcurrentModificationException();
}
}
}
Hashtable 中的方法使用了 synchronized 关键字修饰，因此 Hashtable是线程安全的。
- 遍历方式
Hashtable的遍历方式比较简单，一般分两步：
1. 获得 Entry 或 key 或 value 的集合；
2. 通过 Iterator 迭代器或者 Enumeration 遍历此集合
- 遍历 HashTable 的 Entry （效率高）
Object key = null;
Object value = null;
HashTable table = new HashTable();
Iterator iterator = table.entrySet().iterator();
while(iterator.hasNext()) {
Map.Entry entry = (Map.Entry)iterator.next();
// 获取key
key = entry.getKey();
// 获取value
value = entry.getValue();
}
- 遍历 HashTable 的 key
Object key = null;
Object value = null;
HashTable table = new HashTable();
Iterator iterator = table.keySet().iterator();
while (iterator.hasNext()) {
// 获取key
key = iterator.next();
// 根据key，获取value
value = table.get(key);
}
- 遍历 HashTable 的 value
Object value = null;
HashTable table = new HashTable();
Collection c = table.values();
Iterator iterator= c.iterator();
while (iterator.hasNext()) {
value = iterator.next();
}
- 通过 Enumeration 遍历 HashTable 的 key（效率高）
HashTable table = new HashTable();
Enumeration enumeration = table.keys();
while(enumeration.hasMoreElements()) {
System.out.println(enumeration.nextElement());
}
- 通过 Enumeration 遍历 HashTable 的 value （效率高）
HashTable table = new HashTable();
Enumeration enumeration = table.elements();
while(enumeration.hasMoreElements()) {
System.out.println(enumeration.nextElement());
}
综上所述，Hashtable是一个 散列表，它存储的内容是 键值对(k-v)映射。Hashtable 不允许null对象 且 Hashtable是线程安全的。关于它的介绍就告一段落，希望对大家有所帮助！！！
文章可以白嫖，老铁们顺便关注一下我的公众号，手动滑稽🤣🤣
欢迎大家关注：武哥聊编程、Java开发宝典、Java秃头哥，您的支持，是我创作的持续动力！