@kiraSally
2018-03-12T18:29:13.000000Z
字数 5211
阅读 2221
JAVA
COLLECTIONS
源码
1.7版本
- 笔者个人博客 kiraSally的掘金个人博客 感谢支持
HashMap
,线程安全推荐使用ConcurrentHashMap
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable
//The hash table data.
//底层维护一个Entry(键值对)数组
private transient Entry<K,V>[] table;
//The total number of entries in the hash table.
//元素总量,等同于HashMap的size
private transient int count;
//The load factor for the hashtable.
//负载因子
private float loadFactor;
/**
* The table is rehashed when its size exceeds this threshold.
* (The value of this field is (int)(capacity * loadFactor).)
* 超过阈值进行rehash
*/
private int threshold;
/**
* 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).
* 结构性变动时modCount计数+1,用于遍历时的fail-fast机制生效
*/
private transient int modCount = 0;
/**
* initialCapacity 默认11
* loadFactor 默认 0.75
*/
public Hashtable() {
this(11, 0.75f);
}
/**
* 跟JDK1.7的HashMap基本一致
* @param initialCapacity 容量默认11
* @param loadFactor 负载因子默认0.75
*/
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);
//区别在于没有强制令cap为2次幂,当initCap=0时,默认为1
if (initialCapacity==0)
initialCapacity = 1;
this.loadFactor = loadFactor;
table = new Entry[initialCapacity];
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
//useAltHashing为boolean,其如果为真,则执行另一散列的字符串键,以减少由于弱哈希计算导致的哈希冲突的发生
useAltHashing = sun.misc.VM.isBooted() &&
(initialCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
}
public synchronized V put(K key, V value) {
// Make sure the value is not null,而HashMap选择将key为null永远存放为table[0]位置
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
//确保key不在hashtable中
//首先,通过hash方法计算key的哈希值,并计算得出index值,确定其在table[]中的位置
//其次,迭代index索引位置的链表,如果该位置处的链表存在相同的key,则替换value,返回旧的value
Entry tab[] = table;
int hash = hash(key);
//计算下标,这里使用%方法,性能远不及HashMap的位运算 (这也是不推荐使用HashTable的原因之一)
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
//直接使用equals比较,而HashMap多了一层地址比较 `((k = e.key) == key || key.equals(k))`
if ((e.hash == hash) && e.key.equals(key)) {
V old = e.value;
e.value = value;
return old;
}
}
//结构性变更操作 modCount计数+1
modCount++;
//HashMap选择新增addEntry方法封装一下逻辑
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
//如果超过阀值,就进行rehash操作
rehash();
tab = table;
hash = hash(key);
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
//将值插入,返回的为null
Entry<K,V> e = tab[index];
// 创建新的Entry节点,并将新的Entry插入Hashtable的index位置,并设置e为新的Entry的下一个元素
tab[index] = new Entry<>(hash, key, value, e);
//size++
count++;
return null;
}
protected void rehash() {
int oldCapacity = table.length;
Entry<K,V>[] oldMap = table;//使用临时拷贝,保证当前数据时效性(参见JAVA的`观察者`模式实现)
// overflow-conscious code
//原容量的2倍+1
int newCapacity = (oldCapacity << 1) + 1;
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (oldCapacity == MAX_ARRAY_SIZE)
// Keep running with MAX_ARRAY_SIZE buckets
return;
newCapacity = MAX_ARRAY_SIZE;
}
Entry<K,V>[] newMap = new Entry[newCapacity];
//rehash也属于结构化变更,modCount计数+1
modCount++;
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
boolean currentAltHashing = useAltHashing;
useAltHashing = sun.misc.VM.isBooted() && (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean rehash = currentAltHashing ^ useAltHashing;
table = newMap;
//遍历原数组重新赋值给新数组
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
old = old.next;
if (rehash) {
e.hash = hash(e.key);//重新hash计算
}
//还是坑爹的%运算
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = newMap[index];
newMap[index] = e;
}
}
}
public synchronized V get(Object key) {
Entry tab[] = table;//使用临时拷贝,保证当前数据时效性(参见JAVA的`观察者`模式实现)
int hash = hash(key);
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;
}
//1、使用keys()
Enumeration<String> en1 = table.keys();
while(en1.hasMoreElements()) {
en1.nextElement();
}
//2、使用elements()
Enumeration<String> en2 = table.elements();
while(en2.hasMoreElements()) {
en2.nextElement();
}
//3、使用keySet()
Iterator<String> it1 = table.keySet().iterator();
while(it1.hasNext()) {
it1.next();
}
//4、使用entrySet()
Iterator<Entry<String, String>> it2 = table.entrySet().iterator();
while(it2.hasNext()) {
it2.next();
}
- HashTable 基于 Dictionary 类,而 HashMap 是基于 AbstractMap。Dictionary 是任何可将键映射到相应值的类的抽象父类,而 AbstractMap 是基于 Map 接口的实现,它以最大限度地减少实现此接口所需的工作.
- HashMap 的 key 和 value 都允许为 null,而 Hashtable 的 key 和 value 都不允许为 null。HashMap 遇到 key 为 null 的时候,调用 putForNullKey 方法进行处理(统一放入table[0]位置),而对 value 没有处理;Hashtable遇到 null,直接返回 NullPointerException.
- Hashtable 方法是同步,而HashMap则不是。Hashtable 中的几乎所有的 public 的方法都是 synchronized 的,而有些方法也是在内部通过 synchronized 代码块来实现。
- HashTable由于使用sync和%运算(以及相关算法实现)的缘故,相比于HashMap,性能较低,因此非常不推荐继续使用HashTable.
非竞争环境下推荐使用HashMap
多线程环境下推荐使用ConcurrentHashMap
集合番@Hashtable一文通(1.7版) 由 黄志鹏kira 创作,采用 知识共享 署名-非商业性使用 4.0 国际 许可协议 进行许可。
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名。