JDK1.8 Hashtable详解
Hashtable 是一个散列表，它存储的内容是键值对(key-value)映射。
1 Hashtable类定义
public class Hashtable<K,V>extends Dictionary<K,V>implements Map<K,V>, Cloneable, java.io.Serializable {}//内部静态类Entry，Entry为存储的节点//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 Opspublic K getKey() {return key;}public V getValue() {return value;}public V setValue(V value) {if (value == null)throw new NullPointerException();V oldValue = this.value;this.value = value;return oldValue;}public boolean equals(Object o) {if (!(o instanceof Map.Entry))return false;Map.Entry<?,?> e = (Map.Entry<?,?>)o;return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&(value==null ? e.getValue()==null : value.equals(e.getValue()));}public int hashCode() {return hash ^ Objects.hashCode(value);}public String toString() {return key.toString()+"="+value.toString();}}
1）Hashtable继承于Dictionary抽象类，Dictionary中定义了对于容器操作的多种抽象方法。
2）实现Map接口，Hashtable实现了Map接口中定义的方法,具体的方法将在后文中分析。
3）实现Cloneable接口。
4）实现Serializable接口，可序列化。
2 属性值
Hashtable的属性值含义已在代码注释中说明
// 保存key-value的数组,支持泛型// Entry同样采用链表解决冲突，每一个Entry本质上是一个单向链表private transient Entry<?,?>[] table;// Entry中键值对的数量private transient int count;// 阈值，用于判断是否需要调整Entry的容量private int threshold;// 负载因子，当元素个数count大于总容量 * 负载因子时，扩容private float loadFactor;// Entry被改变的次数，用于fail-fast机制的实现private transient int modCount = 0;
3 构造方法
1）无参构造方法
//无参构造方法public Hashtable() {//默认容量大小为11，负载因子设置为0.75this(11, 0.75f);}
2）初始化容量大小为initialCapacity
//带有初始化容量大小的构造方法public Hashtable(int initialCapacity) {this(initialCapacity, 0.75f);}
3） 初始化容量为initialCapacity，负载因子为 loadFactor
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);//如果设置初始容量为0，则默认修改为1if (initialCapacity==0)initialCapacity = 1;//设置负载因子this.loadFactor = loadFactor;//根据设置的初始化容量创建数组table = new Entry<?,?>[initialCapacity];//计算阈值，取初始化容量与可分配的最大容量中的最小值。threshold = (int)Math.min(initialCapacity, MAX_ARRAY_SIZE + 1);}
4） 使用Map集合初始化
//使用Map集合初始化public Hashtable(Map<? extends K, ? extends V> t) {// 若集合t元素大于5，则初始化容量为集合t中元素数目的2倍// 否则初始化容量为11// 负载因子设置为0.75this(Math.max(2*t.size(), 11), 0.75f);//将集合t中元素全部存储putAll(t);}public synchronized void putAll(Map<? extends K, ? extends V> t) {// for循环遍历集合t，将t中元素存储到this集合中for (Map.Entry<? extends K, ? extends V> e : t.entrySet())//将键值对添加至集合中put(e.getKey(), e.getValue());}
4 核心方法
| 方法名 | 含义 | 时间复杂度 |
|---|---|---|
| get(Object key) | 根据key值获取元素 | O(1) |
| put(K key, V value) | 添加元素 | O(n) |
| putAll() | 添加集合中元素 | O(n) |
| contains(Object value) | 判断是否包含元素 | O(n) |
| containsValue(Object value) | 判断是否包含元素 | O(n) |
| containsKey(Object key) | 判断是否包含key | O(1) |
| replace(K key, V oldValue, V newValue) | 替换元素值 | O(1) |
| size() | 获取元素数目 | O(1) |
| isEmpty() | 判断集合是否为空 | O(1) |
| remove(Object key) | 根据键值删除元素 | O(n) |
| clear() | 清空集合 | O(n) |
5 get()方法
public synchronized V get(Object key) {Entry<?,?> tab[] = table;//得到key的hashcodeint hash = key.hashCode();//根据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;}}// 若没有找到，则返回nullreturn null;}
6 put()方法
public synchronized V put(K key, V value) {// 检验数据值的合法性if (value == null) {throw new NullPointerException();}Entry<?,?> tab[] = table;//根据键值获取索引indexint hash = key.hashCode();int index = (hash & 0x7FFFFFFF) % tab.length;//采用for循环方式解决哈希冲突，如果出现冲突则放在链表末尾。@SuppressWarnings("unchecked")Entry<K,V> entry = (Entry<K,V>)tab[index];for(; entry != null ; entry = entry.next) {//当前键值key已存在，更新key的映射值value，并返回旧值if ((entry.hash == hash) && entry.key.equals(key)) {V old = entry.value;entry.value = value;return old;}}//若没有找到重复键值key，则将key和value添加链表末尾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();//更新扩容后的数组信息tab = table;hash = key.hashCode();index = (hash & 0x7FFFFFFF) % tab.length;}// 没有超过阈值，则添加至数组中@SuppressWarnings("unchecked")Entry<K,V> e = (Entry<K,V>) tab[index];tab[index] = new Entry<>(hash, key, value, e);//增加元素数目count++;}//扩容方法protected void rehash() {//获取旧数组大小int oldCapacity = table.length;Entry<?,?>[] oldMap = table;// 创建新容量大小的Entry数组，数组容量大小为原数组的2倍+1int newCapacity = (oldCapacity << 1) + 1;if (newCapacity - MAX_ARRAY_SIZE > 0) {if (oldCapacity == MAX_ARRAY_SIZE)// Keep running with MAX_ARRAY_SIZE bucketsreturn;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;}}}
7 contains()方法
//判断是否含有valuepublic 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;}// 判断是否包含键值keypublic 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;}
8 replace()方法
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;}
9 remove()方法
//根据键值删除元素，返回被删除元素值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;}
10 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的tableEntry<?,?>[] 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 methodspublic 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;elseprev.next = e.next;count--;lastReturned = null;return;}}throw new ConcurrentModificationException();}}}
11 小结
Hashtable是一个散列表，它存储的内容是键值对(key-value)映射。Hashtable不允许null对象。Hashtable中的方法使用了synchronized关键字修饰，因此Hashtable是线程安全的。
曾经终败给现在
太过爱你忘了你带给我的痛
刺骨的言语ヽ痛彻心扉
向右看齐
朱雀
港控/mmm°
还没有评论，来说两句吧...