集合

1.集合和数组之间的区别有：

数组的长度是固定的，集合的长度是可变的
数组中存储的是同一类型的元素，集合中存储的数据可以是不同类型的，除了泛型限制
数组中可以存放基本类型数据或者对象，集合中只能存放对象，基本数据类型会自动装箱
数组是由JVM中现有的类型+[] 组合而成的，除了一个length属性，还有从Object中继承过来的方法之外，数组对象就调用不到其他属性和方法了
集合是由JavaAPI中的java.util包里面所提供的接口和实现类组成的，这里面定义并实现了很多方法，可以使用集合对象直接调用这些方法，从而操作集合存放的数据

2.集合框架中主要有三个要素组成：

接口整个集合框架的上层结构，都是用接口进行组织的。接口中定义了集合中必须要有的基本方法。通过接口还把集合划分成了几种不同的类型，每一种集合都有自己对应的接口。
实现类对于上层使用接口划分好的集合种类，每种集合的接口都会有对应的实现类。每一种接口的实现类很可能有多个，每个的实现方式也会各有不同。
数据结构每个实现类都实现了接口中所定义的最基本的方法，例如对数据的存储、检索、操作等方法。但是不同的实现类，它们存储数据的方式不同，也就是使用的数据结构不同。

3.集合按照其存储结构可以分为两大类：

java.util.Collection 单列集合基本数据类型对应的包装器类型 list set queue
java.util.Map 双列集合 key-value

其他的集合接口，都是由这两个接口派生出来的,Collection父接口：Interable

4.Collection是父接口，其中定义了单列集合(List和Set)通用的一些方法，这些方法可用于操作所有的单列集合对象。 Collection类型集合必须要有的基本的方法：

//向集合中添加元素

boolean add(E e)

//把一个指定集合中的所有数据，添加到当前集合中 1 2 3

一些方法的使用样例：

boolean addAll(Collection c)

//清空集合中所有的元素。

void clear()

//判断当前集合中是否包含给定的对象。

boolean contains(Object o)

//判断当前集合中是否包含给定的集合的所有元素。

boolean containsAll(Collection c)

//判断当前集合是否为空。

boolean isEmpty()

//返回遍历这个集合的迭代器对象

Iterator iterator()

//把给定的对象，在当前集合中删除。

boolean remove(Object o)

//把给定的集合中的所有元素，在当前集合中删除。

boolean removeAll(Collection c)

//判断俩个集合中是否有相同的元素，如果有当前集合只保留相同元素，如果没有当前集合元素清空

boolean retainAll(Collection c)

//返回集合中元素的个数。

int size()

//把集合中的元素，存储到数组中。

Object[] toArray()

//把集合中的元素，存储到数组中，并指定数组的类型

T[] toArray(T[] a)

5.Vector

since 1.0 java集合的开始，实现自动扩容，可变长数组,现在Vector成了Collection的子类，线程安全的集合

6.迭代器

为了能够方便的遍历集合中的每一个元素，API中提供了一个迭代器接口： java.util.Iterator 该接口可以很方便的迭代出集合中的元素。是Collection集合及其子类型集合通用的方式

java.lang.Iterable 接口中，定义了获取迭代器的方法：

public interface Iterable {

Iterator iterator();

}

java.util.Iterator 接口中，主要定义俩个方法：

public interface Iterator {

boolean hasNext(); //返回当前迭代器中是否还有下一个对象

Object next(); //获取迭代器中的下一个对象

}

7.foreach循环

增强for循环 Collection类型及其子类型的集合，还有数组，都可以使用foreach循环进行遍历其中的元素数据

for(变量类型变量名：集合）{

//操作变量

}

集合：

Collection c1 = new ArrayList<>();

c1.add("hello1");

c1.add("hello2");

c1.add("hello3");

for(Object o:c1){

System.out.println(o);

}

数组：

int[] arr = {1,3,5,7,9};

//每次循环，使用变量i接收数组中的一个数据

for(int i : arr){

System.out.println(i);

}

8.数据结构

（1）栈：先进后出，弹栈、压栈

（2）队列 queue：一端插入，另一端删除，先进先出

（3）数组：连续的内存空间，数组查询速度快，中间删除较慢

（4）链表：数据+下一个对象的地址值单向链表，双向链表查找元素慢，新增和删除元素较快

（5）红黑树:平衡二叉B树前序、中序、后序，左旋、右旋，保持平衡

左子树都比根节点小，右子树都比根节点大

红黑树的指定颜色的目的，是利用颜色值作为二叉树的平衡对称性的检查

根节点必须是黑色
其他节点可以是红色的或者黑色
叶子节点（特指null节点）是黑色的
每个红色节点的子节点都是黑色的
任何一个节点到其每一个叶子节点的所有路径上黑色节点数相同

（6）哈希表：数组+链表+红黑树

哈希碰撞，哈希相同链表链表长度默认是8，超过八转化为红黑树

9.List集合：接口 (Collection)

（1）有序集合（而非排序），元素可以重复，带索引

（2）List接口常用方法：还有从父接口Collection中继承过来的方法

//返回集合中指定位置的元素。

E get(int index);

//用指定元素替换集合中指定位置的元素,并返回被替代的旧元素。

E set(int index, E element);

//将指定的元素，添加到该集合中的指定位置上。

void add(int index, E element);

//从指定位置开始，把另一个集合的所有元素添加进来

boolean addAll(int index, Collection c);

//移除列表中指定位置的元素, 并返回被移除的元素。

E remove(int index);

//查收指定元素在集合中的所有，从前往后查到的第一个元素（List集合可以重复存放数据） int indexOf(Object o);

//查收指定元素在集合中的所有，从后往前查到的第一个元素（List集合可以重复存放数据） int lastIndexOf(Object o);

//根据指定开始和结束位置，截取出集合中的一部分数据

List subList(int fromIndex, int toIndex);

（3）List接口的实现类

ArrayList ：增删慢，查找快，使用数组来实现数据的存储

LinkedList ：采用的数据结构是链表还是一个双向链表

LinkedList 类不仅实现了 List 接口，还有 Queue 接口以及子接口 Deque 也实现了

//将指定元素插入此列表的开头

void addFirst(E e)

//将指定元素添加到此列表的结尾

void addLast(E e)

//返回此列表的第一个元素 E

getFirst()

//返回此列表的最后一个元素

E getLast()

//从此列表所表示的堆栈处弹出一个元素

E pop()

//将元素推入此列表所表示的堆栈

void push(E e)

//移除并返回此列表的第一个元素

E removeFirst()

//移除并返回此列表的最后一个元素

E removeLast()

LinkedList 同时具有队列和栈的操作方法，pop和push都是栈结构的操作方法

VectorVector

内部也是采用了数组来存储数据，但是 Vector 中的方法大多数都是线程安全的方法，所以在多线并发访问的环境中，可以使用 Vector 来保证集合中元据操作的安全。

查看 Vector 中方法的定义，可以看到多大数方法都使用了 synchronized 关键字，来给当前方法加锁。

（4）list集合的索引：也有以下三种方式的遍历，还有一种根据索引进行遍历

迭代器、增强for循环、forEach

List list = new ArrayList(set);

for(int x=0;x<list.size();x++){

Object o = list.get(x);

System.out.println(o);

}

10.Set集合 (Collection)

（1）无序集合、不带下标索引、不能存放重复数据

Set set = new HashSet();

//用迭代器遍历

        Iterator it = set.iterator();

        while(it.hasNext()){

                Object obj = it.next();

        System.out.println(obj);

        }

//增强for循环遍历

for(Object obj : set){

        System.out.println(obj);

        }

//JDK8中的forEach遍历

(1)class ConsumerImpl implements Consumer{

        @Override

public void accept(final Object o){

System.out.println(o);

}

}

set.forEach(new ConsumerImpl());

(2）set.forEach(new Consumer(){



@Override

public void accept(final Object o){

System.out.println(o);

}

})；

//（3）接口中只有一个方法,lambda表达式重写就可以省略

set.forEach(o->System.out.println(o));/

set.forEach（System.out：：println);

（2）Set实现类

hashSet 底层：hashMap (key,value) 值赋给key

HashSet中元素不可重复，主要是靠对象的hashCode和equals方法来判断对象是否重复。

若重复，就不会被传进来，而不是覆盖

TreeSet (Set接口的子接口SortedSet的实现类) 底层：TreeMap Conparable接口的compareTo方法保证不可重复

TreeSet可以将我们存进去的数据进行排序，排序的方式有俩种：

自然排序 int result = o1.compareTo(o2); 字符串：字典顺序排序

public static void main(String[] args) {

        Set set = new TreeSet();

         set.add(3); //代码执行的时候，会自动进行装箱，把基本类型数据3变为Integer对象，然后再存放到集合中

        set.add(5); //Integer类是实现了 Comparable 接口的，那么Integer类的俩个对象之间就可以调用 compareTo 方法比较大小了，当前对象比较出来大小，那么对象就可以按照从小到大的顺序进行排序。

        set.add(1);

        set.add(7);

for(Object obj : set){

        System.out.println(obj);

        }

}

//输出结果：

1

3

5

7

比较器排序（也称客户化排序）Set排序逻辑和业务逻辑不符时，自定义排序逻辑

public interface Comparator { //指定泛型

int compare(T o1, T o2);

}

public static void main(String[] args) {

//使用Comparator接口，创建出匿名内部类对象，这个对象就是要用的比较器对象

        Comparator c = new Comparator() {

                @Override

                public int compare(Object o1, Object o2) {

                        Student s1 = (Student) o1;   //

                        Student s2 = (Student) o2;    //

                        return s1.age > s2.age? 1 : (s1.age==s2.age? 0 : -1);    //

// return -s1.compareTo(s2);

        }

};

//创建TreeSet对象的时候，把比较器对象传入

        Set set = new TreeSet(c);

        set.add(new Student("mary",23));

        set.add(new Student("jack",21));

        set.add(new Student("tom",20));

        set.add(new Student("lucy",22));

        for(Object obj : set){

                System.out.println(obj);

        }

}

class Student implements Comparable{

public int compareTo(Object o){

Student that = (Student)o;

                return 0;

//Student rhat =(Student)o;

//先比name,name如果能产生结果，则整个就是name的结果

//如果name相等，再比age

//int nameComp = this.name.compareTo(that.name);

// int ageComp = this.age-that.age;

// return nameComp ==0?ageComp:nameComp;

}

}

（3）java.util.Objects 是JDK1.7提供的一个对象的工具类，里面定义的一些静态方法，提供了操作对象的方法 equals(Object a, Object b) hash(Object... values)

Arrays 工具类

Collections工具类

11.发展历程

Vector (单列) HashTable（双列）

List Map

Collection(List、、（Vector）、 Map( Hashtable)

Set(Map的key实现))

12.List和Set

可以通过Set集合对List集合中的元素去重

List list=new ArrayList(Set);

Set set = new HashSet(list);

Set 集合和List集合都实现了对toString方法的重写

13.Map（双列）

（1）Set：Map的key Map的value没有任何特性

Set添加元素：add Map添加元素：put

Map map = new HashMap();

map.put("张三",20);

map.put("张三",30);

System.out.println(map); // {张三=30} key值重复，会更新，然后把被覆盖的值返回

Set<K> keySet() 获取Map集合中所有的key值

Collection<V> values() 获取Map集合中所有的value值

Set<Map.Entry<K,V>> entrySet() 把Map集合中的key-value封装成Entry类型对象，再存放到set集合中，k-v当成一个元素

Set<Map.entry> entries = map.entrySet();
for(Map.entry entry: entries){

Object key = entry.getKey();

Object value = entry.getValue();

}

///getKey() getValue()

（2）Map集合的遍历

(1) 通过get()方法

Set keys = map.keySet();

System.out.println(keys);

for(Object key:keys){

Object value = map.get(key);

System.out.println("value = "+value);

}

（2）拿到所有的Entry对象，再通过getKey() getValue()

Set<Map.entry> entries = map.entrySet();
for(Map.entry entry: entries){

Object key = entry.getKey();

Object value = entry.getValue();

}

(3) jdk8中的forEach

14.练习

public class Student{
//练习//编写Student（String name,int age)类//创建多个Student类的对象//将其存储在List集合中，对List集合进行迭代遍历//判断 如果名字叫“张三”，从List中移除该对象String name;int age;Student(String name,int age){this.age=age;this.name=name;}
}
class StudentTest {public static void main(String[] args) {Student stu1=new Student("赵六",20);Student stu2=new Student("李四",22);Student stu3=new Student("张三",24);Student stu4=new Student("王五",25);List list=new ArrayList<>();list.add(stu1);list.add(stu2);list.add(stu3);list.add(stu4);Iterator iterator = list.iterator();while(iterator.hasNext()) {Student s = (Student)iterator.next();System.out.println(s);if ("张三".equals(s.name)){list.remove(s);}}}}

并发修改异常：两个及以上不属于同一个对象的行为在操作同一个集合

原因：迭代器初始化在-1，类似于指针，通过集合长度和索引值+1判断有没有下个元素，将张三移除后，后面元素补上，长度改变，索引值+1=长度，认为后边没有元素

Iterato是一次性的，知道有下一个元素hasNext()，但是取不出来，先获取的迭代器，再在list中添加

hasNext（）决定理论上能不能移，next（）决定实际上能不能移,增强for循环底层也是迭代器

解决方案：只针对list集合，set没有解决方法,增强for循环也会出现并发修改异常

迭代器 listIterator ,只能解决并发修改问题，迭代器添加元素只会在当前位置添加，不会添加在最后 litr.add("kevin",20)，不管移不移除张三，都取不到kevin

ListIterator litr = list.listIterator();while (litr.hasNext()){Student s=(Student)litr.next();System.out.println(s);if("张三".equals(s.name)){litr.remove();}

通过索引遍历，不会出现并发修改异常

for(int x=0;x<list.size();x++){Student s=(Student)list.get(x);System.out.println(s);if("张三".equals(s.name)){list.remove(s);list.add(new Student("kevin",20));}