第16章集合类

作者: yangsg | 来源:发表于2019-04-12 10:18 被阅读517次

第10章集合类与泛型《Kotin 编程思想·实战》
第7章集合类
Java集合
14. 集合类
第16章集合类
Java 容器 - 一文详解HashMap
Collection 集合类
Java集合类-集合类图谱
那些年我们追过的Java面试之集合类、异常处理
函数的定义和调用

1. 集合的概念

集合是一种数学概念，表述的是“由一个或多个确定的元素所构成的整体”。

1.1 Java中集合与数组的比较

数组

数组在初始化时是定长的，初始化后数组长度不可改变。（长度表示的是最大容量）
数组中只能存放同类型的数据，比如int数组只能存数字不能存String
数组中没有现成API方法使用，数组只有一个length属性可用

集合

集合在初始化时可以不设置长度，随着元素放入集合，长度可变。（集合中已经存放了多少个元素）
集合在没有约束泛型的情况下，其可以存放任意类型的数据
集合类中提供了大量的API方法，方便程序开发者操作集合

1.2 集合的分类

集合的继承体系

Collection接口（线性集合）
(1) List接口（有序号可重复）
ArrayList实现类基于数组方式实现
LinkedList实现类基于链表方式实现
(2) Set接口（无序号不重复）
HashSet实现类基于Hash表算法
Map接口（键值集合）
HashMap实现类基于Hash表算法
Iterator接口（迭代器）

2. 线性集合（Collection接口）

2.1 线性集合的概念

Collection接口表述的是“线性集合”，线性结构是n个数据元素的有序（次序）集合
线性集合的特征
1．集合中必存在唯一的一个"第一个元素"。
2．集合中必存在唯一的一个"最后的元素"。
3．除最后元素之外，其它数据元素均有唯一的"后继"。
4．除第一元素之外，其它数据元素均有唯一的"前驱"。

2.2 线性集合(Collection)的实现类

2.2.1 List接口

有序集合（也称为序列）。该界面的用户可以精确控制列表中每个元素的插入位置。用户可以通过整数索引（下标）访问元素，并搜索列表中的元素。允许集合中存放重复的数据。
有序号可重复

2.2.1.1 ArrayList实现类

底层是基于数组实现的，方法都是线程不安全的
API方法

add(Object o)返回值是boolean
在集合的结尾处添加一个元素
add(int index, Object o)返回值是void
在index位置插入一个元素，插入后，后面的元素会自动后移
addAll(Collection c)返回值是boolean
在集合结尾处添加集合c中的所有元素
clear()返回值是void
清空集合，保留集合对象
contains(Object o)返回值是boolean
在集合中查找o是否存在，存在判断依据是元素是否“equals”o
如果在集合中找到了“相等”的元素，返回true，否则返回false
get(int index)返回值是Object
获得集合中index位置上的元素，不会移除这个元素
set(int index, Object o)返回值是Object
用指定元素o替换集合中index位置上的元素，并返回被替代的元素
remove(int index)返回值是Object
移除集合中index位置上的元素，并返回这个元素
remove(Object o)返回值是boolean
移除集合中的第一个o元素（判断依据是集合中的某个元素“equals”o），返回是否移除成功。
size()返回值是int
返回集合中元素的个数（集合的长度）
indexOf(Object o)返回值是Object
查找o在集合中位置，如果没找到返回-1

public class Test {

    public static void main(String[] args) {
        ArrayList list = new ArrayList();
        System.out.println(list.size());
        list.add(new String("哈哈"));
        list.add(23);
        list.add(new Date());
        list.add("哈哈");
        list.add(3.14);
        System.out.println(list.size());
        System.out.println("插入了5个元素==========================");
        for(int i = 0; i < list.size(); i++) {
            Object o = list.get(i);
            System.out.println(o);
        }
        System.out.println("在2位置插入了嘻嘻==========================");
        list.add(2, "嘻嘻");
        for(int i = 0; i < list.size(); i++) {
            Object o = list.get(i);
            System.out.println(o);
        }
        System.out.println("替换2位置为嘿嘿==========================");
        list.set(2, "嘿嘿");
        for(int i = 0; i < list.size(); i++) {
            Object o = list.get(i);
            System.out.println(o);
        }
        System.out.println("移除位置2的元素==========================");
        list.remove(2);
        for(int i = 0; i < list.size(); i++) {
            Object o = list.get(i);
            System.out.println(o);
        }
        System.out.println("移除元素“3.14”的元素==========================");
        list.remove(3.14);
        for(int i = 0; i < list.size(); i++) {
            Object o = list.get(i);
            System.out.println(o);
        }
        System.out.println("移除元素“哈哈”的元素==========================");
        list.remove(new String("哈哈"));
        for(int i = 0; i < list.size(); i++) {
            Object o = list.get(i);
            System.out.println(o);
        }
        System.out.println("判断集合中是否有“哈哈”的元素==========================");
        boolean b = list.contains("哈哈");
        System.out.println(b);
        System.out.println("判断集合中是否有“3.14”的元素==========================");
        boolean x = list.contains(3.14);
        System.out.println(x);
        System.out.println("清空集合==========================");
        list.clear();
        System.out.println(list.size());
    }
}

如果遇到了集合中有元素2，且还需要移除2下标时，注意写法

list.remove(2);  //移除下标位置2的元素
list.remove(new Integer(2)); //移除集合中元素2

2.2.1.2 LinkedList实现类

底层是基于链表实现的
主要的增删改查的方法参照ArrayList类的API学习
特有API方法

addFirst(Object o)和addLast(Object o)返回值void
在集合的开始和结尾处插入一个元素o
getFirst()和getLast()返回值Object
返回集合的开始和结尾处的元素

将LinkedList看做为一个栈

peek()返回值Object
查看栈顶元素，但不移除它
poll()和pop()返回值Object
出栈
push(Object o)返回值void
将Object o入栈

public class Test3 {
    public static void main(String[] args) {
        LinkedList<Object> list = new LinkedList<Object>();     
        list.push("哈哈");
        list.push("嘻嘻");
        list.push(100);
        list.push(3.14);
        list.push(new Date());
        
        for(int i = 0; i < list.size(); i++) {
            Object o = list.get(i);
            System.out.println(o);
        }
        System.out.println("查看栈顶==============================");
        Object x = list.peek(); //查看栈顶
        System.out.println(x);
        for(int i = 0; i < list.size(); i++) {
            Object o = list.get(i);
            System.out.println(o);
        }
        System.out.println("出栈==============================");
        Object y = list.pop();
        System.out.println(y);
        System.out.println("====");
        for(int i = 0; i < list.size(); i++) {
            Object o = list.get(i);
            System.out.println(o);
        }
        System.out.println("入栈==============================");
        list.push("abc");
        for(int i = 0; i < list.size(); i++) {
            Object o = list.get(i);
            System.out.println(o);
        }
        System.out.println("出栈==============================");
        Object z = list.poll();
        System.out.println(z);
        System.out.println("====");
        for(int i = 0; i < list.size(); i++) {
            Object o = list.get(i);
            System.out.println(o);
        }
    }
}

2.2.1.3 Vector实现类

底层是基于数组实现的，方法都是线程安全的
API方法参照ArrayList学习

笔试题/面试题
(1)ArrayList和LinkedList的区别？
本质上就是问“数组”与“链表”的区别。
ArrayList基于数组实现的，LinkedList基于链表实现
数组：在查询元素速度快，插入删除速度慢
链表：在查询元素速度慢，插入删除速度快

(2)ArrayList和Vector的区别？
ArrayList线程不安全，Vector线程安全

2.2.2 Set接口

不包含重复元素的集合。如果有元素e1和e2（e1.equals(e2) 为true），e1和e2只能保留一个元素。Set接口的特征是使用者无法控制元素的存放顺序，其存放顺序有Set接口的实现类自身的算法决定

2.2.2.1 HashSet实现类

实现算法是基于Hash表算法，存放顺序不由使用者控制，允许存放一个null值
Object类中有hashcode方法，返回int值，该int值是由对象的内存地址计算出来的
一个对象会有一个HashCode（哈希码，Hash码，HashCode），它有如下特征：

如果两个对象拥有相同的内存地址，他们一定有相同的哈希码
如果两个对象拥有相同的哈希码，他们的内存地址可能不一样
哈希表算法，按照哈希码的大小顺序存放数据。

比如：字符串“哈哈”的哈希码是34，字符串“嘻嘻”的哈希码是20。
使用代码存入集合的顺序：哈哈，嘻嘻
实际集合中存储顺序：嘻嘻，哈哈

比如：字符串“哈哈”的哈希码是34，字符串“嘻嘻”的哈希码是20，字符串“嘿嘿”的哈希码也是34。
使用代码存入集合的顺序：哈哈，嘻嘻
实际集合中存储顺序：嘻嘻，（哈哈，嘿嘿）

类似的存储结构

API方法

add(Object o)返回值boolean
将o对象放入集合，放入的位置由集合的算法自身决定
clear() 返回值void
清空集合
isEmpty()返回值boolean
判断集合是否为空
remove(Object o)返回值boolean
在集合中移除o元素
size()返回值int
返回集合的长度
iterator()返回值Iterator
返回set集合对应的迭代器

因为Set集合无法使用下标，所以不能通过下标进行遍历访问集合中的元素。只能通过迭代器去遍历Set集合

2.2.3 Iterator(迭代器)

负责通过一个向前的“游标”不断的访问元素和移动，完成Set集合的遍历。

理解迭代器

API方法

hasNext()返回值：boolean
判断游标当前位置之后是否有数据
next()返回值：Object
取得游标当前位置之后的数据，再将游标向后移动一位
由于next()包含了移动的操作，所以在循环中应该只调用一次

示例：利用迭代器遍历set集合

public class Test1 {

    public static void main(String[] args) {
        HashSet<Object> set = new HashSet<Object>();
        set.add("哈哈");
        set.add(3.14);
        set.add(new Date());
        set.add("hehe");
        set.add(23);    
        set.add(12);
        System.out.println(set.size());
        
        Iterator<Object> ite = set.iterator();//获得了set集合对应的迭代器
        while(ite.hasNext()) {
            Object o = ite.next();
            System.out.println(o);
        }
    }
}

面试题/笔试题：
(1)List集合和Set集合的区别？
List集合：有序可重复，可以通过下标访问数据，存放顺序可控，允许存放重复数据
Set集合：无序不重复，不能通过下标访问数据，存放数据由实现类自己决定，重复数据只能保留一个
(2)HashSet和TreeSet的区别？
HashSet基于哈希表算法实现
TreeSet基于红黑树算法实现

很多时候使用Set集合完成去重复的操作。

3. 键值集合（Map接口）

Map集合是一种以键值对为单位，进行数据存储的一种结构，它与线性集合有所区别：线性集合一个位置上只存储一个数据，键值对集合一个位置上存储的是一个键（key）和一个值（value）。不同数据之间键（key）是不能重复的，值（value）是也可重复的。存放数据时，必须提供key和value，取得数据时一般是根据key来获取value
Map的主要实现类

3.1 HashMap和HashTable

基于哈希表算法实现存储

3.1.1 构造方法

HashMap()创建一个初始容量是16，负载因子是0.75的默认的对象
初始容量：对象初始默认可以存放16个键值对
负载因子：表示当容量达到最大容量的75%时（比如，初始16，16的75%是12），，容量会加倍扩容（16*2=32）。
这个构造方法是比较常用的
HashMap(int init)创建一个初始容量是init，负载因子是0.75的对象
HashMap(int init, float ext)创建一个初始容量是init，负载因子是ext的对象
HashMap(Map map)利用map的数据重新构建一个同样数据的HashMap

3.1.2 API方法

put(Object key, Object value)返回值：Object
将key-value组成的键值对，放入集合；如果集合中已经存在了同key的键值对，会利用新的key-value替换原有的key-value

HashMap<Integer, String> map = new HashMap<Integer, String>();
map.put(101, "赵四");  //向集合中添加一条数据
map.put(102, "刘能");  //向集合中添加一条数据
map.put(101, "哈哈");  //替换集合中原来101这条数据

remove(Object key)返回值：Object
根据key值，删除集合中的一个键值对，并返回对应value
这个方法是使用频率较高的

map.remove(103);

remove(Object key, Object value)返回值：boolean
根据key-value值，删除集合中的一个键值对。返回是否删除成功

map.remove(104,"刘能"); //成功，有这对数据
map.remove(102,"aaa");//失败，虽然有102，102中不是aaa

clear()返回值：void
清空整个集合

map.clear();

get(Object key)返回值：Object
根据key值，返回集合中key对应value，如果集合中没有这个key，返回null

String v1 = map.get(103);
String v2 = map.get(105);

size()返回值：int
返回集合中键值对的个数

System.out.println("集合中的元素个数是:"+map.size());

entrySet()返回值：Set<Entry>
一个entry对象表示一个键值对
返回所有键值对组成的一个Set集合

Set<Entry<Integer, String>> set = map.entrySet();//得到键值对的Set集合
Iterator<Entry<Integer, String>> ite = set.iterator();//将set集合变成迭代器
while(ite.hasNext()) { //遍历迭代器
    Entry<Integer, String> e = ite.next(); //一个键值对
    System.out.println(e.getKey()+":"+e.getValue());
}

keySet()返回值：Set<Object>
返回所有key值组成的一个Set集合

Set<Integer> kset = map.keySet(); //所有key值组成的set集合
Iterator<Integer> kite = kset.iterator(); //将set集合变成迭代器
while(kite.hasNext()) { //遍历迭代器
    int key = kite.next();
    String value = map.get(key); //取得value
    System.out.println(key+":"+value);
}

isEmpty()返回值：boolean
判断集合是否为空集合

boolean x = map.isEmpty();

containsKey(Object key)返回值boolean
判断集合中的key是否包含参数key，（判断依据：equals）

boolean b1 = map.containsKey(101);
boolean b2 = map.containsKey(105);

containsValue(Object value)返回值boolean
判断集合中的value是否包含参数value，（判断依据：equals）

boolean b3 = map.containsValue("刘能");
boolean b4 = map.containsValue("AAA");

面试题/笔试题
(1)HashMap与HashTable的区别
HashMap是线程不安全的，HashTable是线程安全。
HashMap中允许null作为key，HashTable不允许null作为key

(2)HashMap与TreeMap的区别
HashMap底层基于Hash表算法
TreeMap底层基于二叉树算法

(3)HashMap的桶容量（扩容机制）
以默认hashmap()构造方法解释：，默认初始值16，负载因子0.75.
初始时hashmap的最大容量是16，当存储数据至12时（16*0.75）,进行扩容，扩容方式是16*2=32; 当继续存储数据至24时（32*0.75）,继续扩容，扩容方式32*2=64

3.2 TreeMap

基于红黑树算法实现存储
参照HashMap的API去理解

put
get
remove
keySet
entrySet
containsKey

4. 泛型

泛型是用于约束集合中输入数据类型的。集合默认是可以将任何数据都放入其中，很多情况下我们需要约束集合中输入的元素类型，借助于泛型可以达到效果。
泛型的优势

约束输入至集合的数据类型，控制数据准确
从集合输出数据时，无需考虑类型转换问题
可以使用for...each句式快速遍历集合

约束输入类型为String

ArrayList<String> list = new ArrayList<String>();

由于泛型约束只支持引用数据类型，如果需要约束一个整数集合，需要使用包装类

ArrayList<Integer> list = new ArrayList<Integer>();

泛型约束Employee类的集合

ArrayList<Employee> list = new ArrayList<Employee>();

泛型约束其他的集合

ArrayList<HashSet<String>> list = new ArrayList<HashSet<String>>();

for...each句式：使用变量s去遍历list集合中每（each）一个元素

ArrayList<String> list = new ArrayList<String>();
for(String s : list) {
    System.out.println(s);
}

5. Collections类（集合工具类）

主要提供了大量的关于集合操作的方法，方便操作集合

copy(List dest, List src)返回值：void
将集合src复制到集合dest中
list2一开始必须有不少于list1的数据，否则会报出异常

public class Test2 {

    public static void main(String[] args) {
        ArrayList<Integer> list1 = new ArrayList<Integer>();
        ArrayList<Integer> list2 = new ArrayList<Integer>();
        Random r = new Random();
        for(int i = 0; i < 10; i++) {
            int x = r.nextInt(100);
            list1.add(x);
        }
        for(int i = 0; i < 10; i++) {
            int x = r.nextInt(100);
            list2.add(x);
        }
        System.out.println(list1);
        System.out.println(list2);
        System.out.println("=======================");
        //集合copy
        Collections.copy(list2, list1);
        
        System.out.println(list1);
        System.out.println(list2);
    }
}

sort(List list)返回值：void
将集合按照“自然排序”（实际上就是升序）

public class Test3 {
    public static void main(String[] args) {
        ArrayList<Integer> list1 = new ArrayList<Integer>();
        Random r = new Random();
        for(int i = 0; i < 10; i++) {
            int x = r.nextInt(100);
            list1.add(x);
        }
        System.out.println(list1);
        Collections.sort(list1);//升序
        System.out.println(list1); 
    }
}

如果想比较的是自己编写的类，可以通过让自己的类实现Comparable接口并完成CompareTo方法
Student类

public class Student implements Comparable<Student>{
    
    private int sno;
    private String sname;
    
    public Student() {}
    
    public Student(int sno, String sname) {
        this.sno = sno;
        this.sname = sname;
    }

    public int getSno() {
        return sno;
    }

    public void setSno(int sno) {
        this.sno = sno;
    }

    public String getSname() {
        return sname;
    }

    public void setSname(String sname) {
        this.sname = sname;
    }

    @Override
    public int compareTo(Student o) {
        if(this.sno < o.sno) {
            return -1;
        }else if(this.sno == o.sno) {
            return 0;
        }else {
            return 1;
        }
    }
}

利用sort方法进行排序

public class Test {

    public static void main(String[] args) {
        ArrayList<Student> list = new ArrayList<Student>();
        
        Student s1 = new Student(1002,"赵四");
        Student s2 = new Student(1004,"刘能");
        Student s3 = new Student(1001,"谢广坤");
        Student s4 = new Student(1003,"王大拿");
        
        list.add(s1);
        list.add(s2);
        list.add(s3);
        list.add(s4);
        
        for(Student s : list) {
            System.out.println(s.getSno()+"\t"+s.getSname());
        }
        System.out.println("============================");
        Collections.sort(list);
        
        for(Student s : list) {
            System.out.println(s.getSno()+"\t"+s.getSname());
        }   
    }
}

sort(List list, Comparator c)返回值：void
将集合按照“ Comparator”的规则进行排序
Student类

public class Student{
    
    private int sno;
    private String sname;
    
    public Student() {}
    
    public Student(int sno, String sname) {
        this.sno = sno;
        this.sname = sname;
    }

    public int getSno() {
        return sno;
    }

    public void setSno(int sno) {
        this.sno = sno;
    }

    public String getSname() {
        return sname;
    }

    public void setSname(String sname) {
        this.sname = sname;
    }

}

编写一个比较器

public class StudentComparator implements Comparator<Student> {

    @Override
    public int compare(Student o1, Student o2) {
        if(o1.getSno() < o2.getSno()) {
            return -1;
        }else if(o1.getSno() == o2.getSno()) {
            return 0;
        }else {
            return 1;
        }
    }
}

利用sort进行排序

public class Test {

    public static void main(String[] args) {
        ArrayList<Student> list = new ArrayList<Student>();
        
        Student s1 = new Student(1002,"赵四");
        Student s2 = new Student(1004,"刘能");
        Student s3 = new Student(1001,"谢广坤");
        Student s4 = new Student(1003,"王大拿");
        
        list.add(s1);
        list.add(s2);
        list.add(s3);
        list.add(s4);
        
        for(Student s : list) {
            System.out.println(s.getSno()+"\t"+s.getSname());
        }
        System.out.println("============================");
        Collections.sort(list, new StudentComparator());
        
        for(Student s : list) {
            System.out.println(s.getSno()+"\t"+s.getSname());
        }       
    }
}

reverse(List list)返回值：void
将集合list中的所有数据反转

public class Test3 {
    public static void main(String[] args) {
        ArrayList<Integer> list1 = new ArrayList<Integer>();
        Random r = new Random();
        for(int i = 0; i < 10; i++) {
            int x = r.nextInt(100);
            list1.add(x);
        }
        System.out.println(list1);
        Collections.sort(list1);//升序
        System.out.println(list1); 
        Collections.reverse(list1);//降序
        System.out.println(list1); 
    }
}

第10章集合类与泛型《Kotin 编程思想·实战》
第10章集合类与泛型 10.1 Kotlin集合类10.1.1 不可变集合类10.1.1.1 List10.1....
第7章集合类
第7章集合类在 Java 类库中有一套相当完整的容器集合类来持有对象。Kotlin没有去重复造轮子（Scala...
Java集合
集合概述 •Java提供集合类，集合类主要负责保存、盛装其他数据，因此集合类也被称为容器类。所有集合类都位于jav...
14. 集合类
1. Kotlin的集合类 Kotlin的集合类分为可变集合类和不可变集合类 2. 常用的三种集合类主要有三种:...
第16章集合类
1. 集合的概念集合是一种数学概念，表述的是“由一个或多个确定的元素所构成的整体”。 1.1 Java中集合与数...
Java 容器 - 一文详解HashMap
Map 类集合 Java Map类集合，与Collections类集合存在很大不同。它是与Collection 类...
Collection 集合类
Collection 集合类 java.util包中提供了一些集合类，这些集合类又称为容器；集合类和数组的区别在于...
Java集合类-集合类图谱
数据结构在计算机知识体系中的重要性无需赘言，Java的jdk的集合类正是学习数据结构的很好素材。如果能把jdk的集...
那些年我们追过的Java面试之集合类、异常处理
标签：Java面试、集合类、异常处理 2017/05/09 09:36 三.Java集合类 10.Java集合类框...
函数的定义和调用
3.1 创建集合 kotlin没有采用自己的集合类，而是采用的标准的java集合类。在java集合类的基础上新增了...