欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HashTable

程序员文章站 2022-05-12 10:57:26
...
[align=center][size=large]Hashtable[/size][/align]

一、对比HashMap

1.
[table]
|项目|HashMap|Hashtable|
|默认容量|16|11|
|负载因子|0.75|0.75|
|null值|允许key/value为空|不允许key/value为空(put操作时报空指针异常)|
|扩容|length*2|length*2+1|
|安全|线程不安全|线程安全|
|extends|AbstractMap|Dictionary|
|容量|>=1|2^n|
[/table]

2.负载因子
过低,空间利用率低,频繁的扩容
过高,寻址时间增加,key value 的多了;

3.快速失败
modCount

在遍历过程中,如果 modCount > expectedCount
throw new ConcurrentModificationException

二、类定义

1.源码

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


三、属性

1.源码

/**
* The hash table data.
*/
// Entry 的数组,Entry
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).)
*
* @serial
*/
// 临界值
private int threshold;

/**
* The load factor for the hashtable.
*
* @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 = 0;

/** use serialVersionUID from JDK 1.0.2 for interoperability */
private static final long serialVersionUID = 1421746759512286392L;



四、构造方法

1.

// 初始化容量,负载因子
public Hashtable(int initialCapacity, float loadFactor) {
// 初始化容量不能小于0
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
// 负载因子不能小于0且其是 float类型的数据
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal Load: "+loadFactor);

if (initialCapacity==0)
// 初始化容量 为任意数字 ,HashMap 要求必须为 2 的 N 次幂
initialCapacity = 1;
this.loadFactor = loadFactor;
table = new Entry[initialCapacity];
threshold = (int)(initialCapacity * loadFactor);
}


2.

// 默认负载因子 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
public Hashtable() {
this(11, 0.75f);
}



3.以存在的集合作为参数


/**
* 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).
*
* @param t the map whose mappings are to be placed in this map.
* @throws NullPointerException if the specified map is null.
* @since 1.2
*/
public Hashtable(Map<? extends K, ? extends V> t) {
// 调用构造方法,初始化容量为 已有集合中的key-value 对数量的 2 倍
this(Math.max(2*t.size(), 11), 0.75f);
putAll(t);
}

// 遍历已有集合,调用put方法,synchronized 关键字,线程安全
public synchronized void putAll(Map<? extends K, ? extends V> t) {
for (Map.Entry<? extends K, ? extends V> e : t.entrySet())
put(e.getKey(), e.getValue());
}



五、put()

1.源码


public synchronized V put(K key, V value) {
// Make sure the value is not null

// value 不允许为空,空指针异常
if (value == null) {
throw new NullPointerException();
}

// Makes sure the key is not already in the hashtable.
// 赋值
Entry tab[] = table;

// key 不能为空,否则获取 hashcode 时报空指针异常
// 一次hash,key本身的hash值
int hash = key.hashCode();
// 二次计算hash值,再与length 取余,确定存放在数组中的位置
int index = (hash & 0x7FFFFFFF) % tab.length;
// 取出index 位置的数据,遍历数组下的链表,判断此 key 是否已存在
// 若已存在,则替换已存在的value值,并返回旧的value值
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
V old = e.value;
e.value = value;
return old;
}
}
// 操作次数加 1
modCount++;
// Hashtable 中 Entry 的数量 count 是否大于临界值
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
// 扩容
rehash();

tab = table;
index = (hash & 0x7FFFFFFF) % tab.length;
}

// Creates the new entry.
// 将 tab[index] 位置的链表赋值给 e
Entry<K,V> e = tab[index];
// 新增Entry ,将原有的链表放在新加入的Entry 的next 中
// 即 新增的Entry 是放在链表的首位的
tab[index] = new Entry<K,V>(hash, key, value, e);
count++;
return null;
}

// Entry 的构造方法
protected Entry(int hash, K key, V value, Entry<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}

// 扩容
protected void rehash() {
// 扩容前的容量
int oldCapacity = table.length;
Entry[] oldMap = table;
// 扩容后的容量 length*2 + 1
int newCapacity = oldCapacity * 2 + 1;
Entry[] newMap = new Entry[newCapacity];
// 操作次数加1
modCount++;
threshold = (int)(newCapacity * loadFactor);
table = newMap;

// 两层循环,外层遍历原数组的总长度,将旧数组依次放入新的数组中
for (int i = oldCapacity ; i-- > 0 ;) {
// 获取旧数据中下标 i 处的链表
for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
// 获取链表当前位置的元素值
Entry<K,V> e = old;
// 指针下移
old = old.next;
// 计算存储位置
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
// 当前元素指向新的数组中 index 下标位置
e.next = newMap[index];
// 新数组的index 位置指向 e
newMap[index] = e;
}
// 遍历的结果是将链表中的元素倒置放入新的数组中
}
}



六、remove()
1.源码

public synchronized V remove(Object key) {
Entry tab[] = table;
int hash = key.hashCode();
// 定位存储位置
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index], prev = null ; e != null ; prev = e, e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
modCount++;
// 若链表中的元素数量 > 1 ,则将前一个Entry.next 指向 当前元素的next
if (prev != null) {
prev.next = e.next;
} else {
// 遍历条件
// Entry<K,V> e = tab[index], prev = null
// 下一次循环时,进行赋值 prev = e ;若 prev == null
// 说明链表中的第一个Entry 即为目标
tab[index] = e.next;
}
count--; // count表示存放的 Entry的数量
V oldValue = e.value;
e.value = null;
return oldValue;
}
}


七、get()

1.源码


public synchronized V get(Object key) {
Entry tab[] = table;
// key 不能为 null,此处报空指针
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return e.value;
}
}
return null;
}
相关标签: Hashtable