集合分类
Collection接口(单列集合)
-
List接口: 特性 继承collection集合,排列有序且可重复
- LinkedList 接口实现类:链表实现,适用于插入删除型链表,线程不安全
- ArrayList接口实现类:数组实现,适用于随机访问型链表,线程不安全
- Vector接口实现类:数组实现,线程安全。
-
Set接口: 特性 继承collection集合,排列无序且不可重复
-
HashSet接口实现类:适用hash表(数组)存储元素。
- LinkedHashSet 继承HashSet,实现Set,链表维护元素的插入次序。
TreeSet接口实现类:二叉树实现,元素有序。
-
Map接口(双列集合)
HashTable 接口实现类,线程安全。
-
HashMap 接口实现类,线程不安全。
- LinkedHashMap 双向链表和哈希实现类。
- WeakHashMap
TreeMap 红黑树对所有的key进行排序。
IdentifyHashMap
总结
Map和List、Set的区别
- Map是接口,而List和Set是Collection的子接口
- Map是双列集合,而List和set是单列集合
List和set的区别
- List 是排列有序且可重复得集合,而且可以通过索引查询集合中的元素。
- Set 排列无序且不可重复,没有索引,当然,Set中的实现类LinkedHshSet是通过链表维护着插入顺序的。
List集合
有序列表,允许存放重复元素;其实现类由三个:
- ArrayList:数组实现,查询快,增删慢,轻量级;(线程不安全)
- LinkedList:双向循环链表实现,增删快,查询慢 (线程不安全)
- Vector:数组实现,重量级 (线程安全、使用少)
List的四种遍历方式
public class ListTest {
public static void main(String[] args) {
List<Integer> list=new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
//方法一,使用for循环(这种方法Set集合不适用)
for (int i = 0; i <list.size() ; i++) {
System.out.println(list.get(i));
}
//方法二:增强for循环
for(Integer elem:list){
System.out.println(elem);
}
//方法三:迭代器实现遍历(第一种和第二种的底层也是使用迭代器实现
Iterator<Integer> integerIterator=list.iterator();
while (integerIterator.hasNext()){
Integer elem=integerIterator.next();
System.out.println(elem);
}
//方法四:Lambda表达式+流式编程
list.forEach((elem)->System.out.println(elem));
//使用方法引用输出
list.forEach(System.out::println);
}
}
ArrayList自动扩充机制
源码:
private void add(E e, Object[] elementData, int s) {
// 判断元素个数是否等于当前容量
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}
private Object[] grow() {
return grow(size + 1);
}
private Object[] grow(int minCapacity) {
// 获取老容量,也就是当前容量
int oldCapacity = elementData.length;
// 如果当前容量大于0 或者 数组不是DEFAULTCAPACITY_EMPTY_ELEMENTDATA
if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity, /* minimum growth */
oldCapacity >> 1 /* preferred growth */);
return elementData = Arrays.copyOf(elementData, newCapacity);
// 如果 数组是DEFAULTCAPACITY_EMPTY_ELEMENTDATA(容量等于0的话,只剩这一种情况了)
} else {
return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
}
}
扩容可分为两种情况:
第一种情况,当ArrayList的容量为0时,此时添加元素的话,需要扩容,三种构造方法创建的ArrayList在扩容时略有不同:
1.无参构造,创建ArrayList后容量为0,添加第一个元素后,容量变为10,此后若需要扩容,则正常扩容。
2.传容量构造,当参数为0时,创建ArrayList后容量为0,添加第一个元素后,容量为1,此时ArrayList是满的,下次添加元素时需正常扩容。
3.传列表构造,当列表为空时,创建ArrayList后容量为0,添加第一个元素后,容量为1,此时ArrayList是满的,下次添加元素时需正常扩容。
第二种情况,当ArrayList的容量大于0,并且ArrayList是满的时,此时添加元素的话,进行正常扩容,每次扩容到原来的1.5倍。
ArrayList的线程安全解决方案
用victor代替;List list = new Vector<>();
用Colections:List list = Collections.synchronizedList(new ArrayList);
List list = CopyOnWriteArrayList<>();
LinkedList
采用双向循环链表实现,可以用来实现stack,queue,双向队列,但是哟实现的时候需要遵循实现结构的特性,比如实现栈的时候不能提供不是栈顶的元素出栈的方法,实现对列的时候需要遵循先进先出原则。
vector
和ArrayList类似,但是其实重量级组件,同时也是线程安全的,适用于高并发的场景。
List常用方法
void add(int index, Object element) :添加对象element到位置index上
boolean addAll(int index, Collection collection) :在index位置后添加容器collection中所有的元素
Object get(int index) :取出下标为index的位置的元素
int indexOf(Object element) :查找对象element 在List中第一次出现的位置
int lastIndexOf(Object element) :查找对象element 在List中最后出现的位置
Object remove(int index) :删除index位置上的元素
ListIterator listIterator(int startIndex) :返回一个ListIterator 跌代器,开始位置为startIndex
List subList(int fromIndex, int toIndex) :返回一个子列表List ,元素存放为从 fromIndex 到toIndex之前的一个元素