您现在的位置是:首页 > 文章详情

java源码-Hashtable

日期:2018-07-28点击:270

开篇

Hashtable作为jdk提供的最原始的key/value存储结构,属于线程安全系列的,所以这边顺便把这个类分析一下,基本上如果你看过了HashMap相关的数据结构,这个看起来就是小菜一碟了。


Hashtable类关系图

img_7b19cef5fb5af9e7d5ce4dda22945342.png
Hashtable类关系图


Hashtable源码分析

Hashtable类成员变量

Hashtable中核心的存储结构是table,table中存储的数据结构是Entry对象

public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, java.io.Serializable { // 实际key/value存储的table数组 private transient Entry<?,?>[] table; private transient int count; private int threshold; private float loadFactor; // modCount private transient int modCount = 0; 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; } } 


Hashtable的构造函数

Hashtable构造函数的核心内容就是初始化loadFactor、threshold等变量,以及根据initialCapacity初始化table对象。

 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) { this(initialCapacity, 0.75f); } public Hashtable() { this(11, 0.75f); } public Hashtable(Map<? extends K, ? extends V> t) { this(Math.max(2*t.size(), 11), 0.75f); putAll(t); } 


Hashtable的put操作

Hashtable的put()方法 采用synchronized方法修饰保证线程安全,put的执行过程就是根据key计算hash值,根据hash值找到table中对应的hash桶后采用倒链法保存节点。
在put过程中如果找到key对应的value,那么就覆盖value值并返回旧value值。

 public synchronized V put(K key, V 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; 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)) { 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 = 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++; } 


Hashtable的get操作

Hashtable的get()方法 用synchronized关键进行修饰保证线程安全,get的过程通过计算key的hash值找table中对应的hash桶,然后遍历hash桶下面的所有的对象链表,通过比较key的值查找对象。

 public synchronized V get(Object key) { Entry<?,?> tab[] = table; int hash = key.hashCode(); 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; } 


迭代器

Hashtable的迭代器其实核心在于getIterator()方法,该方法内部创建了Enumerator类对象,其中Enumerator类是核心的对象。
Enumerator的hasMoreElements()方法用于判断是否还有下一个变量,nextElement()方法用于返回当前变量的值并将entry指向下一个变量。
Hashtable的遍历是从数组的最后一个非空的元素开始遍历的,遍历完hash桶下的所有链表对象后再往前推进下一个hash桶。

 // Types of Enumerations/Iterations private static final int KEYS = 0; private static final int VALUES = 1; private static final int ENTRIES = 2; public Set<K> keySet() { if (keySet == null) keySet = Collections.synchronizedSet(new KeySet(), this); return keySet; } private class KeySet extends AbstractSet<K> { public Iterator<K> iterator() { return getIterator(KEYS); } } public Set<Map.Entry<K,V>> entrySet() { if (entrySet==null) entrySet = Collections.synchronizedSet(new EntrySet(), this); return entrySet; } private class EntrySet extends AbstractSet<Map.Entry<K,V>> { public Iterator<Map.Entry<K,V>> iterator() { return getIterator(ENTRIES); } } public Collection<V> values() { if (values==null) values = Collections.synchronizedCollection(new ValueCollection(), this); return values; } private class ValueCollection extends AbstractCollection<V> { public Iterator<V> iterator() { return getIterator(VALUES); } } private <T> Iterator<T> getIterator(int type) { if (count == 0) { return Collections.emptyIterator(); } else { return new Enumerator<>(type, true); } } private class Enumerator<T> implements Enumeration<T>, Iterator<T> { Entry<?,?>[] table = Hashtable.this.table; // index默认是table.length的长度 int index = table.length; Entry<?,?> entry; Entry<?,?> lastReturned; int type; boolean iterator; protected int expectedModCount = modCount; Enumerator(int type, boolean iterator) { this.type = type; this.iterator = iterator; } 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; } @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(); } } 
原文链接:https://yq.aliyun.com/articles/666347
关注公众号

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。

持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。

文章评论

共有0条评论来说两句吧...

文章二维码

扫描即可查看该文章

点击排行

推荐阅读

最新文章