HashMap与HashTable

in JAVA with 0 comment

简介

HashMap与HashTable均实现了Map接口 HashTable已经过时,HashMap可以通过下面的语句进行同步: Map m = Collections.synchronizeMap(hashMap); 或者使用同步的ConcurrentHashMap

区别

HashMap | HashTable -|- 非线程安全|线程安全 允许null作为键和值|不允许 效率高|较低 非同步|同步,适合多线程环境 fail-fast迭代器|非fail-fast迭代器 不能保证元素次序|- -|提供了对键的列举(Enumeration)。 扩容后是2的次方倍|扩大一倍

JDK1.8之后的HashMap增加了红黑树

红黑树的引入显著提高了Hash的效率,当一个链表太长的时候,HashMap会动态的将它替换成一个红黑树,这话的话会将时间复杂度从O(n)降为O(logn),在Hash极不均匀的情况下,JDK1.7的花费时间是增长的趋势,而JDK1.8是明显的降低趋势,并且呈现对数增长稳定。

什么是同步:

同步sychronized意味着在一次仅有一个线程能够更改Hashtable。就是说任何线程要更新Hashtable时要首先获得同步锁,其它线程要等到同步锁被释放之后才能再次获得同步锁更新Hashtable。

什么是Fail-Safe:

Fail-safe和iterator迭代器相关。如果某个集合对象创建了Iterator或者ListIterator,然后其它的线程试图结构上更改集合对象(即删除或者插入一个元素),将会抛出ConcurrentModificationException异常。但其它线程可以通过set()方法更改集合对象是允许的,因为这并没有从“结构上”更改集合。但是假如已经从结构上进行了更改,再调用set()方法,将会抛出IllegalArgumentException异常。

实现

底层结构

Hash

创建

PUT

GET