精华内容
下载资源
问答
  • java各种集合类区别

    万次阅读 多人点赞 2019-03-27 17:54:45
    最近面试经常遇到java集合类的问题,上网搜了一下,做个笔记 百度的图 集合类型主要有3种:set(集)、list(列表)和map(映射)。 集合接口分为:Collection和Map,list、set实现了Collection接口 List总结: ...

    最近面试经常遇到java集合类的问题,上网搜了一下,做个笔记

    百度的图

    集合型主要有3种:set(集)、list(列表)和map(映射)。

    集合接口分为:Collection和Map,list、set实现了Collection接口

     

    List总结

    可以重复,通过索引取出加入数据,顺序与插入顺序一致,可以含有null元素

    ArrayList:底层数据结构使数组结构array,查询速度快,增删改慢,因为是一种类似数组的形式进行存储,因此它的随机访问速度极快;

    Vector:底层是数组结构array,与ArrayList相同,查询速度快,增删改慢;

    LinkedList:底层使用链表结构,增删速度快,查询稍慢;

    ArrayList与Vector的区别

    1.如果集合中的元素数量大于当前集合数组的长度时,Vector的增长率是目前数组长度的100%,而ArryaList增长率为目前数组长度的50%。所以,如果集合中使用数据量比较大的数据,用Vector有一定优势

    2.线程同步ArrayList是线程不同步,所以Vector线程安全,但是因为每个方法都加上了synchronized,所以在效率上小于ArrayList

    Set总结:

    数据无序且唯一,实现类都不是线程安全的类,解决方案:Set set = Collections.sysnchronizedSet(Set对象);    

    HashSet:是Set接口(Set接口是继承了Collection接口的)最常用的实现类,顾名思义,底层是用了哈希表(散列/hash)算法。其底层其实也是一个数组,存在的意义是提供查询速度,插入的速度也是比较快,但是适用于少量数据的插入操作,判断两个对象是否相等的规则:1、equals比较为true;2、hashCode值相同。要求:要求存在在哈希表中的对象元素都得覆盖equals和hashCode方法。

    LinkedHashSet:继承了HashSet类,所以它的底层用的也是哈希表的数据结构,但因为保持数据的先后添加顺序,所以又加了链表结构,但因为多加了一种数据结构,所以效率较低,不建议使用,如果要求一个集合急要保证元素不重复,也需要记录元素的先后添加顺序,才选择使用LinkedHashSet

    TreeSet:Set接口的实现类,也拥有set接口的一般特性,但是不同的是他也实现了SortSet接口,它底层采用的是红黑树算法(红黑树就是满足一下红黑性质的二叉搜索树:①每个节点是黑色或者红色②根节点是黑色的③每个叶子结点是黑色的④如果一个节点是红色的,那么他的两个子节点是黑色的⑤对每个节点,从该节点到其所有的后代叶子结点的简单路径上,仅包含相同数目的黑色结点,红黑树是许多“平衡”搜索树的一种,可以保证在最坏情况下的基本操作集合的时间复杂度为O(lgn)。普及:二叉搜索树的性质:它或者是一棵空树;或者是具有下列性质的二叉树:若左子树不空,则左子树上所有结点的值均小于它的根结点的值;若右子树不空,则右子树上所有结点的值均大于它的根结点的值;左、右子树也分别为二叉排序树。若子树为空,查找不成功。),要注意的是在TreeSet集合中只能存储相同类型对象的引用。

    Tree最重要的就是它的两种排序方式:自然排序和客户端排序

    自然排序;实现了Comparable接口,所以TreeSet可以调用对象的ComparableTo()方法来比较集合的大小,然后进行升序排序,这种排序方式叫做自然排序。其中实现了Comparable接口的还有BigDecimal、BigInteger、Byte、Double、Float、Integer、Long、Short(按照数字大小排序)、Character(按照Unicode值的数字大小进行排序)String(按照字符串中字符的Unicode值进行排序)类等。
    客户化排序:其实就是实现java.util.Comparator<Type>接口提供的具体的排序方式,<Type> 是具体要比较对象的类型,他有个compare的方法,如compare(x,y)返回值大于0表示x大于y,以此类推,当我们希望按照自己的想法排序的时候可以重写compare方法。

    Map总结:

    java的Map(映射)是一种把键对象和值对象进行映射的集合,其中每一个元素都包含了键对象和值对象,其中值对象也可以是Map类型的数据,因此,Map支持多级映射,Map中的键是唯一的,但值可以不唯一,Map集合有两种实现,一种是利用哈希表来完成的叫做HashMap,它和HashSet都是利用哈希表来完成的,区别其实就是在哈希表的每个桶中,HashSet只有key,而HashMap在每个key上挂了一个value;另一种就是TreeMap,它实现了SortMap接口,也就是使用了红黑树的数据结构,和TreeSet一样也能实现自然排序和客户化排序两种排序方式,而哈希表不提供排序。
    HashMap:哈希表的实现原理中,先采用一个数组表示位桶,每个位桶的实现在1.8之前都是使用链表,但当每个位桶的数据较多的时候,链表查询的效率就会不高,因此在1.8之后,当位桶的数据超过阈值(8)的时候,就会采用红黑树来存储该位桶的数据(在阈值之前还是使用链表来进行存储),所以,哈希表的实现包括数组+链表+红黑树,在使用哈希表的集合中我们都认为他们的增删改查操作的时间复杂度都是O(1)的,不过常数项很大,因为哈希函数在进行计算的代价比较高,HashMap和Hashtable类似,不同之处在于HashMap是非同步的,并且允许null,即null value和null key。,但是将HashMap视为Collection时(values()方法可返回Collection),其迭代子操作时间开销和HashMap 的容量成比例。因此,如果迭代操作的性能相当重要的话,不要将HashMap的初始化容量设得过高,或者load factor过低。

    TreeMap:TreeMap 是一个有序的key-value集合,它是通过红黑树实现的。TreeMap 继承于AbstractMap,所以它是一个Map,即一个key-value集合。TreeMap 实现了NavigableMap接口,意味着它支持一系列的导航方法。比如返回有序的key集合。TreeMap 实现了Cloneable接口,意味着它能被克隆。TreeMap 实现了java.io.Serializable接口,意味着它支持序列化。

    TreeMap基于红黑树(Red-Black tree)实现。该映射根据其键的自然顺序进行排序,或者根据创建映射时提供的 Comparator 进行排序,具体取决于使用的构造方法。TreeMap的基本操作 containsKey、get、put 和 remove 的时间复杂度是 log(n) 。另外,TreeMap是非同步的。 它的iterator 方法返回的迭代器是fail-fastl的。

    HashTable:Hashtable继承Map接口,实现一个key-value映射的哈希表。任何非空(non-null)的对象都可作为key或者value,线程安全

    展开全文
  • java中常用的几个集合类

    万次阅读 多人点赞 2019-06-10 20:19:24
    //包含Collection(集合),List,Set,Map(图),以及其Iterator,Comparator,Cloneable,还有常用的具体实现 //List<List<String>>集合的嵌套使用 //1、是否允许空 //2、是否允许重复数据 //3、...
    //TODO
    
    //未完成
    //不过先发了吧
    
    //包含Collection(集合),List,Set,Map(图),以及其Iterator,Comparator ,Cloneable,还有常用的具体实现类
    //List<List<String>>集合的嵌套使用
    //1、是否允许空
    //2、是否允许重复数据
    //3、是否有序,有序的意思是读取数据的顺序和存放数据的顺序是否一致
    //4、是否线程安全

    JAVA SE 8官方文档 

    JAVA官方文档中集合类的关系

    目录

    概览

    瞎说几句

    对第一张图(集合类的关系)的解析

    具体的几个集合类(List,Set,Map)

    List 

    ArrayList

    LinkedList

    Set

    HashSet

    TreeSet

    Map

    HashMap

    TreeMap


    概览

    瞎说几句

    JAVA中有许多的集合,常用的有List,Set,Queue,Map。

    其中List,Set,Queue都是Collection(集合),其每个元素都是单独的一个对象,如List<String>,Set<Integer>等,String和Integer就是单独的一个对象。

    而Map是一种图,其每个元素都是两个对象一一对应,如Map<Integer, String>中的Integer是键 (key),String是这个键所对应的值(value)。每个元素都是一对Integer和String

    tip 1: List<String>中<>的内容表示其中元素的类型,是泛型的一种使用。

    tip 2: Integer是一个对象(可从首字母大写的命名方式中看出),可以粗略地将其视作int。

    tip 3: 由于这些集合类的元素必须是对象或者由对象构成,所以不能直接使用int这种简单数据类型将Map定义为Map<int, String>,而应该使用Integer将Map定义为Map<Integer, String>。

    tip 4: 不能直接使用简单数据类型的更深层次的原因在于:

             集合类(比如Set)在进行各种 "操作" ( 如contains()) 时都会调用元素本身提供的 "方法" ( 如hashCode()和equals()),而不是由集合类自身去实现这些 "方法"。这就要求如果某人想要用这个集合执行某些 "操作",那就必须在要加入集合的元素中实现相应的 "方法"。

             由于简单数据类型 (如int),只是单纯的一个数值,而无法在其中实现方法,所以应该使用实现了各种所需"方法"的类 (如Integer) 作为元素。

     

    对第一张图(集合类的关系)的解析

    从第二行 java.util.AbstractCollection<E> (implements java.util.Collection<E>) 看起

     

    接着看 java.util.AbstractMap<K,V> (implements java.util.Map<K,V>) 这一行

    AbstractMap<K,V>是一个抽象类,实现了java.util.Map<K,V>接口,具有图的功能(即key和value的一一对应)。其下有几个具体的实现类,分别是:EnumMap<K,V>,HashMap<K,V>,LinkedHashMap<K,V>,IdentityHashMap<K,V>,TreeMap<K,V>,WeakHashMap<K,V>

     

    具体的几个集合类(List,Set,Map)

    List 

    List(列表),相当于数组。长度可变,元素存放有一定的顺序,下标从0开始。

    tip

    在JDK中,List作为接口,本身已经声明好了所有的方法(比如add(), contains()......),所以不管是选择ArrayList还是LinkedList,完成各种操作的时候依然是使用List中已经声明过的这一套方法,对使用者来说没有区别。

    二者只是内部实现逻辑不同,所以在不同的应用场景下会有不同的效率。

    ArrayList  

    先回答四个问题:

    是否允许空元素(即null)
    是否允许重复数据
    是否有序
    是否线程安全
    //如何使用ArrayList创建一个List
    //不指定存放的元素类型
    
    //默认容量为10
    List list = new ArrayList();
    
    //容量为6
    List list = new ArrayList(6);

     Array即数组,顾名思义,ArrayList是用数组实现的一个List(列表)。它实现了List接口声明的的所有方法,而且允许加入包括null在内的所有元素。除了实现列表接口之外,这个类还提供了一些方法来操作内部用于存储列表的数组的大小。

    在每一个ArrayList实例中,都有专门保存容量的capacity属性,我在jdk1.8中找到了它的默认容量大小是

    DEFAULT_CAPACITY = 10,如下是jdk1.8中对DEFAULT_CAPACITY的定义

    public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
        /*
            some code
        */
    
        private static final int DEFAULT_CAPACITY = 10;
    
        /*
            some code
        */
    }

    接下来讨论ArrayList中对capacity的控制

    举个栗子,ArrayList的add()方法,首先需要说明几个变量的含义,我从jdk1.8中找来了这些变量的声明语句包括其注释:

    public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
    {
        /*
            some code
        */
    
        /**
         * Default initial capacity.
         */
        private static final int DEFAULT_CAPACITY = 10;
    
        /**
         * Shared empty array instance used for empty instances.
         */
        private static final Object[] EMPTY_ELEMENTDATA = {};
    
        /**
         * Shared empty array instance used for default sized empty instances. We
         * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
         * first element is added.
         */
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
        /**
         * The array buffer into which the elements of the ArrayList are stored.
         * The capacity of the ArrayList is the length of this array buffer. Any
         * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
         * will be expanded to DEFAULT_CAPACITY when the first element is added.
         */
        transient Object[] elementData; // non-private to simplify nested class access
    
        /**
         * The size of the ArrayList (the number of elements it contains).
         *
         * @serial
         */
        private int size;
    
        /*
            some code
        */
    }

    其中各个变量的含义如下:

    private static final int DEFAULT_CAPACITY = 10;

    是默认的容量大小。当不指定容量大小的时候,就是用默认容量10

    private static final Object[] EMPTY_ELEMENTDATA = {};

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    这两个作用类似,在创建一个新的ArrayList对象的时候引用。初始化ArrayList中的数组(即elementData变量)。

    两个Object数组本身并没有区别,定义这样没区别的两个是为了区分使用的是哪种构造方法。在ArrayList()方法中用的是DEFAULTCAPACITY_EMPTY_ELEMENTDATA,而在ArrayList(int initialCapacity)和ArrayList(Collection<? extends E> c)方法中用的是EMPTY_ELEMENTDATA。

    transient Object[] elementData;

    tip:这里有一个transient关键字,是关于序列化和反序列化的。简单说一下,序列化就是把对象转换成字节序列的形式,这些字节序列包含了对象的数据和信息,一个序列化后的对象可以被写到数据库或文件中,也可以用于网络传输。一般当我们使用缓存cache(内存空间不够有可能会本地存储到硬盘)或远程调用rpc(网络传输)的时候,经常需要让我们的实体类实现Serializable接口,目的就是为了让其可序列化。序列化之后再反序列化就能得到原来的java对象。而transient修饰的数据将不会被自动序列化。但是,elementData会被writeObject方法手动序列化,这个不多说了。

    这个变量就是ArrayList中的Array,ArrayList中的元素就是保存在这里。

    private int size;

    数组中元素的个数,当我们调用size()方法的时候返回的就是这个size。跟容量(capacity)是两个不同的概念,不要混淆。

    protected transient int modCount = 0;

    还有一个继承自其父类AbstractList的属性,modCount,表示发生结构化改变的次数。关于结构化改变(Structural modifications),AbstractList中是这样子解释的

    The number of times this list has been structurally modified. Structural modifications are those that change the size of the list, or otherwise perturb it in such a fashion that iterations in progress may yield incorrect results.

    意即当size改变了,这个modCount就会+1。

    测试代码是这样的:

    public class Test{
      public static void main(String[] args) {
        List<String> list = new ArrayList();
        for(int i = 0; i <= 10; i++){
            //向list中依次添加“ii”。
            //例如,当i为0时,向list添加"00";当i为1时,向list添加"11"。
            StringBuilder sb = new StringBuilder();
            sb.append(i)
              .append(i);
            list.add(sb.toString());
        }
      }
    }

    运行结果是ArrayList的size为11,容量为15

    for循环结束之后的ArrayList​​​​

     

    下面是ArrayList在执行add()方法的时候所涉及的方法,我给放在一个页面里方便查找。

    public class ArrayList<E> extends AbstractList<E>
            implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
        /*
            some code
        */
    
        public ArrayList() {
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }
    
        /*
            some code
        */
    
        private static int calculateCapacity(Object[] elementData, int minCapacity) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            }
            return minCapacity;
        }
    
        private void ensureCapacityInternal(int minCapacity) {
            ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
        }
    
        private void ensureExplicitCapacity(int minCapacity) {
            modCount++;
    
            // overflow-conscious code
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }
        
        /*
            some code
        */
    
        private void grow(int minCapacity) {
            // overflow-conscious code
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    
        /*
            some code
        */
    
        public boolean add(E e) {
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            elementData[size++] = e;
            return true;
        }
    
        /*
            some code
        */
    }

    当i = 0时,此时是第一次向list中添加元素,elementData容量不足,需要加大elementData的容量。初始的list是一个空的Object[],依次调用add(), ensureCapacityInternal(), ensureExplicitCapacity(), grow(), calculateCapacity()方法。

    在calculateCapacity()方法中,由于list是由ArrayList的无参构造方法构造的,所以elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA的结果为true,执行语句:return Math.max(DEFAULT_CAPACITY, minCapacity);会得到DEFAULT_CAPACITY即10。

    返回的结果交给ensureExplicitCapacity(),modCount先自增一次,表示ist必然会做一次结构性修改。此时minCapacity - elementData.length > 0结果为true(nimCapacity = 10, elementData.length = 0),执行grow(minCapacity);

    在grow()方法中,oldCapacity = 0,newCapacity = 0,minCapacity = 10。(oldCapacity >> 1相当于oldCapacity / 2)故会进入if (newCapacity - minCapacity < 0)条件判断体中的语句,执行newCapacity = minCapacity,令newCapacity = 10,再执行Array.copyOf()方法,将elementData扩充到容量为10。

    之后,回到add()方法体中,elementData[size++] = e; 将elemtntData[0]的值赋为"00",然后size再将赋值为1。

    可见,扩容发生在grow()方法中,而在ensureExplicitCapacity()方法中决定是否要扩容。

    i = 1~9的过程中,elementData的容量都没有发生改变。不做叙述。

    当i = 10时,容量为10的elementData已经被填充满了,需要再次扩容,经过之前提到的方法调用顺序,得到新的容量应该为15。进行扩容。

     

    Set

    不包含重复元素的集合。更确切地说,是不同时包含使得e1.equals(e2)成立的e1和e2(因为e1与e2的equals()逻辑可以由使用者自己定义)。并且最多包含一个空元素。这个接口是数学集合的一个抽象建模。
    注意:如果可变的(mutable)对象用作集合元素,则必须非常小心。当一个对象是集合中的元素时,以影响equals()比较结果的方式更改对象的值,则无法预测集合的行为。有一个特殊情况是,不允许一个集合作为一个元素来包含它自己。所以还是尽量使用immutable的对象作为Set的元素。

    HashSet

    先回答四个问题:

    是否允许空元素(即null)
    是否允许重复数据
    是否有序
    是否线程安全
    //如何使用HashSet创建一个Set
    //不指定存放的元素类型
    
    //默认容量为16
    Set set = new HashSet();
    
    //容量为6
    Set set = new HashSet(6);

    HashSet是基于HashMap实现的,所以需要先理解HashMap。但是我希望这篇文章是List,Set,Map的顺序,并且并不打算换序,所以还不理解HashMap的点这里跳转到后面。

    在HashSet中,保存数据的变量名为map:

    private transient HashMap<E,Object> map; 

    一个HashMap,map的key是E类型,即HashSet中的元素;每个key的value是Object类型,这是HashSet类中定义的一个常量,名为PRESENT

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

    这只是为了使用HashMap而创建的一个Object对象,用来占掉value的位置,无其他意义 。

    HashSet不保证集合的迭代顺序;具体来说,它不保证顺序将随时间保持不变(除非你自己实现一个迭代器去保证迭代顺序)。它的一些基本操作(add()、remove()、contains()和size())的时间复杂度是常量级的,前提是散列函数在存储桶中正确地分散元素(即要把hashCode()写好,让equals()方法判定为相等的两个对象的hashCode也相等,尽量让equals()方法判定为不等的两个对象的hashCode不等)。

    迭代此集合需要与哈希集实例的大小(即HashSet中元素的个数)加上支持哈希映射实例的“容量”(存储桶数)之和成比例的时间。因此,如果迭代性能很重要,那么不要将初始容量设置得太高(或者负载系数设置得太低)。

    TreeSet

    先回答四个问题:

    是否允许空元素(即null)
    是否允许重复数据
    是否有序
    是否线程安全
    //如何使用TreeSet创建一个Set
    //不指定存放的元素类型
    
    //无参构造方法
    Set set = new TreeSet();

    同样是借助Map实现的,不过这次是TreeMap。还不理解TreeMap的点这里跳转到后面。

    基于TreeMap的NavigableSet实现。元素是使用它们的自然顺序来排序的,或者通过在设置的创建时提供的比较器来排序的,这取决于使用的是哪个构造函数。

    此实现为基本操作(add()、remove()和contains())提供了保证的log(n)时间成本。

    注意,如果要正确实现集合接口,集合维护的顺序(无论是否提供显式比较器)必须与equals一致。(请参阅Comparable或Comparator以获得与equals一致的精确定义。)这是因为集合接口是根据equals操作定义的,但TreeSet实例使用其CompareTo(或Compare)方法执行所有元素比较,因此从TreeSet的角度来看,该TreeSet认为相等的两个元素应该是equals()方法返回true的两个元素。这个TreeSet的行为是清晰的,即使其中元素的顺序与equals()方法不一致;它只是不遵守Set接口的总规约(即spec)。

    注意,这个实现是不同步的。如果多个线程同时访问一个树集,并且至少有一个线程修改了该集,则必须在外部对其进行同步。这通常是通过在自然封装集合的某个对象上进行同步来完成的。如果不存在此类对象,则应使用collections.synchronizedSortedSet方法“包装”集合。这最好在创建时完成,以防止意外的对集合的非同步访问:

    SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));

    Map

    将key映射到value的对象。Map不能包含重复的key;每个key最多可以映射到一个value

    HashMap

    TreeMap

     

     

     

    展开全文
  • Java基础-各种集合类的特性简介

    千次阅读 2020-12-31 19:46:39
    各种集合类的特性简介集合类概述集合中存储什么不同集合对应不同数据结构集合继承结构及特性简介Map集合继承结构及特性简介总结: 集合类概述 什么是集合?有什么用? 数组其实就是一个集合,集合实际上一个容器,...

    集合类概述

    什么是集合?有什么用?
    数组其实就是一个集合,集合实际上一个容器,可以来容纳其他类型的数据。
    集合为什么说在开发中使用的比较多?
    集合是一个容器,是一个载体,可以一次容纳多个对象(如超市的购物袋)
    在实际开发中,假设连接数据库,数据库中有10条记录
    那么假设把这10条记录查询出来,在java程序中将会有10条数据封装成10个对象,然后将10个java对象放到某一个集合中,将集合传到前端,然后遍历集合,将一个数据一个数据

    集合中存储什么

    集合不能直接存储基本数据类型,另外集合也不能直接存储java对象
    集合当中存储的都是java的内存地址。(或者集合中存储的是引用)

    list.add(100);			//自动装箱Integer
    

    注意:
      集合在java中本身是一个容器,是一个对象
      集合中任何时候存储的都是引用
    在这里插入图片描述
    集合里面也可以存集合

    不同集合对应不同数据结构

    在java中每一个不同的集合,底层会对应不同的数据结构,往不同的集合中存储元素,等于将数据放到了不同的数据结构中。什么是数据结构?数据存储的结构就是数据结构,不同的数据结构,数据存储方式不同,例如:
    数组、二叉树、链表、哈希表
    以上都是常见的数据结构。
    往集合c1中放数据,可能放到数组上。
    往集合c2中放数据,可能放到二叉树了
    使用不同的集合等同于使用了不同的数据结构。
    在java集合这一章节,你需要掌握的不是精通数据结构,java中已经将数据结构实现了,已经写好了这些常用集合类,只需要掌握怎么用?在什么情况下选择哪一种合适的集合去使用即可。
    ArrayList底层使用数组
    LinkedList底层使用链表
    HashMap底层哈希表
    TreeSet底层二叉树结构

    new ArrayList(); //创建一个集合,底层是数组
    new LinkedList(); //创建一个集合,底层是链表。

    集合继承结构及特性简介

    集合在java JDK中在哪个包下?
      java.util.*;

    所有的集合类和集合接口都在java.util包下
    为了能够掌握集合这块的内容,最好能够将集合的继承结构背会
    集合整个这个体系是怎样的一个结构,需要有印象。
    在java中集合分为两大类
    一类是以单个方式存储元素:

      这一类集合超级父接口:java.util.Collection
    一类是以键值对方式存储元素

      这一类结合超级父接口:java.util.Map
    在这里插入图片描述
    Iterable有.iterator()方法,可以获得迭代器对象,从而遍历集合
      Iterator it=“collection对象”.iterator();
      it是迭代器对象

    所有集合都继承Iterator的含义是,所有集合都是可迭代(遍历)的。
    在这里插入图片描述

    图片可能比较模糊,但是没关系
    Iterable接口:(最上面一层)
    最上面的是Iterable接口。Iterator接口是可迭代的,可遍历的。所有集合元素都是可迭代的,可遍历的。是Collection接口的父类。
    Iterator接口:(最左边的一个):
    集合的迭代器对象。与Collection接口是关联关系
    Collection接口:
    集合接口的公共父类。
    List接口:
    list集合存储元素特点,有序可重复,存储的元素有下标:有序实际上是指存进去是这个顺序,取出来还是这个顺序,这里的顺序不是说按照大小顺序排序。
    有序是因为list集合都有下标,下标从0开始,以1递增。
    Set接口:
    set集合存储元素特点:无序不可重复,无序表示存进去是这个顺序,取出来就不一定是这个顺序了,另外Set集合中元素没有下标,set集合中的元素还不能重复。
    List接口实现类:
      ArrayList实现类
      ArrayList集合底层采用了数组这种数据结构,ArrayList是非线程安全的。
      1.ArrayList集合初始化容量是10
      2.ArrayList集合底层是Object类型的数组Object[]
      3.扩容到原容量的1.5倍。
      4.建议给定一个预估计的初始化容量,减少数组的扩容次数,这是ArrayList集合比较重要的优化策略。
      5.数组的优点:检索效率比较高。
      6.数组的缺点:随机增删元素效率比较低。
      LinkedList实现类
      LinkedList集合底层采用了双向链表数据结构
      1.LinkedList集合是双向链表
      2.对于链表数据结构来说,随机增删效率高,检索效率比较低。
      3.链表中的元素在空间存储上,内存地址不连续。
      Vector实现类
      Vector集合底层采用了数组这种数据结构, Vector是非线程安全的,vector所有方法加了sychronize关键字修饰,但是效率较低,现在保证线程安全有别的方案,所以Vector使用的比较少了。
    Set接口实现类:
      HashSet实现类
      实际上hashSet底层在new的时候,底层实际上new了一个hashMap的集合,向HashMap集合中存储元素,实际上是存储到hashMap集合中了。hashMap是一个hash表存储结构。
      HashSet集合初始化容量为16,初始化容量建议是2的倍数,扩容:扩容之后是原容量的2倍。
      SortedSet实现类
      SortedSet由于继承了Set集合,所以它的特点也是无序不可重复,但是放在SortedSet集合中的元素可以自动排序。我们称为可排序集合,放到该集合中的元素自动按照大小顺序排序的。
      TreeSet实现类(直接继承自Sorted实现类)
      TreeSet底层在new的时候,底层实际上new了一个TreeMap的集合,TreeSet集合在放数据的时候,实际上是将数据放到TreeMap中了。(具体查看treeset的构造方法)
      TreeMap集合底层采用了二叉树的数据结构。

    Map集合继承结构及特性简介

    在这里插入图片描述

    Map接口:
    1.Map集合和collection集合没有关系
    2.Map集合以key和value的键值对方式来存储元素
    3.key和value都是存储java对象的内存地址。
    4.所有Map集合的key特点:无序不可重复
    5.Map集合的key和set集合存储元素特点相同。
    HashMap实现类:
    HashMap底层是哈希表数据结构,是非线程安全的。
    在JDK8之后,如果哈希表单向链表中元素超过8个,单向链表这种数据结构会变成红黑树数据结构。当红黑树上的节点数量少于6时,会重新把红黑树变成单向链表数据结构。这种方式也是为了提高检索效率,二叉树的检索会再次缩小扫描范围。提高效率。初始化容量16,默认加载因子0.75.
    扩容是:扩容之后的容量是原容量的2倍。

    Hashtable实现类
    HashTable底层也是哈希表数据结构,是线程安全的,其中所有的方法都带有sychronized关键字,效率较低,现在使用较少。
    hashtable的key和value不允许为null
    hashtabe集合初始化容量11
    hashtable集合扩容是:原容量*2+1
    Properties实现类(直接继承自Hashtable)
    Properties是线程安全的,因为继承HashTable,Properties存储元素的时候,也是key和value方式存储,它只支持String类型,不支持其他类型。Properties被称为属性类。
    SortedMap实现类
    SortedMap也是一个接口,它实现了Map,SortedMap集合的key存储元素的特点:首先是无序不可重复的,另外放在SortedMap集合key部分的元素会自动按照大小顺序排序,称为可排序的集合。
    TreeMap实现类(直接继承自SortedMap)
    TreeMap实现了SortedMap,它是一个实现类。TreeMap集合底层的数据结构是一个二叉树

    总结:

    ArrayList:底层是数组
    LinkedList:底层是双向链表
    Vector:底层是数组,线程安全的,效率较低,使用较少
    HashSet:底层是HashMap,放到HashSet集合中的元素等同于放到HashMap集合key部分了
    TreeSet:底层是TreeMap,放到TreeSet集合中的元素等同于放到TreeMap集合中的key部分了
    HashMap:底层是哈希表数据结构
    Hashtable:底层也是哈希表,线程安全,效率
    Properties
    TreeMap:底层是二叉树,TreeMap集合的key可以自动按照大小顺序排序。

    List集合存储元素的特点
    有序可重复

    Set集合元素的特点
    无序不可重复

    Sorted
    首先是无序不可重复的,但是Sorted集合中的元素是可排序的(大小顺序)

    Map集合的key就是一个Set集合
    在Set集合中放入数据,实际上放到了Map集合的key部分(具体查看源代码set的put方法)

    展开全文
  • scala集合类详解

    万次阅读 2017-05-28 21:59:14
    对scala中的集合类虽然有使用,但是一直处于一知半解的状态。尤其是与java中各种集合类的混合使用,虽然用过很多次,但是一直也没有做比较深入的了解与分析。正好趁着最近项目的需要,加上稍微有点时间,特意多花了...

    项目github地址:bitcarmanlee easy-algorithm-interview-and-practice
    欢迎大家star,留言,一起学习进步

    对scala中的集合类虽然有使用,但是一直处于一知半解的状态。尤其是与java中各种集合类的混合使用,虽然用过很多次,但是一直也没有做比较深入的了解与分析。正好趁着最近项目的需要,加上稍微有点时间,特意多花了一点时间对scala中的集合类做个详细的总结。

    1.数组Array

    在说集合类之前,先看看scala中的数组。与Java中不同的是,Scala中没有数组这一种类型。在Scala中,Array类的功能就与数组类似。
    与所有数组一样,Array的长度不可变,里面的数据可以按索引位置访问。

      def test() = {
        val array1 = new Array[Int](5)
        array1(1) = 1
        println(array1(1))
        val array2 = Array(0, 1, 2, 3, 4)
        println(array2(3))
      }
    

    上面的demo就演示了Array的简单用法。

    2.集合类的大致结构

    盗用网上的一张图,scala中集合类的大体框架如下图所示。
    这里写图片描述

    特意查了下scala的源码,贴上几张图,可以对应到上面的这幅继承关系图。
    这里写图片描述

    根据图以及源码可以很清晰地看出scala中的集合类可以分为三大类:
    1.Seq,是一组有序的元素。
    2.Set,是一组没有重复元素的集合。
    3.Map,是一组k-v对。

    3.Seq分析

    Seq主要由两部分组成:IndexedSeq与LinearSeq。现在我们简单看下这两种类型。

    首先看IndexedSeq,很容易看出来这种类型的主要访问方式是通过索引,默认的实现方式为vector。

      def test() = {
        val x = IndexedSeq(1,2,3)
        println(x.getClass)
        println(x(0))
    
        val y = Range(1, 5)
        println(y)
      }
    

    将以上函数运行起来以后,输出如下:

    class scala.collection.immutable.Vector
    1
    Range(1, 2, 3, 4)
    

    而作为LinearSeq,主要的区别在于其被分为头与尾两部分。其中,头是容器内的第一个元素,尾是除了头元素以外剩余的其他所有元素。LinearSeq默认的实现是List。

      def test() = {
        val x = collection.immutable.LinearSeq("a", "b", "c")
        val head = x.head
        println(s"head is: $head")
    
        val y = x.tail
        println(s"tail of y is: $y")
      }
    

    将上面的代码运行起来以后,得到的结果如下:

    head is: a
    tail of y is: List(b, c)
    

    4.Set

    与其他任何一种编程语言一样,Scala中的Set集合类具有如下特点:
    1.不存在有重复的元素。
    2.集合中的元素是无序的。换句话说,不能以索引的方式访问集合中的元素。
    3.判断某一个元素在集合中比Seq类型的集合要快。

    Scala中的集合分为可变与不可变两种,对于Set类型自然也是如此。先来看看示例代码:

      def test() = {
        val x = immutable.HashSet[String]("a","c","b")
        //x.add("d")无法使用,因为是不可变集合,没有add方法。
        val y = x + "d" + "f"  // 增加新的元素,生成一个新的集合
        val z = y - "a"  // 删除一个元素,生成一个新的集合
        val a = Set(1,2,3)
        val b = Set(1,4,5)
        val c = a ++ b  // 生成一个新的集合,增加集合
        val d = a -- b  // 生成一个新的集合,去除集合
        val e = a & b // 与操作
        val f = a | b // 或操作
      }
    

    因为上面代码里的集合类型都是不可变类型,所以所有语句结果其实都是生成一个新的集合。

      def test() = {
        val x = new mutable.HashSet[String]()
        x += "a"  // 添加一个新的元素。注意此时没有生成一个新的集合
        x.add("d") //因为是可变集合,所以有add方法
        x ++= Set("b", "c")  // 添加一个新的集合
        x.foreach(each => println(each))
        x -= "b"  // 删除一个元素
        println()
        x.foreach(each => println(each))
        println()
        val flag = x.contains("a") // 是否包含元素
        println(flag)
      }
    

    将上面这段代码运行起来以后,得到的结果如下:

    c
    d
    a
    b
    
    c
    d
    a
    
    true
    

    5.Map

    Map这种数据结构是日常开发中使用非常频繁的一种数据结构。Map作为一个存储键值对的容器(key-value),其中key值必须是唯一的。 默认情况下,我们可以通过Map直接创建一个不可变的Map容器对象,这时候容器中的内容是不能改变的。示例代码如下。

      def test() = {
        val peoples = Map("john" -> 19, "Tracy" -> 18, "Lily" -> 20) //不可变
        // people.put("lucy",15) 会出错,因为是不可变集合。
        //遍历方式1
        for(p <- peoples) {
          print(p + "  ") // (john,19)  (Tracy,18)  (Lily,20)
        }
        //遍历方式2
        peoples.foreach(x => {val (k, v) = x; print(k + ":" + v + "  ")}) //john:19  Tracy:18  Lily:20
        //遍历方式3
        peoples.foreach ({ case(k, v) => print(s"key: $k, value: $v  ")})
        //key: john, value: 19  key: Tracy, value: 18  key: Lily, value: 20
      }
    

    上面代码中的hashMap是不可变类型。
    如果要使用可变类型的map,可以使用mutable包中的map相关类。

      def test() = {
        val map = new mutable.HashMap[String, Int]()
        map.put("john", 19) // 因为是可变集合,所以可以put
        map.put("Tracy", 18)
        map.contains("Lily") //false
        val res = getSome(map.get("john"))
        println(res) //Some(19)
      }
    
      def getSome(x:Option[Int]) : Any = {
        x match {
          case Some(s) => s
          case None => "None"
        }
      }
    

    6.可变数组ArrayBuffer

    特意将ArrayBuffer单独拎出来,是因为ArrayBuffer类似于Java中的ArrayList。而ArrayList在Java中是用得非常多的一种集合类。
    ArrayBuffer与ArrayList不一样的地方在于,ArrayBuffer的长度是可变的。与Array一样,元素有先后之分,可以重复,可以随机访问,但是插入的效率不高。

      def test() = {
        val arrayBuffer = new mutable.ArrayBuffer[Int]()
        arrayBuffer.append(1)  //后面添加元素
        arrayBuffer.append(2)
        arrayBuffer += 3  //后面添加元素
        4 +=: arrayBuffer  //前面添加元素
      }
    

    7.java与scala集合的相互转换

    scala最大的优势之一就是可以使用JDK上面的海量类库。实际项目中,经常需要在java集合类与scala集合类之间做转化。具体的转换对应关系如下:
    scala.collection.Iterable <=> Java.lang.Iterable
    scala.collection.Iterable <=> Java.util.Collection
    scala.collection.Iterator <=> java.util.{ Iterator, Enumeration }
    scala.collection.mutable.Buffer <=> java.util.List
    scala.collection.mutable.Set <=> java.util.Set
    scala.collection.mutable.Map <=> java.util.{ Map, Dictionary }
    scala.collection.mutable.ConcurrentMap <=> java.util.concurrent.ConcurrentMap

    scala.collection.Seq => java.util.List
    scala.collection.mutable.Seq => java.util.List
    scala.collection.Set => java.util.Set
    scala.collection.Map => java.util.Map
    java.util.Properties => scala.collection.mutable.Map[String, String]

    在使用这些转换的时候,只需要scala文件中引入scala.collection.JavaConversions._ 即可。

    一般比较多件的场景是在scala中调用java方法。如前面所讲,jdk的类库太丰富了,在scala中会经常有调用java方法的需求。给个简单的例子:
    假设有如下java代码:

    public class TestForScala {
    
        public static <T> void printCollection(List<T> list) {
            for(T t: list) {
                System.out.println(t);
            }
        }
    }
    
    

    我们想在scala代码中调用TestForScala类中的printCollection方法。可以这么写:

      def test() = {
        val raw = Vector(1, 2, 3)
        TestForScala.printCollection(raw)
      }
    

    java方法中需要的参数是个List,参照我们前面的转换关系,scala.collection.Seq可以自动转化为java中的List,而Vector就是scala中Seq的实现,所以可以直接传入到printCollection方法中!

    展开全文
  • Java集合类详解

    万次阅读 多人点赞 2016-08-01 21:09:05
    Collection ├List │├LinkedList │├ArrayList │└Vector │ └Stack └Set Map ├Hashtable ... Collection是最基本的集合接口,一个Collection代表一组Object,即Collection的元素(Element
  • JAVA集合类整理

    千次阅读 多人点赞 2018-08-28 19:01:49
    集合类之间的关系如下:实线边框的是实现类,折线边框的是抽象类,而点线边框的是接口(图片来源) Collection:(java.util.*; JDK 1.2)   有以下核心方法: Collection接口下面有两个重要的子接口List和...
  • 【C++】类和对象编程练习——定义整数集合类

    千次阅读 多人点赞 2019-09-04 21:43:30
    定义整数集合类intSet.该类包括以下成员函数: inSet(); //类的构造函数,根据需要可以定义多个构造函数 int Empty(); //清空该整数集合 bool Isempty(); //判断整数集合是否为空 bool Ismemberof(...
  • 算法:如何使用C++实现一个简单的集合类

    千次阅读 多人点赞 2019-02-15 14:24:36
    实现一个集合类,要求实现以下4个操作。 (1)向集合中添加元素,如果集合中已存在元素则不添加 (2)从集合中移除元素,移除之前需要先判断集合中元素是否存在 (3)重载+运算符,用以实现集合的求并集运算 (4...
  • JAVA集合类汇总

    万次阅读 多人点赞 2017-02-20 08:25:38
    一、集合与数组 数组(可以存储基本数据类型)是用来存现对象的一种容器,但是数组的长度固定,不适合在对象数量未知的情况下使用。...集合(只能存储对象,对象...如图所示:图中,实线边框的是实现,折线边
  • Java集合类总结,详细且易懂!

    万次阅读 多人点赞 2020-09-01 00:44:34
    1.3集合概述 Java集合框架图: 注:上图中粉红色的为接口,紫色的和蓝色框为实现。 Java集合要从两大接口说起,一为Collection接口,二为Map接口,它们是同一个层次的。 Collection接口被List接口和Set接口继承; ...
  • java集合类的创建方式

    千次阅读 2020-12-17 14:31:06
    java集合类的创建方式 常常因为不会创建集合类的语法而浪费时间。。 集合可以看作一个容器,集合中的对象可以很容易存放到集合中,也很容易将其从集合中取出来,还可以按一定的顺序摆放。Java中提供了不同的集合类,...
  • Java中的集合类包括ArrayList、LinkedList、HashMap等,下列关于集合类描述错误的是(C) A.ArrayList和LinkedList均实现了List接口 B.ArrayList的访问速度比LinkedList快 C.随机添加和删除元素时,ArrayList的表现...
  • Java 集合类中的常用类

    千次阅读 2018-05-12 19:35:39
    Java中的集合类包含的内容很多而且很重要,很多数据的存储和处理(排序,去重,筛选等)都需要通过集合类来完成。首先java中集合类主要有两大分支:(1)Collection (2)Map先看它们的类图:(1)Collection(2)Map ...
  • 哪些集合类是线程安全的?

    千次阅读 2019-08-05 18:06:51
    答案: vector:就比arraylist多了个同步化机制(线程安全) ...这几个线程安全的集合类基本上都是jdk1.1中出现的,基本上实现方式就是直接对方法上锁,锁的粒度太大了,所以性能不是很好。 像vector因为效率...
  • 集合类(概念类)

    千次阅读 2018-04-07 18:21:07
    Java中的集合类集合的概念 Java中集合类是用来存放对象的 集合相当于一个容器,里面包容着一组对象——容器类 其中的每个对象作为集合的一个元素出现 Java API提供的集合类位于java.util包内Java中数组与集合的...
  • Java知识中有一个类集框架的概念,每种文献各有各的说法,也有的叫做Java集合类,造成混乱。并且概念中Collection翻译成中文又是类集的意思,Set翻译成中文是集合的意思,混乱的翻译、指代不明的名词概念以及网络上...
  • 常用集合类都有哪些?主要方法?

    千次阅读 2019-09-07 08:58:11
    常用集合类都有哪些?主要方法? 常见的集合 ArrayList,LinkedList,HashSet,HashMap,TreeSet 等等 常见方法: size() add() remove() 等等
  • Java哪些集合类是线程安全的?

    万次阅读 2019-07-05 15:30:43
    早在jdk的1.1版本中,所有的集合都是线程安全的。但是在1.2以及之后的版本中就出现了一些线程不安全的集合,为什么版本升级会出现一些线程不安全的集合呢?因为线程不安全的集合普遍比线程安全的集合效率高的多。...
  • java集合类List的用法

    千次阅读 2018-04-21 10:49:14
    为什么出现集合类 面对对象语言对事物的体现就是以对象的形式,所以方便多个对象的操作。Java提供了集合类 数组和集合的区别: A:长度区别 数组的长度固定 集合长度可变 B:数组中可以存储基本数据类型 集合...
  • Java集合类面试题

    千次阅读 2017-10-03 21:35:57
    每种编程语言中都有集合,最初的Java版本包含几种集合类:Vector、Stack、HashTable和Array。随着集合的广泛使用,Java1.2提出了囊括所有集合接口、实现和算法的集合框架。在保证线程安全的情况下使用泛型和并发集合...
  • C++集合类简介

    千次阅读 2019-03-05 00:02:25
    STL   STL是Standard Template Library的简称,中文名标准模板库,惠普实验室... 从根本上说,STL是一些“容器”的集合,这些“容器”有list,vector,set,map等,STL也是算法和其他一些组件的集合。这里的“容器...
  • 史上最全的Java集合类解析

    万次阅读 多人点赞 2016-11-10 17:03:05
    本文仅分析部分原理和集合类的特点,不分析源码,旨在对java的集合类有一个整体的认识,理解各个不同类的关联和区别,让大家在不同的环境下学会选择不同的类来处理。Java中的集合类包含的内容很多而且很重要,很多...
  • Java实用方法整理(五)——集合类常用方法

    万次阅读 多人点赞 2018-04-17 23:23:07
    1,集合概述 (1)集合的由来 Java是面向对象的语言,而面向对象语言对事物的描述是通过对象体现的,为了方便对多个对象进行操作,我们必须把多个对象进行存储。已有的容器类型有:数组和StringBuffer。但是,...
  • 之前的文章中,我们使用JOL工具简单的分析过String,数组和集合类的内存占用情况,这里再做一次更详细的分析和介绍,希望大家后面再遇到OOM问题的时候不再抱头痛哭,而是可以有章可循,开始吧。 数组 先看下JOL的代码...
  • Java基础: 线程安全的集合类

    千次阅读 2020-03-13 23:51:30
    集合中学到的ArrayList、LinkedList、HashSet、TreeSet、...如果程序中有多个线程可能访问以上这些集合,就可以使用Collections提供的方法把这些集合包装成线程安全的集合.Collections提供了如下静态方法. ...
  • Java集合类的基本接口

    千次阅读 2018-07-04 14:42:19
    java 集合类的基本接口:collection 和 map什么是接口:在软件中接口是一种规范和标准,他们可以约束类的行为,是一些方法特征的集合,但是没有方法的实现,接口其实上也可以看做是一个特殊的抽象类,但是采用和抽象...
  • C# 线程安全集合类

    千次阅读 2019-07-05 11:56:01
    从.Net 4.0框架开始,在System.Collections.Concurrent命名空间下,增加了用于多线程协同的并发集合类(线程安全集合)。 线程安全集合: 就是当多线程访问时,采用了加锁的机制;即当一个线程访问集合时,会对这个...
  • java中哪些集合类是安全的

    千次阅读 2020-06-28 23:59:14
    List item Vector Stack Hashtable java.util.concurrent 包下所有的集合类 ArrayBlockingQueue、 ConcurrentHashMap、 ConcurrentLinkedQueue、 ConcurrentLinkedDeque
  • Int类型的集合类的设计实现

    千次阅读 2017-10-19 17:00:48
    在本实例中,定义了一个int类型的集合类。实现了比较常用的增加数据,删除数据,排序等的具体操作。 先上图: 增加一个数5,默认增加到最后一个位置 在3号位置增加一个数9 删除第三个数 删除数值为3的数 从小到大...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,559,910
精华内容 623,964
关键字:

集合类