亳州网站制作公司,网站建设合作,适合seo优化的网站,做调查的网站有哪些Java——HashMap和HashTable的区别 Java HashMap和HashTable的区别1. 继承的父类2. 线程安全性3. null值问题4. 初始容量及扩容方式5. 遍历方式6. 计算hash值方式 Java HashMap和HashTable的区别
1. 继承的父类
都实现了Map、Cloneable#xff08;可复制#xff09;、Seria… Java——HashMap和HashTable的区别 Java HashMap和HashTable的区别1. 继承的父类2. 线程安全性3. null值问题4. 初始容量及扩容方式5. 遍历方式6. 计算hash值方式 Java HashMap和HashTable的区别
1. 继承的父类
都实现了Map、Cloneable可复制、Serializable可序列化接口。
HashMap: 继承自AbstractMap类。
public class HashMapK,V extends AbstractMapK,Vimplements MapK,V, Cloneable, Serializable {}HashTable: 继承自Dictionary类。
public class HashtableK,Vextends DictionaryK,Vimplements MapK,V, Cloneable, java.io.Serializable {}2. 线程安全性
HashMap: 线程不安全效率高。在多线程并发的环境下可能会产生死循环数据覆盖等问题。 参考 https://www.jianshu.com/p/e2f75c8cce01 https://www.cnblogs.com/developer_chan/p/10450908.html HashTable: 线程安全效率低。
3. null值问题
HashMap: 允许null值作为key或value。只有一个key可以为null可以多个null为value.
MapInteger, Integer map new HashMap();
map.put(null, 12);
System.out.println(map.get(null)); // 12
map.put(1, null);
map.put(2, null);
System.out.println(map.get(1)); // null
System.out.println(map.get(2)); // nullHashTable: 不允许null值作为key或value
HashtableInteger, Integer hashtable new Hashtable();
hashtable.put(null, 12); // java.lang.NullPointerException
hashtable.put(1, null); // java.lang.NullPointerException4. 初始容量及扩容方式
HashMap: hash数组默认大小为16扩容方式16 * 2 /*** The default initial capacity - MUST be a power of two.*/
static final int DEFAULT_INITIAL_CAPACITY 1 4; // aka 16/*** Initializes or doubles table size. If null, allocates in* accord with initial capacity target held in field threshold.* Otherwise, because we are using power-of-two expansion, the* elements from each bin must either stay at same index, or move* with a power of two offset in the new table.** return the table*/
final NodeK,V[] resize() {NodeK,V[] oldTab table;int oldCap (oldTab null) ? 0 : oldTab.length;int oldThr threshold;int newCap, newThr 0;if (oldCap 0) {if (oldCap MAXIMUM_CAPACITY) {threshold Integer.MAX_VALUE;return oldTab;}else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY)// 将阈值扩大为2倍newThr oldThr 1; // double threshold}else if (oldThr 0) // initial capacity was placed in thresholdnewCap oldThr;else { // zero initial threshold signifies using defaults// 当threshold的为0的使用默认的容量也就是16newCap DEFAULT_INITIAL_CAPACITY;newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if (newThr 0) {float ft (float)newCap * loadFactor;newThr (newCap MAXIMUM_CAPACITY ft (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold newThr;SuppressWarnings({rawtypes,unchecked})// 新建一个数组长度为原来2倍的数组NodeK,V[] newTab (NodeK,V[])new Node[newCap];table newTab;if (oldTab ! null) {for (int j 0; j oldCap; j) {NodeK,V e;if ((e oldTab[j]) ! null) {oldTab[j] null;if (e.next null)newTab[e.hash (newCap - 1)] e;else if (e instanceof TreeNode)((TreeNodeK,V)e).split(this, newTab, j, oldCap);else { // preserve order//HashMap在JDK1.8的时候改善了扩容机制原数组索引i上的链表不需要再反转。// 扩容之后的索引位置只能是i或者ioldCap原数组的长度// 所以我们只需要看hashcode新增的bit为0或者1。// 假如是0扩容之后就在新数组索引i位置新增为1就在索引ioldCap位置NodeK,V loHead null, loTail null;NodeK,V hiHead null, hiTail null;NodeK,V next;do {next e.next;// 新增bit为0扩容之后在新数组的索引不变if ((e.hash oldCap) 0) {if (loTail null)loHead e;elseloTail.next e;loTail e;}else { //新增bit为1扩容之后在新数组索引变为ioldCap原数组的长度if (hiTail null)hiHead e;elsehiTail.next e;hiTail e;}} while ((e next) ! null);if (loTail ! null) { loTail.next null;//数组索引位置不变插入原索引位置newTab[j] loHead;}if (hiTail ! null) {hiTail.next null;//数组索引位置变化为j oldCapnewTab[j oldCap] hiHead;}}}}}return newTab;
}HashTable: hash数组默认大小为11扩容方式old * 2 1
/*** Increases the capacity of and internally reorganizes this* hashtable, in order to accommodate and access its entries more* efficiently. This method is called automatically when the* number of keys in the hashtable exceeds this hashtables capacity* and load factor.*/
SuppressWarnings(unchecked)
protected void rehash() {int oldCapacity table.length;Entry?,?[] oldMap table;// overflow-conscious code// 扩容为 old * 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;}// 新建长度为old * 2 1的数组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 (EntryK,V old (EntryK,V)oldMap[i] ; old ! null ; ) {EntryK,V e old;old old.next;int index (e.hash 0x7FFFFFFF) % newCapacity;// 使用头插法将链表反序e.next (EntryK,V)newMap[index];newMap[index] e;}}
}5. 遍历方式
Hashtable、HashMap都使用了Iterator。而由于历史原因Hashtable还使用了Enumeration的方式。
HashMap实现 Iterator支持fast-fail当有其它线程改变了HashMap的结构增加删除修改元素将会抛出ConcurrentModificationException。不过通过Iterator的remove()方法移除元素则不会抛出ConcurrentModificationException异常。Hashtable的Iterator遍历支持fast-fail用 Enumeration不支持fast-fail。
6. 计算hash值方式
HashMap: 根据元素的key计算出一个hash值然后再用这个hash值来计算得到最终的位置。
HashMap为了提高计算效率将哈希表的大小固定为了2的幂这样在取模预算时不需要做除法只需要做位运算。效率虽然提高了但是hash冲突却也增加了。因为它得出的hash值的低位相同的概率比较高而计算位运算为了解决这个问题HashMap重新根据hashcode计算hash值后又对hash值做了一些运算来打散数据。使得取得的位置更加分散从而减少了hash冲突。当然了为了高效HashMap只做了一些简单的位处理。从而不至于把使用2的幂次方带来的效率提升给抵消掉。例如通过h ^ (h 16)无符号位右移。
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}static final int hash(Object key) {int h;return (key null) ? 0 : (h key.hashCode()) ^ (h 16);
}// 类似的原理 (table.length-1) hash(key)
public native int hashCode();HashTable: Hashtable直接使用key对象的hashCode。hashCode是JDK根据对象的地址或者字符串或者数字算出来的int类型的数值。然后再使用除留余数法来获得最终的位置。然而除法运算是非常耗费时间的效率很低。
public synchronized V put(K key, V value) {// Make sure the value is not nullif (value null) {throw new NullPointerException();}// Makes sure the key is not already in the hashtable.Entry?,? tab[] table;// 直接使用 key对象的 hashcodeint hash key.hashCode();// 0x7FFFFFFF转换为10进制之后是Intger.MAX_VALUE,也就是2^31 - 1int index (hash 0x7FFFFFFF) % tab.length;SuppressWarnings(unchecked)EntryK,V entry (EntryK,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;
}
