Java笔记 | 容器
为Java集合单开一篇。
- Iterable接口
iterator():返回 Iterator 类的迭代器实例。
forEach():对容器中的每个元素进行处理。
spliterator():并行遍历元素。
- Iterator接口
Java Iterator(迭代器)不是一个集合,它是一种用于访问集合的方法,可用于迭代 ArrayList 和 HashSet 等集合。Iterator 是 Java 迭代器最简单的实现,ListIterator 是 Collection API 中的接口, 它扩展了 Iterator 接口。
hasNext():检测容器中是否还有需要迭代的元素。
next():返回迭代器指向的元素,并且更新迭代器的状态,将迭代器指向的元素后移一位。
remove():将迭代器指向的元素删除。默认实现为抛出 UnsupportedOperationException 异常。
forEachRemaining():对容器中的剩余元素进行处理,直到剩余元素处理完毕或者抛出异常。
- Collection接口
添加元素:add()、addAll()
删除元素:remove()、removeAll()、clear()
保留元素:retainAll()
判断包含元素:contains()、containsAll()
其他方法:isEmpty()、size()、toArray()
- Map
HashMap
--数组⾥⾯每个地⽅都存了Key-Value这样的实例,在Java7叫Entry在Java8中叫Node。
--1.7及之前采用 数组 + 链表 实现。
--1.8采用 数组 + 链表or红黑树 实现。链表大于8会转为红黑树,红黑树小于6时转为链表,数组大于12(16*0.75)会扩容。
--put:找到数组中的位置之后,如果数组中没有元素直接存入,反之则判断key是否相同,key相同就覆盖,否则就会插入到链表的尾部。
--get:首先计算出hash值,然后去数组查询,是红黑树就去红黑树查,链表就遍历链表查询就可以了。
--resize:对key重新计算hash,然后把数据拷贝到新的数组。
--线程不安全,允许有null
--使其变为线程安全的两种方法:使用 Collections 的 synchronizedMap 方法;使用 ConcurrentHashMap。
LinkedHashMap
--HashMap与双向链表合并,可以保存插入顺序。
TreeMap
--可以排序
ConcurrentHashMap
--(1.7)用分段的 数组 + 链表 实现。采用锁分离技术,允许多个修改并发进行。内部细分了若干个小的 HashMap,称之为段(Segment)。默认情况下一个 ConcurrentHashMap 被进一步细分为 16 个段,既就是锁的并发度。
--(1.8)用 CAS+synchronized+Node 实现,加入红黑树。
--线程安全,不能有null。
HashTable
--synchronized针对整个哈希表
--线程安全,但并发度低,不推荐使用。
- HashMap 初始长度
HashMap可以指定初始容量,不指定的话默认是16(1<<4),如果传入一个值会使用大于等于这个值的最小2次幂来作为初始容量。
为什么是16:为了降低Hash碰撞的几率,如果HashMap的长度不是2的幂,那么有些索引出现的几率更大,有些索引永远不会出现,不符合均匀分布的原则。
- HashMap 扩容机制
当容量大小超过 现有长度*负载因子(默认0.75f)时就会扩容。
扩容分两步:
1.创建⼀个新的Entry空数组,⻓度是原数组的2倍。
2.ReHash:遍历原Entry数组,把所有的Entry重新Hash到新数组。
为什么重新Hash:
Hash的公式---> index = HashCode(Key) & (Length - 1)
索引与HashMap长度有关。
- HashMap 为什么线程不安全
在JDK1.7中,当并发执行扩容操作时会造成死循环和数据丢失的情况。
在JDK1.8中,在并发执行put操作时会发生数据覆盖的情况。
HashMap的线程不安全主要是发生在扩容函数中,即根源是在 transfer() 函数中,头插法会将链表的顺序翻转,这也是形成死循环的关键点。JDK1.7出现的问题,在JDK1.8中已经得到了很好的解决,JDK1.8直接在 resize() 函数中完成了数据迁移。另外说一句,JDK1.8在进行元素插入时使用的是尾插法。
使用尾插的好处:使⽤头插会改变链表的上的顺序,但是如果使⽤尾插,在扩容时会保持链表元素原本的顺序,就不会出现链表成环的问题了。
put/get⽅法都没有加同步锁,⽆法保证上⼀秒put的值,下⼀秒get的时候还是原值。
- ConcurrentHashMap
1.7使用Segment+HashEntry分段锁的方式实现。
1.8则抛弃了Segment,改为使用 CAS+synchronized+Node 实现,同样也加入了红黑树,避免链表过长导致性能的问题。
1.7 分段锁
从结构上说,1.7版本的ConcurrentHashMap采用分段锁机制,里面包含一个Segment数组(Segment继承与ReentrantLock),Segment则包含HashEntry的数组,HashEntry本身就是一个链表的结构,保存key、value和指向下一个节点的next指针。
实际上就是相当于每个Segment都是一个HashMap,默认的Segment长度是16,也就是支持16个线程的并发写,Segment之间相互不会受到影响。
put:整个流程和HashMap非常类似,只不过是先定位到具体的Segment,然后通过ReentrantLock去操作。
--计算hash,定位到segment,segment如果是空就先初始化
--使用ReentrantLock加锁,如果获取锁失败则尝试自旋,自旋超过次数就阻塞获取,保证一定获取锁成功
--遍历HashEntry,就是和HashMap一样,数组中key和hash一样就直接替换,不存在就再插入链表,链表同样
get:key通过hash定位到segment,再遍历链表定位到具体的元素上。需要注意的是value是volatile的,所以get是不需要加锁的。
1.8 CAS+synchronized
1.8转为用CAS+synchronized来实现,HashEntry改为Node,加入了红黑树的实现。
put:
--首先计算hash,遍历node数组,如果node是空的话,就通过CAS+自旋的方式初始化。
--如果当前数组位置是空则直接通过CAS自旋写入数据。
--如果hash==MOVED,说明需要扩容,执行扩容。
--如果都不满足,就使用synchronized写入数据。写入数据同样判断链表、红黑树,链表写入和HashMap的方式一样,key hash一样就覆盖,反之就尾插法,链表长度超过8就转换成红黑树。
get:通过key计算hash,如果key hash相同就返回,如果是红黑树按照红黑树获取,都不是就遍历链表获取。
- List、Set
ArrayList:基于数组实现。每次扩容为原来的1.5倍。适合随机查找和遍历。
LinkedList:基于双向链表实现,增删更快,改查更慢。同时实现了Queue接口,还提供offer(), peek(), poll()方法。
Vector:线程安全,基于数组实现,每个方法都加锁。Stack 是其子类。每次扩容为原来的2倍。⽤Collections.synchronizedList把⼀个普通ArrayList包装成⼀个线程安全版本的数组容器也可以,原理同Vector是⼀样的。
CopyOnWriteList:线程安全,基于数组实现,读操作不加锁。
HashSet:基于HashMap实现的集合。
CopyOnWriteSet:线程安全,读操作不加锁。
TreeSet:基于TreeMap实现的集合。不允许有null。
- ArrayList 指定初始容量后的大小
会初始化数组⼤⼩,但是List的⼤⼩没有变,因为List的⼤⼩是返回size的。使⽤set()会抛出异常,尽管该数组已创建,但是⼤⼩设置不正确。
- ArrayList 遍历
ArrayList遍历最⼤的优势在于内存的连续性,CPU的内部缓存结构会缓存连续的内存⽚段,可以⼤幅降低读取内存的性能开销。
- ConcurrentHashMap 原理
ConcurrentHashMap 锁的方式是细粒度的。 ConcurrentHashMap 将 hash 表分为 16 个桶(默认值),最大并发个数就是Segment的个数,默认值是16,可以通过构造函数改变一经创建不可更改,这个值就是并发的粒度,每一个segment下面管理一个table数组,加锁的时候其实锁住的是整个segment。
Java 1.7
ConcurrentHashMap 类中包含两个静态内部类 Segment 和 HashEntry。HashEntry 用来封装映射表的键值对;Segment 用来充当锁的角色,每个 Segment 对象守护整个散列映射表的若干个桶。每个桶是由若干个 HashEntry 对象链接起来的链表。一个 ConcurrentHashMap 实例中包含由若干个 Segment 对象组成的数组。
Java 1.8
为进一步提高并发性,放弃了分段锁,锁的级别控制在了更细粒度的table元素级别,也就是说只需要锁住这个链表的head节点,并不会影响其他的table元素的读写,好处在于并发的粒度更细,影响更小,从而并发效率更好
使用 CAS + synchronized 来保证实现put操作:如果Key对应的数组元素为null,则通过CAS操作将其设置为当前值。如果Key对应的数组元素(也即链表表头或者树的根元素)不为null,则对该元素使用synchronized关键字申请锁,然后进行操作。如果该put操作使得当前链表长度超过一定阈值,则将链表(寻址时间复杂度为O(N))转换为红黑树(寻址时间复杂度为O(log(N)),插入操作完成之后如果所有元素的数量大于当前容量(默认16)*负载因子(默认0.75)就进行扩容。
- Collection的常用方法
boolean add(E e):添加一个元素
boolean addAll(Collection<? extends E> c):添加目标集合中所有元素
void clear():清除所有元素
boolean contains(Object o):是否包含一个元素
boolean containsAll(Collection<?> c):是否包含目标集合中所有元素
boolean equals(Object o):比较两集合中的元素是否相等
boolean isEmpty():是否为空
Iterator<E> iterator():迭代器
boolean remove(Object o):删除一个元素
boolean removeAll(Colection<?> c):删除包含目标集合元素的所有元素
boolean retainAll(Collection<?> c):删除不包含目标集合元素的所有元素
int size():当前集合中元素个数
Object[] toArray():返回当前集合对应的Java默认数组
- List的常用方法
void add(int index, E element):在指定位置插入元素,后面的元素后移
boolean addAll(int index, Collection<? extends E> c):插入目标集合中所有元素,返回当前集合是否有改变
E get(int index):返回指定位置的元素
int indexOf(Object o):返回指定元素第一次出现的位置,如果没有返回-1
ListIterator<E> listIterator():列表迭代器
ListIterator<E> listIterator(int index):列表迭代器
E remove(int index):删除指定位置的元素
E set(int index, E element):修改指定位置的元素
List<E> subList(int fromIndex, int toIndex):返回子List
- Map的常用方法
V put(K key, V value):添加键值对
void putAll(Map<? extends K, ? extends V> m):添加指定Map中的所有键值对
boolean containsKey(Object key):是否包含对应键的键值对
boolean containsValue(Object value):是否包含对应值的键值对
Set<Map.Entry<K,V>> entrySet():返回Map对应的Set
V get(Object key):返回键对应的值
V remove(Object key):删除对应键的键值对
Set<K> keySet():返回包含所有键的Set
Collection<V> values():返回包含所有值的Collection
- List在遍历时如何删除元素
for循环:删除时后面元素会前移
增强for循环:删除后无法继续遍历
iterator:可以正常遍历及删除,需要使用iterator的remove方法。
- fail-fast 快速失败机制
当在迭代集合的过程中该集合在结构上发生改变的时候,就有可能会发生fail-fast,即抛出ConcurrentModificationException异常。fail-fast机制并不保证在不同步的修改下一定会抛出异常,它只是尽最大努力去抛出,所以这种机制一般仅用于检测bug。