美文网首页
java高级-集合collection/map

java高级-集合collection/map

作者: 董亚 | 来源:发表于2021-01-14 11:28 被阅读0次

    前言

    类似map、list、set等集合经常在项目中使用,今天在这里做个总结

    为什么要有集合

    java中基础的数据存储为数组,很多集合的底层逻辑就是基于数组实现的,对于数组他的优缺点很明显:

    • 缺点
      一旦初始化数组长度固定,无法自动扩容,数据可以存储重复的数据
      删除/插入数据慢
    • 优点
      查询、修改速度快

    数组的优缺点很明显,但是对于一些高级应用还是欠缺一些功能,所有就诞生了集合,集合分为collection和map两个体系,下面将分开描述这两个体系

    collection

    collection的继承树


    image.png

    上述图中这是描述了简单的继承关系,复杂的继承关系可以查看一些api文档
    collection的方法描述


    image.png

    其中大部分方法不用描述,重点描述下iterator(),removeIf(),stream()这几个方法
    iterator():返回一个迭代器,方便对集合中的数据遍历
    removeIf():顾名思义就是有条件性的删除(删除满足给定Predicate(谓词)的此集合的所有元素),
    stream():返回一个以此集合做为源的顺序流,可以根据此流来过滤以产生用户需要的流或者集合
    removeIf()stream()方法都会涉及一个接口Predicate,

    Predicate的使用参考

    public static void main(String[] args) {
            List<String> list = new ArrayList<>();
            list.add("a");
            list.add("1");
            list.add("a");
            list.add("2");
            list.removeIf(new Predicate<String>() {
                @Override
                public boolean test(String s) {
                    return "a".equals(s);
                }
            });
            System.out.println(list);
        }
    

    当集合中的数据与"a"相等时则删除

    [1, 2]
    

    可以看到,使用Predicate删除集合中的数据是很方便的,不用使用iterator遍历删除

    public static void main(String[] args) {
            List<String> list = new ArrayList<>();
            list.add("a");
            list.add("1");
            list.add("a");
            list.add("2");
            List list1 = list.stream().filter(new Predicate<String>() {
                @Override
                public boolean test(String s) {
                    return "a".equals(s);
                }
            }).collect(Collectors.toList());
            System.out.println(list1);
        }
    
    [a, a]
    

    使用stream流操作可以根据Predicate筛选出符合条件的集合

    List

    list应该被经常在java中使用,常用的子集有ArrayList、LinkedList、vector

    • ArraryList
      • 相信ArraryList中的常用方法大家都很熟悉,下面对几个不常用的方法做个介绍
        • indexOf(Object o):返回此集合中指定元素第一次出现的索引,如果不包含此元素则返回-1
        • lastIndexOf(Object o):返回此集合中指定元素最后一次出现的索引,如不包含返回-1
        • trimToSize:修改这个集合的容量为当前集合的实际大小,最小化集合实例的存储
        • sort(Comparator<? super E> c):使用提供的comparator对此列表进行排序,并返回排序后的集合
        • listIterator():返回一个listIterator对象,Iterator只能单向遍历,而listIterator可以双向遍历,listIterator继承Iterator并且添加一些双向操作,例如:
          • add(E e):将制定的元素插入列表,插入位置为迭代器当前位置之前
          • set(E e):迭代器返回的最后一个元素替换参数e
          • hasPrevious(E e):迭代器当前位置,是否有前序元素
          • previous(E e):返回列表中的上一个元素,并向后移动光标位置
          • previous(E e):返回列表中的上一个元素,并向后移动光标位置
        • retainAll(Collection<?> c):此列表中只保留参数集合中包含的元素,
    public static void main(String[] args) {
            List<String> list = new ArrayList<>();
            list.add("a");
            list.add("1");
            list.add("a");
            list.add("2");
    
            List list1 = new ArrayList();
            list1.add("a");
            list.retainAll(list1);
            System.out.println(list);
        }
    输出:[a, a]
    
    • LinkedList
      ArrayList的内部是由一个可扩容的数组实现的,而LinkedList则是类似c语言中的双向链表,其核心存储结构的私有静态类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;
            }
        }
    

    Node中的泛型对象e为实际存储的object,next和prev分别存储双向链表中的下一个节点和前一个节点,依次存储构成就构成了双向链表

    • ArraryList和LinkedList的优缺点区别:
      • 对于随机访问,ArraryList由于优于LinkedList,ArraryList可根据索引获取,而LinkedList则需要遍历移动指针去获取数据
      • 对于新增和删除数据,则LinkedList优于ArraryList,
    • LinkedList常用方法介绍:
      • peekFirst():获取第一个元素,为空则返回空
      • peekLast():获取最后一个元素,为空则返回空
      • pollFirst():获取第一个元素并删除
      • pollLast():获取最后一个元素并删除
      • pop():弹出队列中第一个元素并删除
        这些方法都是队列中常用的方法,还有一些常用方法是从List中实现的,具体就不一一描述了

    Queue(队列)

    • Queue与Deque的区别:
      • Deque:是Queue接口的子接口,为一个双向队列,双向队列是指该队列即能入队也能出队,如果将Deque限制只能从一端入队和出队,那么可实现栈的数据结构,对于栈而言,有入栈(push)和出栈(pop),遵循先进后出原则,由它衍生出的类有 LinkedBlockingDeque 、LinkedList、ArrayDeque等,当然这些类中也有些实现了Queue接口,所以这些类可以有队列的特性也可以用栈的特性,此接口包含的方法如下:


        image.png

        可以看到Deque中不仅包含可用于队列的add、poll、peek等方法,也包含用于栈的push和pop等方法

      • Queue:常用的队列模式,遵循先进先出原则,由他衍生出的类有LinkedBlockingQueue,ArrayDeque,ArrayBlockingQueue等。此接口包含的方法如下:


        image.png

    在具体的操作中可根据项目的实际需求来判定是要使用Queue下属子类(有些片面,主要是区分栈结构或者队列结构)或者使用Deque下属子类,(当然由于Deque是继承Queue的,所以都算是Queue的子类,但是Deque在Queue的基础上增加了栈的特性,所以继承了Deque的子类也具有栈的结构,同时具有Queue的队列特性,)

    set

    set存储的元素不可重复,且存储的元素无序,该集合中元素是否相等可重写hashCode和equals方法来判断,该接口的常用类有HashSet、TreeSet、LinkedHashSet等

    • HashSet


      image.png

      可以看到HashSet中并没有什么特殊的方法,基本都是从Set接口从实现的,值的一说的是,HashSet内部用于储存数据的是一个HashMap集合,换言之HashSet的实现原理是基于HashMap的;

    • TreeSet
      TreeSet是一个包含有序且没有重复元素的集合,通过TreeMap实现,TreeSet中包含一个"NavigableMap"类型的成员变量,实际上是一个TreeMap实例,TreeSet与HashMap最大的区别就是前者是有序的,后者是无序的;TreeSet用于存储元素时需要注意一点,因为treeMap值有序的,而这个有序并不是插入的顺序而是元素之前的比较顺序,所以存储的元素需要带有比较器(Comparable)或者在实例化TreeSet时传入比较器实例(Comparator),参考其构造方法,
      TreeSet方法介绍:参考
    package java.util;
    
    public class TreeSet<E> extends AbstractSet<E>
        implements NavigableSet<E>, Cloneable, java.io.Serializable
    {
        // 使用NavigableMap对象的key来保存Set集合的元素
        private transient NavigableMap<E,Object> m;
    
        //使用PRESENT作为Map集合中的value
        private static final Object PRESENT = new Object();
    
        // 不带参数的构造函数。创建一个空的TreeMap
        //以自然排序方法创建一个新的TreeMap,再根据该TreeMap创建一个TreeSet
        //使用该TreeMap的key来保存Set集合的元素
        public TreeSet() {
            this(new TreeMap<E,Object>());
        }
    
        // 将TreeMap赋值给 "NavigableMap对象m"
        TreeSet(NavigableMap<E,Object> m) {
            this.m = m;
        }
    
        //以定制排序的方式创建一个新的TreeMap。根据该TreeMap创建一个TreeSet
        //使用该TreeMap的key来保存set集合的元素
        public TreeSet(Comparator<? super E> comparator) {
            this(new TreeMap<E,Object>(comparator));
        }
    
        // 创建TreeSet,并将集合c中的全部元素都添加到TreeSet中
        public TreeSet(Collection<? extends E> c) {
            this();
            // 将集合c中的元素全部添加到TreeSet中
            addAll(c);
        }
    
        // 创建TreeSet,并将s中的全部元素都添加到TreeSet中
        public TreeSet(SortedSet<E> s) {
            this(s.comparator());
            addAll(s);
        }
    
        // 返回TreeSet的顺序排列的迭代器。
        // 因为TreeSet时TreeMap实现的,所以这里实际上时返回TreeMap的“键集”对应的迭代器
        public Iterator<E> iterator() {
            return m.navigableKeySet().iterator();
        }
    
        // 返回TreeSet的逆序排列的迭代器。
        // 因为TreeSet时TreeMap实现的,所以这里实际上时返回TreeMap的“键集”对应的迭代器
        public Iterator<E> descendingIterator() {
            return m.descendingKeySet().iterator();
        }
    
        // 返回TreeSet的大小
        public int size() {
            return m.size();
        }
    
        // 返回TreeSet是否为空
        public boolean isEmpty() {
            return m.isEmpty();
        }
    
        // 返回TreeSet是否包含对象(o)
        public boolean contains(Object o) {
            return m.containsKey(o);
        }
    
        // 添加e到TreeSet中
        public boolean add(E e) {
            return m.put(e, PRESENT)==null;
        }
    
        // 删除TreeSet中的对象o
        public boolean remove(Object o) {
            return m.remove(o)==PRESENT;
        }
    
        // 清空TreeSet
        public void clear() {
            m.clear();
        }
    
        // 将集合c中的全部元素添加到TreeSet中
        public  boolean addAll(Collection<? extends E> c) {
            // Use linear-time version if applicable
            if (m.size()==0 && c.size() > 0 &&
                c instanceof SortedSet &&
                m instanceof TreeMap) {
                //把C集合强制转换为SortedSet集合
                SortedSet<? extends E> set = (SortedSet<? extends E>) c; 
                 //把m集合强制转换为TreeMap集合
                TreeMap<E,Object> map = (TreeMap<E, Object>) m;
                Comparator<? super E> cc = (Comparator<? super E>) set.comparator();
                Comparator<? super E> mc = map.comparator();
                //如果cc和mc两个Comparator相等
                if (cc==mc || (cc != null && cc.equals(mc))) {
                //把Collection中所有元素添加成TreeMap集合的key
                    map.addAllForTreeSet(set, PRESENT);
                    return true;
                }
            }
            return super.addAll(c);
        }
    
        // 返回子Set,实际上是通过TreeMap的subMap()实现的。
        public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                                      E toElement,   boolean toInclusive) {
            return new TreeSet<E>(m.subMap(fromElement, fromInclusive,
                                           toElement,   toInclusive));
        }
    
        // 返回Set的头部,范围是:从头部到toElement。
        // inclusive是是否包含toElement的标志
        public NavigableSet<E> headSet(E toElement, boolean inclusive) {
            return new TreeSet<E>(m.headMap(toElement, inclusive));
        }
    
        // 返回Set的尾部,范围是:从fromElement到结尾。
        // inclusive是是否包含fromElement的标志
        public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
            return new TreeSet<E>(m.tailMap(fromElement, inclusive));
        }
    
        // 返回子Set。范围是:从fromElement(包括)到toElement(不包括)。
        public SortedSet<E> subSet(E fromElement, E toElement) {
            return subSet(fromElement, true, toElement, false);
        }
    
        // 返回Set的头部,范围是:从头部到toElement(不包括)。
        public SortedSet<E> headSet(E toElement) {
            return headSet(toElement, false);
        }
    
        // 返回Set的尾部,范围是:从fromElement到结尾(不包括)。
        public SortedSet<E> tailSet(E fromElement) {
            return tailSet(fromElement, true);
        }
    
        // 返回Set的比较器
        public Comparator<? super E> comparator() {
            return m.comparator();
        }
    
        // 返回Set的第一个元素
        public E first() {
            return m.firstKey();
        }
    
        // 返回Set的最后一个元素
        public E first() {
        public E last() {
            return m.lastKey();
        }
    
        // 返回Set中小于e的最大元素
        public E lower(E e) {
            return m.lowerKey(e);
        }
    
        // 返回Set中小于/等于e的最大元素
        public E floor(E e) {
            return m.floorKey(e);
        }
    
        // 返回Set中大于/等于e的最小元素
        public E ceiling(E e) {
            return m.ceilingKey(e);
        }
    
        // 返回Set中大于e的最小元素
        public E higher(E e) {
            return m.higherKey(e);
        }
    
        // 获取第一个元素,并将该元素从TreeMap中删除。
        public E pollFirst() {
            Map.Entry<E,?> e = m.pollFirstEntry();
            return (e == null)? null : e.getKey();
        }
    
        // 获取最后一个元素,并将该元素从TreeMap中删除。
        public E pollLast() {
            Map.Entry<E,?> e = m.pollLastEntry();
            return (e == null)? null : e.getKey();
        }
    
        // 克隆一个TreeSet,并返回Object对象
        public Object clone() {
            TreeSet<E> clone = null;
            try {
                clone = (TreeSet<E>) super.clone();
            } catch (CloneNotSupportedException e) {
                throw new InternalError();
            }
    
            clone.m = new TreeMap<E,Object>(m);
            return clone;
        }
    
        // java.io.Serializable的写入函数
        // 将TreeSet的“比较器、容量,所有的元素值”都写入到输出流中
        private void writeObject(java.io.ObjectOutputStream s)
            throws java.io.IOException {
            s.defaultWriteObject();
    
            // 写入比较器
            s.writeObject(m.comparator());
    
            // 写入容量
            s.writeInt(m.size());
    
            // 写入“TreeSet中的每一个元素”
            for (Iterator i=m.keySet().iterator(); i.hasNext(); )
                s.writeObject(i.next());
        }
    
        // java.io.Serializable的读取函数:根据写入方式读出
        // 先将TreeSet的“比较器、容量、所有的元素值”依次读出
        private void readObject(java.io.ObjectInputStream s)
            throws java.io.IOException, ClassNotFoundException {
            // Read in any hidden stuff
            s.defaultReadObject();
    
            // 从输入流中读取TreeSet的“比较器”
            Comparator<? super E> c = (Comparator<? super E>) s.readObject();
    
            TreeMap<E,Object> tm;
            if (c==null)
                tm = new TreeMap<E,Object>();
            else
                tm = new TreeMap<E,Object>(c);
            m = tm;
    
            // 从输入流中读取TreeSet的“容量”
            int size = s.readInt();
    
            // 从输入流中读取TreeSet的“全部元素”
            tm.readTreeSet(size, s, PRESENT);
        }
    
        // TreeSet的序列版本号
        private static final long serialVersionUID = -2479143000061671589L;
    }
    
    • LinkedHashSet
      继承HashSet,使用HashSet中带有LinkedHashMap的构造方法实例化出存储数据的map,从源码中可以看到LinkedHashSet直接继承了HashSet并没有新增任何方法,只是复写了spliterator()方法;LinkedHashSet内部使用的是LinkedHashMap,与HashSet的区别就是前者可以保证元素的顺序,也就是遍历顺序和插入顺序是一致的

    上述是大概的Collection中的常用类,当然还有很多类没有被介绍到,可以在具体使用的时候去查看,看一下源码基本的使用方式差不多,下面我们看下Map集合的形式

    Map

    image.png

    map中的方法一览:


    image.png

    对于其中常用方法和不常用方法做个简单介绍:

    • size():返回map大小
    • isEmpty():判断map是否为空
    • containsKey():是否包含当前key
    • containsValue():是否包含当前value
    • get()/put():存储值
    • remove()/clear():清除指定键的值,清除等个map
    • KeySet():返回当前map的所有键值的set集合,其内部是基于iterator(迭代器)实现的,
    • values():返回当前map中所有有效值value的集合
    • entrySet():返回当前map中的所有实例(Entry)的set集合
    • getOrDefault():获取对应key的值,如果没有则返回入参中的默认值
    • forEach:对map的所有键值对遍历,内部实际就是对entrySet的返回值进行遍历输出key-value
    • replaceAll():替换map中所有的value值,替换的值为BiFunction接口中的apply()的返回值
    • putIfAbsent():如果指定的key不存在与map中则新增改key-value值并返回null,如果存在于map中则刷新map的值为新的value值,返回旧value值
    • compute():api文档的解释为计算当前key的映射及当前映射的值,可能初看会看不懂,举个例子:
    String str1 = "hello java, i am vary happy! nice to meet you";
    HashMap<Character, Integer> result2 = new HashMap<>();
    for (int i = 0; i < str1.length(); i++) {
                char curChar = str1.charAt(i);
                //compute是返回最新的值
                result2.compute(curChar, (k, v) -> {
                    if (v == null) {
                        v = 1;
                    } else {
                        v += 1;
                    }
                    return v;
                });
            }
    System.out.println(result1);
    
    输出:
    { =9, !=1, a=5, c=1, e=4, h=2, i=2, j=1, ,=1, l=2, m=2, n=1, o=3, p=2, r=1, t=2, u=1, v=2, y=3}
    

    可以看到compute会根据指定的key生成一个key-value,

    HashMap

    HashMap可以算是项目中最常用的一种map子集,用来存储k-v数据,其内部采用的是哈希结构的形式,其实也就是数组加链表的使用,由于其使用的是哈希结构的方式去存储数据,则其必然会存在哈希冲突,对于哈希冲突只能尽量的减少而不能完全避免,HashMap中真正存储k-v集合的对象为Node对象,此对象继承自Mao.Entry,
    HashMap中包含有很多的内部类,大体如下:


    image.png

    可以看到基本都很类似,其中:
    Node:为HashMap中的存储对象类型实际类型
    KeySet/Values/EntrySet:为键的set集合,value的set集合,Node的set集合,都是用来方便更好的访问HashMap中的key或者value
    keyIterator/valueIterator/EntryIterator都是继承自HashIterator:返回一个key或者value的迭代器
    keySplitIterator/valueSplitIterator/EntrySplitIterator都是继承自HashSplitIterator;
    HashMap继承自Map,所以其中的方法大致来自于Map,上述已经分析过了,部分自定义的方法是扩展自有功能,也不难,可以执行分析一下

    LinkedHashMap

    一看是Linked开头的就知道跟链表有关系,是的,LinkedHashMap区别于HashMap的重要一点就是前者使用的是双向链表,而后者使用的是单向链表,前者可以保证按照插入顺序迭代输出,后者在迭代输出数据时是无序的

    WeakHashMap

    WeakHashMap也是一个散列表,存储的内容也是键值对,键和值都可以是null,不过WeakHashMap的键是"弱键",在weakHashMap中,当某个键没有其他任何地方没有引用时(只有map中的弱引用),该key-value被从weakHashMap中被自动移除(实际是被gc回收了到ReferenceQueue队列中,它会保存被GC回收的弱键),当下一次操作weakHashMap时会先同步table和queue,table中保存了全部的键值对,而queue中保存了被GC回收的键值对,同步他们就是删除table中被GC回收的键值对,这就是弱键如何被自动从weakHashMap中删除的步骤。


    image.png

    可以看到weakHashMap中存储实例Entry类继承了weakReference,并在构造方法中调用了父类的构造方法传入了key,即在此时将key变为了弱键。

    相关文章

      网友评论

          本文标题:java高级-集合collection/map

          本文链接:https://www.haomeiwen.com/subject/cdtvaktx.html