Java容器-集合

目录

1.Java容器概述

2.集合框架

3.Collection接口中的方法使用

4.iterator()

5.List接口

2.ArrayList、LinkedList、Vector相同点

3.不同点

1.ArrayList

2.LinkedList

3.Vector

4.Vector源码分析

5.ArrayList源码分析

6.LinkedList源码分析

6.List中的常用方法

7.区分remove删除的是元素还是索引

8.Set接口存在三个主要的实现类

1.HashSet

2.LinkedHashSet

3.TreeSet

4.如何理解Set的无序、不可重复特性(以HashSet为例)

5.set中添加元素的过程(以HashSet为例)

6.HashSet底层

7.要求

9.LinkedHashSet的使用

10.TreeSet()的使用

11.Map接口

1.HashMap

2.LinkedHashMap

3.TreeMap

4.Hashtable

5.Properties

12.Map的键与值

13.HashMap的底层实现原理

1.以jdk7说明

2.jdk8和jdk7的不同

3.HashMap的默认值

14.Map接口中常用的方法

15.遍历Map的方法

16.TreeMap

17.Collections工具类

19.Collection和Collections的区别

---

1.Java容器概述

1.集合、数组都是对多个数据进行存储的结构，简称java容器。

        此时的存储：主要是内存层面的存储，不涉及到持久化(硬盘方面)的存储

2.数组在存储多个数据方面的特点：

        一旦初始化后，长度就确定了，元素的类型也确定了；

3.数组存储多个数据方面的缺点：

      1.初始化后，其长度无法修改；

      2.数组中提供的方法极其有限，对于增删改查操作不方便，效率不高；

      3.获取数组中实际元素个数的需求，没有现成的方法可用；

       4.数组存储数据的特点：有序、可重复；对于无序、不可重复的需求，不能满足。

2.集合框架

1.Collection接口：单列集合，存储一个一个的对象；分为两大类

        List接口：存储有序的、可重复的数据；主要实现类：ArrayList,LinkedList,Vector

        Set接口：存储无序的、不可重复的数据；主要实现类:HashSet,LinkedHashSet,TreeSet

2.Map接口：双列集合，存储一对(key-value)的数据

        主要实现类：HashMap，LinkedHashMap，TreeMap，Hashtable，Properties

3.Collection接口中的方法使用

        1.使用多态造实现类对象赋给Collection集合对象；

        2.add(E e)：将元素添加到集合中

        3.size()：获取添加元素的个数

        4.addAll(Collection coll)：添加一个集合；

        5.isEmpty():判断当前集合是否为空

        6.clear()：清空集合元素

        7.contains(O o)：判断当前集合中是否包含o

        8.containsAll(Collection coll)：判断形参coll中所有元素是否都存在于当前集合中

        9.remove(Object o)：删除obj数据

        10.removeAll(Collection c)：删除c中包含的所有元素；获取与c集合之间的差集

        11.retainAll(Collection c)：获取与c集合之间的交集

        12.equals(Object o)：判断两个集合所有的元素是否相同，是返回true

        13.hashCode()：调用集合的哈希值

        14.toArray()：集合转化为数组

        15.将数组转换为集合：Arrays.asList(String[])

        注意：包装类数组与基本数据类型数组的区别

        若写为一个基本数据类型的数组则为一个元素，而不是识别为数组；写成包装类就会识别为数组中的多个元素。

        Iterator iterator = c.iterator();//hasNext()：判断是否还有下一个元素while (iterator.hasNext()) {//next()：两个作用：指针下移；返回下移以后的集合位置上的元素System.out.println(iterator.next());}

重要：add和contains方法调用的是obj对象所在类的equals()方法；若未重写即为false；因此向Collection的接口实现类的对象中添加数据obj时，要求obj所在类要重写equals()方法。

4.iterator()

返回Iterator接口的实例，用于遍历集合元素；

        1.使用hasNext()+next()方法。使用next()时指针下移，并将下移后对应的集合元素返回。

        2.集合对象每次调用hasNext()都会得到一个全新的迭代器对象，默认游标都在集合第一个元素之上。

        Iterator iterator = c.iterator();//hasNext()：判断是否还有下一个元素while (iterator.hasNext()) {//next()：两个作用：指针下移；返回下移以后的集合位置上的元素System.out.println(iterator.next());}

        3.内部定义了remove()方法；删除遍历后集合中的元素，此方法不同于集合中调用的remove；

        4.jdk5.0后使用foreach，用于遍历集合、数组；也叫做增强for循环

ArrayList a = new ArrayList();
//增强for循环
for(Object obj : a){System.out.println(obj);
}//for遍历
for (int i = 0; i < a.size(); i++) {System.out.println(a.get(i));
}//iterator迭代器
Iterator iterator = a.iterator();
while(iterator.hasNext()){System.out.println(iterator.next());
}

5.List接口

看作是数组的替换，动态数组

1.存储有序的、可重复的数据；有三个实现类ArrayList、LinkedList、Vector

2.ArrayList、LinkedList、Vector相同点

         三个类都实现了List接口；存储数据都有序可重复。

3.不同点

1.ArrayList

        作为List接口的主要实现类；线程不安全，执行效率比较高；底层使用object[ ]存储。适合查找元素，复杂度较低；不适合插入、删除操作。

2.LinkedList

        对于频繁的插入、删除操作，使用此类效率比ArrayList高，底层使用双向链表存储；不适合查找元素，复杂度较高。

3.Vector

        作为List接口中的古老实现类，线程安全，效率比较低；底层使用object[ ]存储。

4.Vector源码分析

        jdk7和idk8中都是通过Vector()构造器创建对象，底层都创建了长度为10的数组；

        在数组容量不够需要扩容方面，默认扩容为原来的数组长度的2倍。

 //源码public Vector() {this(10);}

5.ArrayList源码分析

1.jdk 7情况下

ArrayList List = new ArrayList();//源码
private static final int DEFAULT_CAPACITY = 10;

        此时：底层创建了长度是10的object[ ]数组elementData

List.add(123);//elementDatale[0] = new Integer(123);

        此时：elementDatale[0] = new Integer(123);
        若：List.add()添加到第十一次：

List.add(11);

        此时：若此次的添加导致底层eLlementData数组容量不够，则扩容。默认情况下，扩容为原来的容量的1.5倍，同时需要将原有数组中的数据复制到新的数组中
结论:建议开发中使用带参的构造器:

ArrayList list = new ArrayList(int capacity)

2.jdk 8中ArrayList的变化:

ArrayList List = new ArrayList();
​
//源码transient Object[] elementData;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

        此时：底层创建了bject[ ]数组，而elementData初始化为{}，说明此时的elementData并没有创建
若调用

List.add(123);//elementDatale[0] = new Integer(123);

    //源码public boolean add(E e) {ensureCapacityInternal(size + 1);  // Increments modCount!!elementData[size++] = e;return true;}private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}private static int calculateCapacity(Object[] elementData, int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);}return minCapacity;}private static final int DEFAULT_CAPACITY = 10;

        此时：第一次调用add()，add()调用底层ensureCapacityInternal()方法，底层传入的最小数组容量为：calculateCapacity(elementData, minCapacity)，calculateCapacity()方法返回的是DEFAULT_CAPACITY = 10(没有扩容的情况下)；之后将并将数据123添加到elementData
后续的添加和扩容操作与idk 7 一样。

2.3小结:

        jdk7中的ArrayList的对象的创建类似于单例模式中的饿汉式，而idk8中的ArrayList的对象的创建类似于单例的懒汉式，延迟了数组的创建，节省内存。

6.LinkedList源码分析

LinkedList list = new LinkedList();

        此时：内部声明了Node类型的first和last性，默认值为null

transient Node<E> first;//null
transient Node<E> last;//null

        向list中封装数据： 

List.add(123);

        此时：直到往list中封装数据后，开始创建Node对象，将123封装到Node中。
其中，Node定义为:

    private static class Node<E> {E item;Node<E> next;Node<E> prev;Node(Node<E> prev, E element, Node<E> next) {this.item = element;this.next = next;this.prev = prev;}}

LinkedList 对数据的封装，就是说把数据封装成Node 对象；当往list封装数据后，创建Node对象，并根据此时的具体情况创建prev和next属性；

        prev属性表示previous-上一个：若此时的元素不是第一个元素，则指向上一个节点

        next属性表示下一个：指向下一个节点

        item属性：保存了当前节点的值

这几个属性体现了LinkedList的双向链表的说法

6.List中的常用方法

加入了调用索引的方法

        1.add(int index,Object o);在index插入o

        2.addAll():在index加入一个集合中的所有元素

        3.get():获取索引处元素

        4.indexOf(Object o):返回o在集合中首次出现位置(若找不到就返回-1)

        5.lastIndexOf(Object o):返回o在集合中末次出现位置(不存在就返回-1)

        6.remove(int index):删除指定索引处元素

        7.set(inded，o):设置指定索引位置元素

        8.subList(from,toIndex):返回指定位置集合

7.区分remove删除的是元素还是索引

        在List方法中提供了重载的remove删除该索引处元素；

        而Collection中删除的是该元素(若Collection无序就不存在索引)

8.Set接口存在三个主要的实现类

set接口中没有额外定义新的方法，使用的都是Collection中声明过的方法。

1.HashSet

        set接口的主要实现类；是线程不安全的；可以存储null值；

2.LinkedHashSet

        作为HashSet的子类，遍历内部数据时，可以按照添加的顺序遍历

3.TreeSet

        可以按照添加的对象指定属性，进行排序。

4.如何理解Set的无序、不可重复特性(以HashSet为例)

       无序性：不等于随机性；存储的数据在底层数组中并非按照数组索引的顺序添加，而是根据数据的哈希值决定.添加时是无序的

      不可重复性：保证添加的元素按照equals()判断时，不能返回true；即相同的元素只能添加一个。

5.set中添加元素的过程(以HashSet为例)

        向HashSet中添加元素a，首先调用a所在类的hashCode方法，计算a的哈希值，此哈希值接着通过某种算法计算出a在HashSet底层数组中的存放位置(即索引位置)，判断数组位置上是否已经有元素，如果此位置没有其他元素，则a添加成功；若此位置有其他元素b(或以链表形式存在的多个元素)，则比较a与b的hash值，若哈希值不同，则a添加成功，若哈希值相同，则调用a所在类的equals()方法，若equals返回true，则a添加失败，若返回false，则a添加成功。

6.HashSet底层

        数组+链表形式。

7.要求

        向Set中添加的数据，其所在的类一定要重写hashCode()和equals();重写的hashCode()和equals()尽可能保持一致性：相等的对象必须具有相等的散列码(即哈希值)

9.LinkedHashSet的使用

        1.LinkedHashSet的使用作为HashSet的子类，在添加数据的同时，每个数据还维护了两个引用，记录此数据前一个数据和后一个数据。

        2.优点：对于频繁的遍历操作，效率高于HashSet()

10.TreeSet()的使用

        1.向TreeSet中添加的数据，要求是相同类的对象，不能添加不同类的对象。

        2.两种排序方式：自然排序(实现Comparable接口)、定制排序(comparator)

        3.自然排序中，比较两个对象是否相同的标准为compareTo()方法返回0；不再是equals()方法

        4.定制排序中，比较两个对象是否相同的标准是compare()返回0，不再是equals()方法

    //Comparable 自然排序
public class Person implements Comparable {@Overridepublic int compareTo(Object o) {if (o instanceof Person){Person oo = (Person)o;return this.age - (oo.getAge());}else {throw new RuntimeException("输入的类型不一致");}}
}//comparator：定制排序Set set3 = new TreeSet(new Comparator() {@Overridepublic int compare(Object o1, Object o2) {if (o1 instanceof Person && o2 instanceof Person){Person oo1 = (Person)o1;Person oo2 = (Person)o2;return oo1.getName().compareTo(oo2.getName());}else{throw new RuntimeException("输入的类型不一致。");}}});

11.Map接口

1.HashMap

        Map的主要实现类；线程不安全的，效率高；可以存储null的key和value。

        底层：jdk7之前：数组+链表

                   jdk8：数组+链表+红黑树

2.LinkedHashMap

        保证在遍历map元素时，可以按照添加的顺序实现遍历。

        原因：在原有的HashMap底层结构基础上，添加了一对指针，指向前一个和后一个元素。

                   对于频繁的遍历操作，效率高于HashMap

3.TreeMap

        可以按照添加的key- value进行排序，实现排序遍历。此时考虑key的自然排序或定制排序。底层使用红黑树。

4.Hashtable

        作为古老的实现类；线程安全的，效率低；不能存储null的key和value

5.Properties

        常用来处理配置文件。key和value都是String类型。

12.Map的键与值

        1.Map当中的key是无序的不可重复的，是使用Set存储的；values也是无序的，但是可以重复，使用Collection存储；而实际上使用put(key,value)时向Map中存储的是一个Entry对象，该对象有两个属性，一个是key，另一个是value，且Entry也是使用Set存储的，无序不可重复。

        2.以HashMap为例，key所在的类必须重写equals()和hashCode()方法；values所在的类要重写equals()方法。

        3.hashCode方法主要是存的时候效率高一点，在查找值时方便一点。

13.HashMap的底层实现原理

1.以jdk7说明

HashMap被实例化后，底层创建长度为16的一维数组Entry[ ] table。

        调用put(key1,value1)后，会先调用key1所在类的hashCode()方法计算key1的哈希值，此哈希值经过计算后得到Entry数组在底层的存放位置：

                若此位置为空，则key1-value1添加成功

                若此位置不为空，则比较key1和该位置元素(假设为key2-value2)的哈希值：

                        若key1的哈希值和该元素key2哈希值都不相同，则key1-value1添加成功

                        若key1的哈希值和该元素key2哈希值相同，则比较key1所在类的equals(key2)方法

                                若equals()返回false，则key1-value1添加成功

                                若equals返回true，则value1将value2进行替换

2.jdk8和jdk7的不同

        1.new HashMap()后不会创建长度为16的数组Entry[ ] table

        2.jdk8 底层使用Node[ ]，而不是Entry[ ] 

        3.调用put方法时，底层创建长度为16的数组

        4.jdk7底层结构为数组+链表；

           jdk8中的底层结构为数组+链表+红黑树；当数组的某一个索引位置元素以链表形式存在的数据个数大于8且当前数组长度大于64，则将该索引位置上的所有数据改为使用红黑树存储。

       

3.HashMap的默认值

HashMap的默认容量：16

HashMap的加载因子：0.75

扩容的临界值：容量*加载因子：16*0.75=12

链表形式存在的数据大于8:转化为红黑树

Node被树化时最小的hash表容量：64

14.Map接口中常用的方法

        1.put()：添加key- value的Node对象

        2.putAll(Map m):将m中所有Node添加

        3.remove(key):删除指定key的键值对

        4.clear():清空当前map

        5.get(key):获取key的value

        6.containsKey(key):是否包含kry

        7.contains Value()

        8.size():Node个数

        9.isEmpty()

        10.equals():两个Map是否相同

15.遍历Map的方法

        1.遍历所有的key：keySet()

        2.遍历所有的value：values()

        3.遍历所有的key-value():entrySet()

代码示例：

    @Testpublic void test(){//1.遍历keyMap map = new HashMap();map.put("Tom",12);map.put("Jerry",45);map.put("Mary","AA");System.out.println(map);Set set = map.keySet();Iterator iterator = set.iterator();while(iterator.hasNext()){System.out.println(iterator.next());}//2.遍历valueCollection c = map.values();System.out.println(c);for (Object o : c){System.out.println(o);}System.out.println("-------------------------------");//3.遍历NodeSet s1 = map.entrySet();Iterator iterator1 = s1.iterator();while(iterator1.hasNext()){Object obj = iterator1.next();Map.Entry entry = (Map.Entry)obj;System.out.println(entry.getKey() + " === " + entry.getValue());}}

16.TreeMap

        1.向TreeMap中添加key-value，要求key必须由同一个类创建的对象

        2.因为要按照key进行排序：自然排序、定制排序

17.Collections工具类

操作Collection和Map的工具类

        1.Collections类中提供了synchronizeXxx():该方法可以使指定集合包装成线程同步的集合，从而可以解决多线程并发访问集合时的线程安全问题。

        2.reverse(List):反转list中元素顺序

        3.shuffle():对集合元素随机排序

        4.sort():根据自然顺序对指定list元素升序

        5.swap():将制定list中的i元素交换为j元素

        6.frequency():返回指定集合元素出现次数

        7.copy(i,j):将j复制到i

19.Collection和Collections的区别

        Collection是单列集合的接口，子接口有List和Set；

        Collections是操作Collection和Map的工具类。