Java基础-集合.md

Posted by lizhao on 07-09,2019

[toc]

List

ArrayList(动态数组)

在内部实现中,核心是一个对象数组 objArr,和一个当前下标索引 size。所有的增删改查都是操作数组。数组的默认大小为 10

插入

尾部插入

尾部插入:正常情况,把 objArr 的 size 位的值设置进去( objArr[size] = E )。

中间插入

中间插入:排队买饭,再过3个人就能到你了,有人塞到了你前面,你的下标现在是多少?

把传入下标位置后面的数据,下标加一。把数组的 传入下标位置 值改为传入的对象,

如:传入下标index和对象E,index~size之间的下标加1(这一块需要循环遍历),然后index位置现在就是空的,就把objArr[index] = E;

扩容

特殊情况,扩容,size值已经比数组的长度大了,所以要进行扩容操作,把数组长度翻个倍

删除

"我被人插队了,还有心情算我的下标?"你一个飞毛腿把她踹出队伍,现在你的下标是多少?

把下标后面的数据往前移,需要循环遍历

恭喜你又成功的变成一个孤独的下标3

查询

返回objArr[index]

总结

内部通过数组实现,能动态增加数组长度。查询很快。删除和插入需要移动/复制部分数据,代价很高

Vector(线程安全的动态数组)

和ArrayList实现原理一样,在增删改查方法前面添加synchronized。

--》线程安全--》所以各个方法都比ArrayList慢。

LinkedList(链表)

维护一个头节点firstNode,节点Node的数据结构包含实体(E),上一个节点(pre),下一个节点(next)

为了说明增删查的操作,用->表示next节点指向的节点。假设有一个LinkedList,里面的数据是firstNode,firstNode->B,B->C,C->D,D->E,E->F。就是firstNode->B->C->D->E->F

删除

把"上家的下家"变成"我的下家",把"下家的上家"变成"我的上家"

比如要删除C,那么整个表就变成了firstNode->B->D->E->F

插入

把要插入地方的上下家修改下。

比如我要在BC之间插入H,那就把B的下家变成H,C的上家变成H,H的上家变为B,H的下家变成C。 firstNode->B->H->C->D->E->F

查询

只能通过循环链表一个个取,然后判断是不是想要的数据。需要循环

比如我要找到E数据,那就是先找到firstNode,这时候就知道要去找B,B知道C的线索,。。。最后找到了E

实现了Deque的接口

这个可以直接对头结点或者尾结点操作,所以可以当做队列或者栈

总结

  1. 插入、删除快,查询比较慢
  2. 可作为队列、栈

CopyOnWriteArrayList

线程安全的ArrayList,内部实现就维护一个数组,读的时候不加锁,在插入删除的时候加锁--顺便复制一份数组--操作完毕在给数组重新赋值

public boolean add(E e) {
    synchronized (lock) {
        Object[] es = getArray();
        int len = es.length;
        es = Arrays.copyOf(es, len + 1);
        es[len] = e;
        setArray(es);
        return true;
    }
}

Map

HashMap

数组加链表(红黑树)的形式,左边是数组,右边是链表。 看图比较好,HashMap里面维护了一个数组NodeArr,默认长度为16。这个数组的坑里面只会有一个数据Node,但是这个node包含了下一个位置的节点,所以组成了一个链表

hash算法

会调用对象的hashCode方法,算出一个数字值,对NodeArr取余数,就可以知道该落在哪个坑里面了

假设通过hash算法a算出来的值为0,b为1,c为2,d为3,e为4 ,a2 = 16,a3=32,a4=64

添加(put)

空情况

如图,我这时候添加一个key为a,值为A的数据,那么NodeArr[0] =Node(a,A) 。

已有数据,key冲突(少于8个)

如图,我这时候添加一个key为b2,值为B2的数据,那么NodeArr[1] = Node(b2,B2);Node(b2,B2).next = B1;

已有数据,key冲突(多于8个)

这时候链表就会变成一个红黑树,存在坑里面的就是根节点,如E

获取(get)

如图,我这时候要获取Node(c3,C3),通过key为c3获取,获取过程。

  1. 算出c3的hash值,为2;
  2. 找到NodeArr(2),为Node(c1,C1);
  3. 循环链表,找到key为c3的节点。
  4. 判断c1 == c3?--》c2==c3?-->c3 == c3,找到了Node(c3,C3);
  5. 返回Node.getValue,返回大写的C3

删除

获取key值,找到坑位,链表的删除,或者红黑树的删除。

扩容

添加的时候有个特殊情况,就是超过一定阈值(预设值0.75*16),就会触发,变成原来的2倍,就是将有32、64、128..个坑位了

我们原来c1,c2,c3,c4 = 3,19,35,67,对数组原大小16取余数都是3,所以放在同一个坑位里面。 现在坑位变成32。

那么c2,c4的余数就会变成19,他们就要去NodeArr[19]= Node(c2,C2); Node(c2,C2).next = Node(c4,C4);

HashTable

和HashMap差不多,线程安全类。就是在各个方法前面加了个synchronized,差不多废弃了

TreeMap

和HashMap差不多,区别在于HashMao维护的是一个NodeArr,而TreeMap维护的是一颗节点数,TreeRodeNode

ConCurrentHashMap

一个线程安全的HashMap。

1.7

搞了一个分段的概念,数组+数组+链表。维护一个SegmentArr,里面存的对象是数组+链表(就是一个HashMap),如果要做到线程同步,那就是把某一个seg锁起来,其他的seg还是正常使用。

1.8

去掉了SegmentArr,数据结构又和HashMap一样了,这里实现线程同步,使用的是CAS和synchronized。

put
  1. 根据 key 计算出 hashcode 。
  2. 判断是否需要进行初始化。
  3. f 即为当前 key 定位出的 Node,如果为空表示当前位置可以写入数据,利用 CAS 尝试
  4. 写入,失败则自旋保证成功。
  5. 如果当前位置的 hashcode == MOVED == -1,则需要进行扩容。
  6. 如果都不满足,则利用 synchronized 锁写入数据(分为链表写入和红黑树写入)。
  7. 如果数量大于 TREEIFY_THRESHOLD 则要转换为红黑树。

Set

关键:不能存放重复的数据

HashSet

挂羊头,卖狗肉。

里面维护的是一个HashMao,增删改查都是去操作HashMap,只是存的时候put(Key,Null);

Iterator

迭代器是一种设计模式,它是一个对象,它可以遍历并选择序列中的对象,而开发人员不需要了解该序列的底层结构。迭代器通常被称为“轻量级”对象,因为创建它的代价小。

就是个游标,指向当前位置,可以通过他进行遍历

用法

  1. 使用方法iterator()要求容器返回一个Iterator。第一次调用Iterator的next()方法时,它返回序列的第一个元素。注意:iterator()方法是java.lang.Iterable接口,被Collection继承。
  2. 使用next()获得序列中的下一个元素。
  3. 使用hasNext()检查序列中是否还有元素。
  4. 使用remove()将迭代器新返回的元素删除。

其他

快速失败(fail-fast)和安全失败(fail-safe)

快速失败(fail—fast)

除法方法,在进行运算之前,会判断除数是否为0,是的话就抛出异常。这就是一个快速失败的案例。

在集合中也有

在用迭代器遍历一个集合对象时,如果遍历过程中对集合对象的内容进行了修改(增加、删除、修改),则会抛出Concurrent Modification Exception。

原理:迭代器在遍历时直接访问集合中的内容,并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化,就会改变modCount的值。每当迭代器使用hashNext()/next()遍历下一个元素之前,都会检测modCount变量是否为expectedmodCount值,是的话就返回遍历;否则抛出异常,终止遍历。

注意:这里异常的抛出条件是检测到 modCount!=expectedmodCount 这个条件。如果集合发生变化时修改modCount值刚好又设置为了expectedmodCount值,则异常不会抛出。因此,不能依赖于这个异常是否抛出而进行并发操作的编程,这个异常只建议用于检测并发修改的bug。

场景:java.util包下的集合类都是快速失败的,不能在多线程下发生并发修改(迭代过程中被修改)。

安全失败(fail—safe)

可参考CopyOnWriteArrayList

采用安全失败机制的集合容器,在遍历时不是直接在集合内容上访问的,而是先复制原有集合内容,在拷贝的集合上进行遍历。

原理:由于迭代时是对原集合的拷贝进行遍历,所以在遍历过程中对原集合所作的修改并不能被迭代器检测到,所以不会触发Concurrent Modification Exception。

缺点:基于拷贝内容的优点是避免了Concurrent Modification Exception,但同样地,迭代器并不能访问到修改后的内容,即:迭代器遍历的是开始遍历那一刻拿到的集合拷贝,在遍历期间原集合发生的修改迭代器是不知道的。

场景:java.util.concurrent包下的容器都是安全失败,可以在多线程下并发使用,并发修改。

题目

容器

  1. java 容器都有哪些?
  2. Collection 和 Collections 有什么区别?
  3. List、Set、Map 之间的区别是什么?
  4. HashMap 和 Hashtable 有什么区别?
  5. 如何决定使用 HashMap 还是 TreeMap?
  6. 说一下 HashMap 的实现原理?
  7. 说一下 HashSet 的实现原理?
  8. ArrayList 和 LinkedList 的区别是什么?
  9. 如何实现数组和 List 之间的转换?
  10. ArrayList 和 Vector 的区别是什么?
  11. Array 和 ArrayList 有何区别?
  12. 在 Queue 中 poll()和 remove()有什么区别?
  13. 哪些集合类是线程安全的?
  14. 迭代器 Iterator 是什么?
  15. Iterator 怎么使用?有什么特点?
  16. Iterator 和 ListIterator 有什么区别?
  17. 怎么确保一个集合不能被修改?
  18. Set和List区别?
  19. Arrays.asList获得的List使用时需要注意什么
  20. Enumeration和Iterator区别
  21. 什么是 Properties 类?
  22. 如何将一个字符串转换为arraylist?
  23. 如何对一组对象进行排序
  24. BlockingQueue是什么?
  25. 队列和栈是什么,列出它们的区别?

答案

  1. java 容器都有哪些?
Collection的子类List、Set和Queue
List主要有ArrayList,LinkedList,Vector,CopyOnWriteArrayList
Set主要有HashSet,TreeSet
Map是键值对,子类包括HashMap,ConCurrentHashMap,HashTable,TreeMap
队列Queue
栈Stack继承Vector


  1. Collection 和 Collections 有什么区别?

Collection主要是集合的抽象类,Collections是一个工具类,里面主要是对于集合的操作 3. List、Set、Map 之间的区别是什么?

List:存放有序,列表存储,元素可重复

Set:无序,元素不可重复

Map:无序,元素可重复
  1. HashMap 和 Hashtable 有什么区别?
1. 底层实现差不多
2. HashTable线程安全,主要是通过在方法前面加synchronized
3. HashMap可以存入null(key和value),HashTable不行(key和value)
4. HashTable父类是Dictionary,HashMap父类是AbstractMap
  1. 如何决定使用 HashMap 还是 TreeMap?
HashMap的key值无序, TreeMap的key值有序,按照红黑树来排列
如果需要按照一定顺序遍历key值,可以选用TreeMap

平常用HashMap
  1. 说一下 HashMap 的实现原理?
数组+链表(红黑树)
添加:计算哈希值,找到对应的数组下标位置,然后坐进去
出现hash冲突(2个值有同一个hash值),占住坑位,把原来的对象往后挪,形成一个链表
链表太长了(链表长度默认最大8),会转换成红黑树
红黑树也太长了,扩容数组,然后重新分配坑位

查找:根据key算出hash值,找到对应的坑位,遍历链表,挨个判断是否相同,然后返回

删除::根据key算出hash值,找到对应的坑位,遍历链表,挨个判断是否相同,然后删除

  1. 说一下 HashSet 的实现原理?
维护了一个HashMap,都是通过操作HashMap实现
添加:hashMap.put(key,null);
删除:hashMap.remove(key);
查找:无序,只能通过遍历方式比较获取
  1. ArrayList 和 LinkedList 的区别是什么?
动态数组和链表
删除和插入LinkedList的时间复杂度O(1),ArrayList为O(n)
查找LinkedList的时间复杂度O(n),ArrayList为O(1)
LinkedList 还实现了 Queue 接口,该接口比List提供了更多的方法,包括 offer(),peek(),poll()等
  1. 如何实现数组和 List 之间的转换?
List转数组:toArray(arraylist.size()方法

数组转List:Arrays的asList(a)方法

捞一点就循环

  1. ArrayList 和 Vector 的区别是什么?
Vector和ArrayList都是动态数组,但Vector属于强同步类。
如果你的程序本身是线程安全的,没有多个线程共享该数组,那么使用ArrayList比较好。
  1. Array 和 ArrayList 有何区别?
Array 是原生数组,不可变大小
ArrayList 是动态数组,同时也封装了很多方法 remove,Iterator

  1. 在 Queue 中 poll()和 remove()有什么区别?
poll()方法和remove()方法都是从队列中取出一个元素,但是poll()在获取失败的时候会返回空,remove()方法在获取数据失败的时候抛出异常
  1. 哪些集合类是线程安全的?
Vector:就比arraylist多了个同步化机制(线程安全),因为效率较低,现在已经不太建议使用。在web应用中,特别是前台页面,往往效率(页面响应速度)是优先考虑的。

Statck:继承了vector,堆栈类,先进后出

HashTable:就比hashmap多了个线程安全

ConCurrentHashMap:1.8以前是分段锁,1.8之后是CAS和synchronized
  1. 迭代器 Iterator 是什么?
游标,遍历。根据这个东西能获取到当前位置的数据。不管你是list、Set。
不管你内部怎么实现,ArrayList或者LinkedList,我就是拿到当前位置的值,然后在继续往下走

  1. Iterator 怎么使用?有什么特点?
public static void main(String[] args) {
    ArrayList list = new ArrayList();
    list.add("a");
    list.add("b");
    list.add("c");
    Iterator it = list.iterator();
    while(it.hasNext()){
        String str = (String) it.next();
        System.out.println(str);
    }
}
  1. Iterator 和 ListIterator 有什么区别?
Iterator 可用来遍历 Set 和 List 集合,但是 ListIterator 只能用来遍
历 List。Iterator 对集合只能是前向遍历,ListIterator 既可以前向也可以后
向。
ListIterator 实现了 Iterator 接口,并包含其他的功能,比如:增加元素,替
换元素,获取前一个和后一个元素的索引,等等
  1. 怎么确保一个集合不能被修改?
private final static ImmutableList<Integer> list = ImmutableList.of(1, 2, 3);  // 这样被初始化之后 list是不能被改变
private final static ImmutableSet set = ImmutableSet.copyOf(list); // 这样被初始化之后set是不能被改变的
private final static ImmutableMap<Integer, Integer> map = ImmutableMap.of(1,2,3,4,5, 6);
private final static ImmutableMap<Integer, Integer> map2 = ImmutableMap.<Integer, Integer>builder().put(1,2).put(3,4).put(5,6).build();

  1. Set和List区别?
无序和有序
无重复和可重复
不可使用for循环(无下标)和可以使用for循环
插入删除不会引起元素位置变化 和 会
  1. Arrays.asList获得的List使用时需要注意什么
asList 得到的只是一个 Arrays 的内部类,一个原来数组的视图 List,因此如果对它进行增删操作会报错

用 ArrayList 的构造器可以将其转变成真正的 ArrayList
  1. Enumeration和Iterator区别
函数接口不同

Enumeration只有2个函数接口。通过Enumeration,我们只能读取集合的数据,而不能对数据进行修改。
Iterator只有3个函数接口。Iterator除了能读取集合的数据之外,也能数据进行删除操作。
Iterator支持fail-fast机制,而Enumeration不支持。

Enumeration 是JDK 1.0添加的接口。使用到它的函数包括Vector、Hashtable等类,这些类都是JDK 1.0中加入的,Enumeration存在的目的就是为它们提供遍历接口。Enumeration本身并没有支持同步,而在Vector、Hashtable实现Enumeration时,添加了同步。
而Iterator 是JDK 1.2才添加的接口,它也是为了HashMap、ArrayList等集合提供遍历接口。Iterator是支持fail-fast机制的:当多个线程对同一个集合的内容进行操作时,就可能会产生fail-fast事件。
注意:Enumeration迭代器只能遍历Vector、Hashtable这种古老的集合,因此通常不要使用它,除非在某些极端情况下,不得不使用Enumeration,否则都应该选择Iterator迭代器。
  1. 什么是 Properties 类?
Properties 是Hashtable的子类。它被用于维护值的list,其中它们的键、值都是String类型
  1. 如何将一个字符串转换为arraylist?
arrayList.toArray() 方法

  1. 如何对一组对象进行排序
Arrays.sort()
Collection.sort()
  1. BlockingQueue是什么?
Java.util.concurrent.BlockingQueue是一个队列,在进行检索或移除一个元素的时候,它会等待队列变为非空;当在添加一个元素时,它会等待队列中的可用空间。BlockingQueue接口是Java集合框架的一部分,主要用于实现生产者-消费者模式。我们不需要担心等待生产者有可用的空间,或消费者有可用的对象,因为它都在BlockingQueue的实现类中被处理了。Java提供了集中BlockingQueue的实现,比如ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue,、SynchronousQueue等。
  1. 队列和栈是什么,列出它们的区别?
队列:先进先出,吃了拉
栈:先进后出,吃了吐