- 1. 概要
- 2. Collection
- 3. Map
- 4. 容器与 Lambda
- 4.1 list 与 lambda
- 4.2 map 与 lambda
- 方法引用，支持 lambda 简写">4.3 方法引用，支持 lambda 简写
- 5. 容器与线程安全
1. 概要
List、Set 与 Map 的关联 | 容器 | ArrayList | LinkedList | HashSet | LinkedHashSet | TreeSet | HashMap | LinkedHashMap | TreeMap | | —- | —- | —- | —- | —- | —- | —- | —- | —- | | 结构 | Object数组 | 双向链表 | HashMap | LinkedHashMap | 红黑树 | 数组+链表 | 拉链式散列结构 + 双向链表 | 红黑树 |
选用说明
线程安全性：ArrayList 和 LinkedList 均非同步，不保证线程安全；
- 插入和删除是否受元素位置的影响：ArrayList 受， LinkedList不受（与存储结构有关）；
三种遍历方式
//方式一：forfor (int i = 0; i < list.size(); i++) {str = list.get(i);}//方式二：IteratorIterator<String> iter = list.iterator();while(iter.hasNext()){str = iter.next();}//方式三：foreachfor (Object obj:list) {str = (String)obj;}
三种遍历速度对比
- ArrayList的遍历速度 for > Iterator > foreach，级别基本一致，推荐使用 for；
- LinkedList的遍历速度 Iterator > foreach >>> for；级别相差很大,且数据量越大越明显(尤其是超过100000级别)，一般用 foreach 或 Iterator；
- 现象与分析：
- ArrayList 的遍历中 for 比 Iterator 快，而 LinkedList 中却是 Iterator 远快于 for；
- ArrayList 是基于索引(index)的数组，LinkedList 是一个双向循环带头节点的链表，另 ArrayList 实现了RandomAccess 接口，支持快速随机访问；
- 补充：RandomAccess 接口无具体实现，只是作为一个标志说明实现该接口的类具有随机访问功能；
2.1.2 小结
collections 集合一般使用 foreach，对于 ArrayList 推荐用for，特殊情况下利用显示迭代器 Iterator：
1）遍历过程需对集合某元素进行删除、修改等； 2）并行地遍历多集合；
foreach 和 Iterator 基本效率相当，Iterator 稍快: foreach 基于 Iterator 实现；
2.2 Set
2.2.1 对比 HashSet、LinkedHashSet 与 TreeSet
Set 无重复元素
- HashSet 引用类型下保证唯一性的方法：Override hashCode & equals 方法；
- TreeSet 引用类型保证唯一性的方法：
- 自然排序法：引用类实现 Comparable 接口，重写 compareTo 方法；
- 比较器（推荐）：新建一个实现 Comparator 接口的类，重写 compare 方法；
//1.自然排序法class Object implements Comparable<Student>{@Overridepublic int compareTo(Object o){}}//2.比较器class ObjectComparetor implements Comparator<Object>{@Overridepublic int compare(Object o1, Object o2){}}class Object{}
插入顺序对比：HashSet 随机插入，treeSet 按自定义顺序插入，LinkedList 按构造顺序插入。
插入性能对比：HashSet 和 LinkedHashSet 在百万级及以下规模时，效率基本一致，LinkedHashSet 的时间消耗主要是在创建双向循环链表上； TreeSet 插入性能普遍更差的主要原因是在插入过程中构造一棵红黑树；
3. Map
3.1 HashMap
- 基本使用
```java
Map map = new HashMap();
Map map1 = new HashMap
//putAll map1.putAll(map); System.out.println(map1);//output : {a=4, b=2, c=3, e=5} //会按照 hashCode 排序 map2.putAll(map); System.out.println(map2);//output : {1=1, a=4, b=2, e=5} //map 允许 key 的类型不同, 即补充的泛型类型对map没有约束作用，可不写！
//remove map1.remove(“c”); System.out.println(map1);//output : {a=4, b=2, e=5}
//get System.out.println(map2.get(“c”)); // 对于不存在的key，返回的value为null System.out.println(map2.get(“b”));//output : 2
//isContain System.out.println(map1.containsKey(“c”));//output : false System.out.println(map2.containsValue(1));//output : true
//清空 map map.clear();
判断map是否为空 System.out.println(map.isEmpty());//isEmpty()
- 三种遍历方式```java//方式一：keySet，通过 key 获得 valueSet set = map.keySet();Iterator it1 = set.iterator();while (it1.hasNext()) {Object key_obj = it1.next();Object value_obj = map.get(key_obj);System.out.println("key : " + key_obj + " , value : " + value_obj);}//方式二：values，only value, no keyCollection collection = map.values();Iterator it = collection.iterator();while (it.hasNext()) {Object value_obj = it.next();System.out.println("value : " + value_obj);}//方式三：entrySet，既能获得 key，也能获得 value；Map.Entry en = null;Iterator iterator = map.entrySet().iterator();while (iterator.hasNext()) {en = (Map.Entry) iterator.next();System.out.println("key : " + en.getKey() + " , value : " + en.getValue());}
3.2 对比 HashMap、LinkedHashMap 和 TreeMap
- Map 无重复元素
- HashMap 引用类型下保证唯一性的方法：Override hashCode & equals 方法；
- TreeMap 引用类型下保证唯一性的方法：自然排序法、比较器（同 TreeSet）；
- key or value 为 null
- Hashtable 不支持 key 或 value 为 null，会抛出空指针异常 compareTo 方法；
- hashMap & linkedHashMap 支持 key-null,null-value,null-null；
- treeMap 不支持 key 为 null，会抛出空指针异常；
- 补充：HashMap 最多只允许一条记录的 key 为 null ，允许多条记录的 value 为 null；
- 插入顺序对比
- hashTable & hashMap 无序；
- linkedHashMap 有序，且与 put 顺序一致；
- treeMap 不支持 key 为 null，会抛出空指针异常；
- 插入性能对比： linkedHashMap > hashMap > treeMap （put过程中维持树的顺序）
-
4. 容器与 Lambda
4.1 list 与 lambda
foreach
ArrayList<String> list = new ArrayList<String>(Arrays.asList("af","bcws","cfw","daw","b","f","c")); list.forEach(str -> {if (str.equals("b")) { System.out.println("find b~"); }});removeIf
ArrayList<String> list = new ArrayList<String>(Arrays.asList("af","bcws","cfw","daw","b","f","c")); list.removeIf(s -> s.equals("c"));//对于已经删除的元素，在调用该方法的时候不报错replaceAll
ArrayList<String> list = new ArrayList<String>(Arrays.asList("af","bcws","cfw","daw","b","f","c")); list.replaceAll(s -> s.toLowerCase());sort
ArrayList<String> list = new ArrayList<String>(Arrays.asList("af","bcws","cfw","daw","b","f","c")); list.sort((s1,s2) -> s1.length() - s2.length());4.2 map 与 lambda
public static void testMapAndLambda(){ HashMap<Integer,String> map = new HashMap<>(); map.put(1,"cyt"); map.put(2,"ly"); map.put(3,"lrx"); //foreach map.forEach((k,v)->System.out.println(k+"="+v)); // replaceAll map.replaceAll((k,v)->v.toUpperCase()); // merge map.merge(1,"jjj",(v1,v2)->v1+v2); map.forEach((k,v)->System.out.println(k+"="+v));// 1=CYTjjj、2=LY、3=LRX // compute map.compute(1,(k,v)->v!=null?"new_cyt":v); map.forEach((k,v)->System.out.println(k+"="+v));// 1=new_cyt、2=LY、3=LRX }4.3 方法引用，支持 lambda 简写
5. 容器与线程安全
5.1 概要
HashMap 的线程安全： Collections.synchronizedMap or ConcurrentHashMap；
- 并行\并发集合
- 同步集合类：Hashtable、Vector、stack；
- 同步集合包装类：Collections.synchronizedMap()、Collections.synchronizedList()；
- 并发集合：ConcurrentHashMap、ConcurrentSkipListMap、ConcurrentSkipListSet、CopyOnWriteArrayList、CopyOnWriteArraySet、ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue、LinkedBlockingDeque、ConcurrentLinkedQueue；
5.2 使用
5.2.1 ConcurrentLinkedDeque
public static void testConcurrentLinkedDeque() { // 使用非阻塞线程安全的并发列表: 如果操作不能立即完成，将根据这个操作抛出异常或返回 null 值； // 大量添加数据到列表 class AddTask implements Runnable{ private ConcurrentLinkedDeque<String> list; public AddTask(ConcurrentLinkedDeque<String> list){ this.list = list; } @Override public void run(){ String name = Thread.currentThread().getName(); for (int i = 0; i < 10000; i++) { list.add(name + i); } } } class PollTask implements Runnable{ private ConcurrentLinkedDeque<String> list; public PollTask(ConcurrentLinkedDeque<String> list){ this.list = list; } @Override public void run(){ String name = Thread.currentThread().getName(); for (int i = 0; i < 5000; i++) { list.pollFirst(); list.pollLast(); } } } ConcurrentLinkedDeque<String> list = new ConcurrentLinkedDeque<>(); Thread[] threads = new Thread[100]; AddTask addTask = new AddTask(list); for (int i = 0; i < threads.length; i++) { // AddTask addTask = new AddTask(list); threads[i] = new Thread(addTask); threads[i].start(); } System.out.println("AddTask threads have been launched"); for (int i = 0; i < threads.length; i++) { try{ threads[i].join(); } catch (InterruptedException e) { e.printStackTrace(); } } System.out.println("Size of List : " + list.size()); PollTask pollTask = new PollTask(list); for (int i = 0; i < threads.length; i++) { // PollTask pollTask = new PollTask(list); threads[i] = new Thread(pollTask); threads[i].start(); } System.out.println("PollTask threads have been launched"); for (int i = 0; i < threads.length; i++) { try{ threads[i].join(); } catch (InterruptedException e) { e.printStackTrace(); } } System.out.println("Size of List : " + list.size()); /** output * AddTask threads have been launched * Size of List : 1000000 * PollTask threads have been launched * Size of List : 0 */ }
5.2.2 ConcurrentHashMap
public static void testConcurrentHashMap () {
// 并发执行时，线程安全的容器只能保证自身的数据不被破坏，无法保证业务的行为是否正确。
// final Map<String, Integer> count = new ConcurrentHashMap<>();
final Map<String, AtomicInteger> count = new ConcurrentHashMap<>();
final CountDownLatch endLatch = new CountDownLatch(2);
Runnable task = new Runnable() {
@Override
public void run() {
// concurrentHashMap 的 key 和 value 均不能为 null；
AtomicInteger oldValue;
for (int i = 0; i < 5; i++) {
oldValue = count.get("a");
if (null == oldValue) {
AtomicInteger zeroValue = new AtomicInteger(0);
oldValue = count.putIfAbsent("a", zeroValue);
if (null == oldValue) {
oldValue = zeroValue;
}
}
oldValue.incrementAndGet();
}
endLatch.countDown();
}
};
new Thread(task).start();
new Thread(task).start();// 使用多线程操作 concurrentHashMap，并发会造成结果覆盖，所以 “a” 的 value <= 10 ；
try {
endLatch.await();
System.out.println(count);
} catch (InterruptedException e) {
e.printStackTrace();
}
// 改进 1 ： public synchronized void run()
}
5.2.3 CopyOnWriteArrayList
public static void testCopyOnWriteArrayList(){
// CopyOnWriteArrayList 适合使用在读操作远大于写操作的场景中，如缓存；
class ListReader implements Runnable{
private List<String> list;
public ListReader(List list){
this.list = list;
}
@Override
public void run(){
if (list != null) {
for (String str : this.list) {
System.out.println(Thread.currentThread().getName() + " : " + str);
}
}
}
}
class ListWriter implements Runnable{
private List<String> list;
private int index;
public ListWriter(List list, int index){
this.list = list;
this.index = index;
}
@Override
public void run(){
if (this.list != null) {
this.list.add("...... add " + this.index + " ......");
}
}
}
// List<String> list = new ArrayList<>();// 多线程下，一个线程对 list 进行修改，另一个线程对 list 进行 for 时会抛出 ConcurrentModificationException 并发异常
List<String> list = new CopyOnWriteArrayList<>();// 每次修改时，会生成一个新的 copy ，并把新修改元素加入 copy 尾部，生成一个新的引用；
for (int i = 0; i <= 5; i++) {
list.add("...... Line " + (i + 1) + "......");
}
ExecutorService service = Executors.newFixedThreadPool(3);
for (int i = 0; i <= 3; i++) {
service.execute(new ListReader(list));
service.execute(new ListWriter(list, i));
}
service.shutdown();
}
5.2.4 CopyOnWriteArraySet
public static void testCopyOnWriteArraySet(){
/**
* 1）适用场景：Set 大小通常保持很小，只读操作远多于可变操作，需在遍历期间防止线程间的冲突；
* 2）线程安全的无序集合，与 hashSet 的相同点：继承父体-AbstractSet，不同点：hashSet 通过散列表 hashMap 实现，CopyOnWriteArraySet 通过动态数组 CopyOnWriteArrayList 实现；
* 3) 可变操作（add、set、remove等）开销很大，需复制整个 list；
* 4）迭代器支持 hasNext()、 next() 等不可变操作，不支持可变 remove() 操作；
* 5）使用迭代器进行遍历的速度很快，并且不会与其他线程发生冲突。在构造迭代器时，迭代器依赖于不变的数组快照；
*/
Set<String> set = new CopyOnWriteArraySet();
class MyThread extends Thread{
public MyThread(String name){
super(name);
}
@Override
public void run(){
int i = 0;
while (i++ < 10) {
String val = Thread.currentThread().getName() + "-" + i % 6;
set.add(val);
{
Iterator it = set.iterator();
while (it.hasNext()) System.out.print(it.next() + ",");
System.out.println();
}
}
}
}
new MyThread("thread_a").start();
new MyThread("thread_b").start();
/** 小困惑：不懂为什么会输出 两个 thread_a-1
* thread_a-1,thread_a-1,thread_b-1,thread_a-2,thread_b-2,thread_a-3,thread_b-3,thread_b-4,thread_a-4,thread_b-1,thread_a-2,thread_b-2,thread_a-3,thread_b-3,thread_b-4,thread_a-4,
*
*/
}
若有收获，就点个赞吧
0 人点赞
