集合

发布于 2022-04-09  144 次阅读


认识集合

数组的不足

数组

1.长度开始时必须指定,而且一旦指定,不能更改

2.保存的必须为同一类型的元素

3.使用数组进行增加元素的示意代码-比较麻烦

集合

1.可以动态保存任意多个对象,使用比较方便

2.提供了一系列方便的操作对象的方法:add、remove、set、get等

3.使用集合添加,删除新元素的示意代码-简洁了

集合体系图

双列

单列

Collection接口和常用方法

Collection接口实现类的特点

1.collection实现子类可以存放多个元素,每个元素可以是object

2.有些Collection的实现类,可以存放重复的元素,有些不可以

3.有些Collection的实现类,有些是有序的(List),有些不是有序的(Set)

4.Collection接口没有直接的实现子类,是通过它的子接口Set和List来实现的

Collection接口和常用方法

Collection接口常用方法,以实现子类

1.add:添加单个元素

2.remove:删除指定元素

3.contains: 查找元素是否存在

4.size:获取元素个数

5.isEmpty:判断是否为空

6.clear:清空

7.addAll:添加多个元素

8.containsAll : 查找多个元素是否存在

9.removeAll:删除多个元素

  public static void main(String[] args) {
        Collection col=new ArrayList();
        col.add("小龙女");
        col.add(100);
        col.add(true);
        col.add("小龙女");
        col.add(new Integer(10));

        col.remove("小龙女");
        boolean contains=col.contains(10);
        System.out.println(col.size());
        System.out.println(col.isEmpty());
        col.clear();

        Collection c=new ArrayList();
        c.add("AA");
        c.add("CC");
        c.add("BB");
        col.addAll(c);

        Collection c2=new ArrayList();

        c2.add("CC");
        c2.add("AA~");
        boolean containsAll=col.containsAll(c2);//col.removeAll

    }

Collection接口遍历元素方式1-使用Iterator(迭代器)

1.Iterator对象称为迭代器,主要用于遍历Collection集合中的元素

2.所有实现了Collection接口的集合类都有一个iterator()方法,用以返回一个实现了Iterator接口的对象,即可以返回一个迭代器

3.Iterator 仅用于遍历集合,Iterator本身不存放对象。

迭代器的执行原理

Iterator iterator = coll.iterator();//得到一个集合的迭代器

//hasNext():判断是否还有下一个元素

while(iterator.hasNext()){

//next():1指针下移 2将下移以后集合位置上的元素返回

System.out.println(iterator.next());

}

注意:在调用it.next()方法之=之前必须调用it.hasNext()进行检查。若不调用,且下一条记录无效,直接调用it.next()会抛出NoSuchElementException异常。

   public static void main(String[] args) {
    Collection col=new ArrayList();

    col.add(new Book("三国演义","罗贯中",10.1));
    col.add(new Book("小李飞刀","古龙",5.1));
    col.add(new Book("红楼梦","曹雪芹",34.6));

        Iterator iterator = col.iterator();
        while (iterator.hasNext()) {
            Object next = iterator.next();
            System.out.println(next);
        }
        //再次遍历需要重置迭代器
        iterator =col.iterator();
    }

class Book{
    private String name;
    private String author;
    private double num;

    public Book(String name, String author, double num) {
        this.name = name;
        this.author = author;
        this.num = num;
    }

    @Override
    public String toString() {
        return "Book{" +
                "name='" + name + '\'' +
                ", author='" + author + '\'' +
                ", num=" + num +
                '}';
    }
}

增强for循环

可以代替iterattor迭代器,特点:增强for就是简化版的iterator,本质一样,只能用于遍历集合或数组

基本语法

for(元素类型 元素名:集合名或数组名){

访问元素

}

List接口的常用方法

List集合里添加了一些根据索引来操作集合元素的方法

1.void add(int index,Object ele):在index位置插入ele元素

2.boolean addAll(int index,Collection eles):从index位置开始将eles中的所有元素添加进来

3.Object get(int index):获取指定index位置的元素

4.int indexOf(Objct obj):返回obj在集合中首次出现的位置

5.int lastlndexOf(Object obj):返回obj在集合中末次出现的位置

6.Object remove(int index):移除指定index位置的元素,并返回此元素

7.Object set(int index,Object ele):设置指定index位置的元素为ele,相当于是替换

8.List subList(int fromlndex,int tolndex):返回从fromlndex到toIndex位置的子集合

List的三种遍历方式

方式一:使用iterator

Iterator iter=col.iterator()

while(iter.hasNext()){

Object o=iter.next();

}

2.方式二:使用增强for

for(Object‘ o:col){}

3.方式三:使用普通for

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

Object object =list.get(i);

System.out.println(object);

}

ArrayList的注意事项

1.permits all elements,including null,ArrayList 可以加入null,并且多个

2.ArrayList 是由数组来实现数据存储的

3.ArrayList基本等同于Vector,除了ArrayList是线程不安全(执行效率高),在多线程情况下,不建议使用ArrayList

ArrayList的底层操作机制源码分析

1.ArrayLIst中维护了一个object类型的数组elementData.transient Object[] elementData;

2.当创建对象时,如果使用的是无参构造器,则初始elementData容量为0(jdk7为10)

3.当添加元素时:先判断是否需要扩容,如果需要扩容,则调用grow方法,否则直接添加元素到合适位置

4.如果使用的是无参构造器,如果第一次添加,需要扩容的话,则扩容elementData为10,如果需要再次扩容的话,则扩容elementData为1.5倍

5.如果使用的是指定容量capacity的构造器,则初始elementData容量为capacity

6.如果使用的是指定容量capacity的构造器,如果需要扩容,则直接扩容elementData为1.5倍

Vector低层结构和源码剖析

Vetor的基本介绍

1.Vetor类的定义说明

   public class Vector<E>
        extends AbstractList<E>
        implements List<E>,RandomAccess,Cloneable,Serializable

2.Vetor底层也是一个对象数组,protected Object[] elementData;

3.Vetor是线程同步的,即线程安全Vetor类的操作方法带有Synchronuzed

public synchronized E get(int index){
    if(index>=elementsCount){
        throw new ArraylndexOutofBoundsException(index);
        return elementData(index);
    }
        }

4.在开发中,需要线程同步安全时,考虑使用Vector

Vector和ArrayList的比较

底层结构版本线程安全(同步)效率扩容倍数
ArrayList可变数组jdk1.2不安全,效率高如果有参构造1.5倍
如果是无参
1.第一次10
2.第二次开始按1.5倍扩容
Vector可变数组jdk1.0安全,效率不高如果是无参,默认10
满后就按2倍扩容
如果指定大小,
则每次按2倍扩容

LinkedList底层结构

LinkedLIst的全面说明

1.LinKedList实现了双面链表和双端队列特点

2.可以添加任意元素(元素可以重复),包括null

3.线程不安全,没有实现同步

LinkedList的底层操作机制

1.LinKedList底层维护了一个双向链表

2.LinkedList中维护了两个属性first和last分别指向 首节点和尾节点

3.每个节点(Node对象),里面又维护了prev,next,item三个属性,其中通过prev指向前一个,通过next指向后一个节点。最终实现双向链表

4.所以LinKedList的元素的添加和删除,不是通过数组完成的,相对来说效率较高。

5.模拟一个简单的双向链表;

 public static void main(String[] args) {
        Node tom = new Node("tom");
        Node vi = new Node("Vi");
        Node haoye = new Node("haoye");
    //tom-vi-haoye
    tom.next=vi;
    vi.next=haoye;
    //haoye-vi-tom
    haoye.pre=vi;
    vi.pre=tom;

        Node first=tom;//让first引用指向tom,就是双向链表的头节点
        Node last=haoye;//last引用指向haoye,就是双向链表的尾节点

        while(true){
            if(first==null){
                break;
            }

            System.out.println(first);
            first=first.next;
        }
    }

class Node{
    public Object item;//真正存放数据
    public Node next;//指向后一个节点
    public Node pre;//指向前一个节点

    public Node(Object name) {
        this.item = name;
    }

    @Override
    public String toString() {
        return "name:" + item;
    }
}

ArrayList和LinkedKist的比较

底层结构增删的效率改查的效率
ArrayList可变数组较低的数组扩容较高
LinkedList双向链表较高,通过链表追加较低

如何选择ArrayList和LinkedList:

1.如果我们改查的操作多,选择ArrayList

2.如果我们增删的操作多,选择LinkedList

3.一般来说,在程序中,80%-90%都是查询,因此大部分下会选择ArrayList

4.在一个项目中,根据业务灵活选择,也可以这样,一个模块使用的是ArrayList,另外一个模块是LinkedList。

Set接口和常用方法

Set接口基本介绍

1.无序(添加和取出的顺序不一致),没有索引

2.不允许重复元素,所以最多包含一个null

3.JDK APl中Set接口的实现类有:

Set接口和常用方法

Set接口的常用方法

和List接口一样,Set接口也是Collection的子接口,因此,常用方法和Collection接口一样

Set接口的遍历方式

同Collection的遍历方式一样,因为Set接口是Collection接口的子接口

1.可以使用迭代器

2.增强for

3.不能使用索引的方式来获取

HashSet的全面说明

1.HashSet实现了Set接口

2.HashSet实际上是HashMap

public HashSet(){

map = new HashMap<>();

}

3.可以存放null值,但是只能有一个null

4.HashSet不保证元素是有序的,取决于hash后,再确定索引的结果

5.不能有重复元素/对象

HashSet底层机制说明

1.HashSet底层是HashMap

2.添加一个元素时,先得到hash值-会转成->索引值

3.找到存储数据表table,看这个索引位置是否已经存放的有元素

4.如果没有,直接直接加入

5.如果有,调用equals比较,,如果相同,就放弃添加,如果不相同,则添加到最后

6.在java8中,如果一条链表的元素个数到达TREEIFY_THRESHOLD(默认是8),并且table的大小>=MIN_TREEIFY_CAPACITY(默认64)就会进化树化(红黑树)

1.先获取元素的哈希值(hashCode方法)

2.对哈希值进行运算,得到一个索引值为要存放在哈希表中的位置号

3.如果该位置上没有其他元素,则直接存放

4.如果该位置上已经有其他元素,则需要进行equals判断,如果相等,则不再添加,如果不相等,则以链表的方式添加

LinKedHashSet说明

1.LinKedHashSet是HashSet的子类

2.LinKedHashSet 底层是一个LinKedHashMap,底层维护了一个数组+双向链表

3.LinKedHashSet 根据元素的hashCode 值来决定元素的存储位置,同时使用链表维护元素的次序,这使得元素看起来是以插入顺序保存的。

4.LinKedHashSet 不允许添重复元素

机制

1.在LinKedHashSet中维护了一个hash表和双向链表(LinKedHashSet 有head和tail)

2.每一个节点有pre和next属性,这样可以形成双向链表

3.在添加一个元素时,先求hash值,在求索引,确定该元素在hashtable的位置,然后将添加的元素加入到双向链表(如果已经存在,不添加[原则和hashset])

tail.next = newElement//简单指定

newElement.pre = tail

tail = newEelment;

4.这样的话,我们遍历LinedHashSet 也能确保插入顺序和遍历顺序一致

Map接口而常用方法

jdk8的Map接口的特点

1.Map与Collection并列存在。用于保存具有隐射关系的数据:Key-Value

2.Map中的Key和Value可以是任何引用类型的数据,会封装到HashMap$Node对象中

3.Map中的Key不允许重复

4.Map中的Value可以重复

5.Map的Key可以为null,Value也可以为null,注意Key为null,只能有一个,Value为null,可以多个

6.常用String类作为Map的key

7.key和value之间存在单向一对一关系,即通过指定的Key总能找到对应的Value

8.Map存放数据的Key-value,一对k-v是放在Node中的,有因为Node实现了Entry接口。

Map接口常用方法

1.put:添加

2.remove:根据键删除映射关系

3.get:根据键获取值

4.size:获取元素个数

5.isEmpty:判断个数是否为0

6.clear:消除

7.containsKey:查找键是否存在

例子

    public static void main(String[] args) {
        Map map = new HashMap();
        map.put("dd",new Book("",100));
        map.put("dd","wd");
        map.put("qx","ww");
        map.put("uu","ww");
        map.put("i",null);
        map.put(null,"yu");
        map.put("vv","c");

        Object object = map.get("dd");

        map.remove("vv");
        System.out.println(map);

        boolean containsKey = map.containsKey(null);
        System.out.println(containsKey);
        System.out.println(map.containsValue("yu"));

        System.out.println(map.size());
        System.out.println(map.isEmpty());
        map.clear();

    }

class Book{
    private String name;
    private int age;

    public Book(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public String toString() {
        return "Book{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

Map接口遍历方法

1.containsKey:查找键是否存在

2.KeySet:获取所有的键

3.entrySet:获取所有关系

4.values:获取所有的值

   public static void main(String[] args) {
        HashMap map = new HashMap();
        map.put("dd","e");
        map.put("ww","er");
        map.put("yu","dw");
        map.put("i","nv");
        System.out.println("--获取键遍历--");
        Set keys = map.keySet();
        Iterator iterator = keys.iterator();
        while (iterator.hasNext()) {
            Object key =  iterator.next();
            Object value = map.get(key);
            System.out.println(key+"-"+value);
        }

        System.out.println("--超级for--");
        for(Object key : keys) {
            System.out.println(key+"-"+map.get(key));
        }

        System.out.println("--取出所有的value--");
        Collection values = map.values();
        for(Object value : values){
         System.out.println(value);
        }

        Iterator iterator1 = values.iterator();
        while (iterator1.hasNext()) {
            Object value = iterator1.next();
            System.out.println(value);
        }

        System.out.println("--entrys获取所有关系--");
        Set entrys = map.entrySet();//key-value,超级for 迭代器都可以使用
        for(Object entry:entrys){
            Map.Entry e = (Map.Entry)entry;
            Object key = e.getKey();
            Object value = e.getValue();
            System.out.println(key+"-"+value);
        }
    }

HashMap小结

1.Map接口的常用实现类:HashMap、Hashtable和properties

2.HashMap是Map接口使用频率最高的实现类

3.HashMap是以Key-val对的方式来存储数据

4.Key不能重复,但是是值可以重复,允许使用null键和null值

5.如果添加相同的key,则会覆盖原来的Key-val,等同于修改(Key不会替换,val会替换)

6.与HashSet一样,不保证映射的顺序,因为底层是以hash表的方式来存储的

7.HashMap没有实现同步,因此是线程不安全的

HashTable的基本介绍

1.存放的元素是键值对:即k-v

2.hashrable的键和值都不能为null

3.hashTable使用方法基本上和HashMap一样

4.hashTable是线程安全的,hashMap是线程不安全的

properties

1.Propertise类继承自Hashtable类并且实现了Map接口,也是使用一种键值对的形式来保存数据

2.他的使用特点和Hashtable类似

3.Properties还可以用于从xxx.properties文件中,加载数据到properties类对象,并进行读取和修改

4.说明:工作后xxx.properties文件通常作为配置文件

什么时候使用哪种集合

1.先判断存储的类型(一组对象[单列]或一组键值对[双列])

2.一组对象:Collection接口

允许重复:List

增删多:LinKedList[底层维护了一个双向链表]

改查多:ArrayList[底层维护 Object类型的可变数组]

不允许重复:Set

无序:HashSet[底层是HashMap,维护了一个哈希表 即(数组+链表+红黑树)]

排序:TreeSet

插入和取出顺序一致:LinKedHashSet,维护数组+双向链表

3.一组键值对:Map

链无序:HashMap[底层是:哈希表:哈希表 jdk7:数组+链表+红黑树]

键无序:TreeMap

键插入和取出顺序一致:LinKedHashMap

读取文件 Properties

TreeSet

public static void main(String[] args) {
        TreeSet treeSet = new TreeSet(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                  return ((String)o1).compareTo((String)o2);
//                  return ((String)o1).length()-((String)o2).length();
            }
        });
treeSet.add("ww");
treeSet.add("www");
treeSet.add("wwww");
System.out.println(treeSet);
        };

TreeMap

    public static void main(String[] args) {
        TreeMap treeMap = new TreeMap(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                return ((String)o1).compareTo((String)o2);
//                  return ((String)o1).length()-((String)o2).length();
            }
        });
        treeMap.put("w",1);
        treeMap.put("ww",2);
        treeMap.put("www",3);
System.out.println(treeMap);
        };

Collections工具类

Collections工具类介绍

1.Collections是一个操作Set、List和Map等集合的工具类

2.Collections中提供了一系列静态的方法对集合元素进行排序、查询和修改等操作

排序操作:(均为static方法)

1.reverse(List):反转List中元素的顺序

2.shuffle(List):对List集合元素进行随机顺序

3.sort(List):根据元素的自然顺序对指定List集合元素按升序排序

4.sort(List,Comparator):根据指定的Comparator产生的顺序对List集合元素进行排序

5.swap(List,int,int):将指定list集合中的i处元素和j处元素进行交换

查找、替换

1.object man(Collection):根据元素的自然顺序,返回给定集合中的最大元素

2.object man(Collection,Comparator):根据Comparator指定的顺序,返回给定集合中的最大元素

3.object min(Collection):

4.object man(Collection,Comparator):

5.int frequency(Collection,Object):返回指定集合中指定元素的出现次数

6.void copy(List dest,List src):将src中的内容复制到dest中

7.boolean replaceAll(List list,ObjectoldVal,object newVal):使用新值替换List对象的所有旧值