集合框架总览
集合接口:(短虚线表示),表示不同集合类型,是集合框架的基础。
抽象类:(长虚线表示),对集合接口的部分实现。可扩展为自定义集合类。
实现类:(实线表示),对接口的具体实现
HashMap
HashMap内部实现就是一个哈希表,即一个数组,数组的元素是一个链表的头结点。 当HashMap中的元素越来越多的时候,hash冲突的几率也就越来越高。HashMap在创建时有一个负载因子,当元素的个数大于数组长度×负载因子的大小时,HashMap就会进行扩容。把数组的大小扩展2倍。然后重新计算各个元素的hash值。
Fail-Fast
HashMap不是线程安全的,因此如果在使用迭代器的过程中有其他线程修改了Map,那么将抛出ConcurrentModificationException,这就是Fail-Fast策略 其实现是通过modCount域,modeCount记录修改次数,迭代器在初始化的过程中会将这个值保存在expectedModCount,在迭代的过程中,判断modCount与expectedModCount是否相等,如果不相等,说明已经有其他线程修改了Map,注意这里的modCount必须声明为volatile,以保证线程之间的可见性。
TreeMap
TreeMap的内部通过红黑树实现。根据键的自然顺序进行排序,或者根据创建映射时提供的Comparator进行排序,具体取决于使用的构造方法。 TreeMap的基本操作containsKey,get,put和remove的时间复杂度是logn
HashTable
- HashTable基于Dictionary类,而HashMap基于AbstractMap
- HashMap的key和value都允许为null,而HashTable的key和Value都不允许为null
- HashTblae中急速所有的public方法都是synchronized,而有些方法也是在内部通过synchronized代码块来实现。
java的线程安全
Vector、Stack、HashTable、ConcurrentHashMap、Properties
java集合框架(常用)
Collection - List - ArrayList
Collection - List - LinkedList
Collection - List - Vector
Collection - List - Vector - Stack
Collection - Set - HashSet
Collection - Set - TreeSet
Collection - List - LinkedHashSet
Map - HashMap
Map - TreeMap
Map - HashTable
Map - LinkedHashMap
Map - ConcurrentHashMap
为什么使用ConcurrentHashMap而不是HashMap或Hashtable?
HashMap的缺点:主要是多线程同时put时,如果同时触发了rehash操作,会导致HashMap中的链表中出现循环节点,进而使得后面get的时候,会死循环,CPU达到100%,所以在并发情况下不能使用HashMap。让HashMap同步:Map m = Collections.synchronizeMap(hashMap);而Hashtable虽然是同步的,使用synchronized来保证线程安全,但在线程竞争激烈的情况下HashTable的效率非常低下。因为当一个线程访问HashTable的同步方法时,其他线程访问HashTable的同步方法时,可能会进入阻塞或轮询状态。如线程1使用put进行添加元素,线程2不但不能使用put方法添加元素,并且也不能使用get方法来获取元素,所以竞争越激烈效率越低。
ConcurrentHashMap的原理:
HashTable容器在竞争激烈的并发环境下表现出效率低下的原因在于所有访问HashTable的线程都必须竞争同一把锁,那假如容器里有多把锁,每一把锁用于锁容器其中一部分数据,那么当多线程访问容器里不同数据段的数据时,线程间就不会存在锁竞争,从而可以有效的提高并发访问效率,这就是ConcurrentHashMap所使用的锁分段技术,首先将数据分成一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据的时候,其他段的数据也能被其他线程访问。