开发者社区> 游客wiepw7jj4edse> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

集合总结

简介: 集合总结
+关注继续查看

概念

集合:对象容器,实现对对象常用的操作

和数组区别

  1. 数组长度固定,集合长度不固定
  2. 数组可以存储基本类型和引用类型,集合只能存储引用类型

Collection体系

  • Collection:代表一组任意类型的对象
    • List:有序、有下标、元素可重复
      • ArrayList 【重点】
        • 数组结构实现,必须要连续空间,查询快、增删慢
        • jdk1.2版本,运行效率块、线程不安全
      • Vector
        • 数组结构实现,查询快、增删慢
        • jdk1.0版本,运行
      • LinkedList
        • 双向链表结构实现,无需连续空间,增删快,查询慢
    • Set

image

Collection父接口

特点:代表一组任意类型的对象

删除时只能靠元素,不能靠下标

image

常用方法

/**

* @author 伍六七

* @date 2022/8/12 19:37

*/

public class collection_demo {

    public static void main(String[] args) {

        //0创建集合

        Collection collection = new ArrayList();

        System.out.println(collection);//[]

        

        

        //1添加元素

        collection.add("1");

        collection.add("1");

        collection.add("2");

        System.out.println(collection);//[1, 1, 2]

        

        

        //2删除元素

        collection.remove("1");

        System.out.println(collection);//[1, 2]

        collection.clear();//[]

        System.out.println(collection);

        

        

        //3遍历

        //增强遍历

        for(Object o : collection){

            System.out.println(o);

        }

        

        //迭代器

        Iterator iterator = collection.iterator();

        while (iterator.hasNext()){

            String o = (String) iterator.next();

            System.out.println(o);

        }

        

        //4判断

        System.out.println(collection.contains("1"));//true

        System.out.println(collection.isEmpty());//false

    }

}


List子接口

特点:有序、有下标、元素可重复

删除时区别下标(int)与元素(String)image

常用方法

/**

 * @author 伍六七

 * @date 2022/8/12 20:26

 */

public class list_demo {

    public static void main(String[] args) {

        //0新建[]

        ArrayList list = new ArrayList();



        //1添加[4, 3, 2, 1, s, s]

        list.add("4");

        list.add("3");

        list.add("2");

        list.add(1);

        list.add("s");

        list.add("s");



        //2删除按照下标(int)按照参数(String)

        list.remove(1);//[4, 2, 1, s, s]

        list.remove("s");//[4, 2, 1, s]



        //3遍历

        //3.1for遍历

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

            System.out.print(list.get(i)+" ");//4 2 1 s

        }


        //3.2增强for

        for (Object l:list) {

            System.out.print(l+" ");//4 2 1 s


        }


        //3.3迭代器

        Iterator it = list.iterator();

        while (it.hasNext()){

            Object o =  it.next();

            System.out.print(o+" ");//4 2 1 s

            //可以使用it.remove(); 进行移除元素

            //不能使用collection其他方法 会报并发修改异常

            //it.remove();

        }


        //3.4列表迭代器

        ListIterator li = list.listIterator();

        while (li.hasNext()){

            System.out.printf(li.nextIndex()+":"+li.next()+" ");//0:4 1:2 2:1 3:s

        }

        while (li.hasPrevious()){

            System.out.printf(li.previousIndex()+":"+li.previous()+" ");//3:s 2:1 1:2 0:4

        }



        //4获取对应下标

        int i = list.indexOf(1);

        System.out.println(i);//2



        //5返回子集合(左闭右开)

        List list1 = list.subList(1, 3);

        System.out.println(list1);//[2, 1]

    }

}

List实现类

ArrayList

删除与List子接口方法一致

image

常用方法

/**

 * @author 伍六七

 * @date 2022/8/12 21:03

 */

public class arraylist_demo {

    public static void main(String[] args) {

        //0新建[]

        ArrayList arrayList  = new ArrayList<>();

        System.out.println(arrayList);//[]



        //1添加

        arrayList.add(1);

        arrayList.add("1");//会自动转化为int

        arrayList.add("s");

        arrayList.add("s");

        arrayList.add("l");

        System.out.println(arrayList);//[1, 1, s, s, l]



        //2删除按照下标(int)按照参数(String)

        arrayList.remove(1);

        System.out.println(arrayList);//[1, s, s, l]



        //3遍历

        //3.1迭代器

        Iterator it = arrayList.iterator();

        while(it.hasNext()){

            Object o = it.next();

            System.out.print(o+" ");//1 s s l

        }



        //3.1列表迭代器

        ListIterator li = arrayList.listIterator();

        //正序

        while(li.hasNext()){

            Object o = li.next();

            System.out.print(o+" ");//1 s s l

        }

        //倒序

        while(li.hasPrevious()){

            Object o = li.previous();

            System.out.printf(o+" ");//l s s 1

        }



        //4判断

        System.out.println(arrayList.contains(1));//true


        System.out.println(arrayList.isEmpty());//false



        //5获得下标

        System.out.println(arrayList.indexOf(1));//0

        System.out.println(arrayList.indexOf("s"));//1

    }

}

源码分析

DEFAULT_CAPACITY = 10; //默认容量

//注意:如果没有向集合中添加任何元素时,容量0,添加一个后,容量为10

//每次扩容是原来的1.5倍

elementData//存放元素的数组 

size //实际元素个数

image

image

image

LinkedList

创建链表集合

 LinkedList li = new LinkedList<>();

常用方法与List一致

vector

常用方法

增加、删除、判断同上

/**

 * @author 伍六七

 * @date 2022/8/12 21:31

 */

public class vector_demo {

    public static void main(String[] args) {

        //创建集合

        Vector vector = new Vector<>();



        //增加、删除、判断同上

        vector.add(1);

        vector.add(1);

        vector.add(2);

        vector.add("s");

        vector.add("l");//[1, 1, 2, s, l]

        vector.remove(4);//[1, 1, 2, s]

        vector.contains("s");//true

        vector.isEmpty();//false

        vector.indexOf("s");//3



        //遍历中枚举器遍历

        Enumeration en = vector.elements();

        while (en.hasMoreElements()){

            Object o = en.nextElement();

            System.out.printf(o+" ");//1 1 2 s 

        }

    }

}


Set接口

特点:无序、无下标、元素不可重复

方法:全部继承自Collection中的方法

增、删、遍历、判断与collection一致

HashSet

特点

存储结构:哈希表(数组+链表+红黑树)

存储过程(重复依据)

  1. 根据hashCode计算保存的位置,如果位置为空,直接保存,若不为空,进行第二步
  2. 再执行equals方法,如果equals为true,则认为是重复,否则形成链表

不理解

  • 基于HashCode计算元素存放位置
    • 利用31这个质数,减少散列冲突
      • 31提高执行效率 31 * i = (i << 5) - i 转为移位操作
    • 当存入元素的哈希码相同时,会调用equals进行确认,如果结果为true,则拒绝后者存入

/**

 * @author 伍六七

 * @date 2022/8/12 21:49

 */

public class hashset_demo {

    public static void main(String[] args) {

        //新建集合

        HashSet<String> hashSet = new HashSet<String>();



        //添加元素

        hashSet.add("1");

        hashSet.add("1");

        hashSet.add("1");

        hashSet.add("2");

        hashSet.add("3");

        System.out.println(hashSet);//[1, 2, 3]


        //删除元素

        hashSet.remove("1");

        System.out.println(hashSet);//[2, 3]



        //遍历操作

        //1. 增强for

        for(String set:hashSet){

            System.out.print(set);//23

        }


        //2. 迭代器

        Iterator<String> it = hashSet.iterator();

        while(it.hasNext()){

            String s = it.next();

            System.out.printf(s+" ");//2 3

        }



        //判断

        System.out.println(hashSet.contains("2"));//true


        System.out.println(hashSet.isEmpty());//false

    }

}

SortedSet接口

TreeSet

特点

  • 基于排列顺序实现元素不重复
  • 实现SortedSet接口(如果实现该接口需要重写方法),对集合元素自动排序
  • 元素对象的类型必须实现Comparable接口指定排序规则,默认升序
  • 通过CompareTo方法确定是否为重复元素

存储结构:红黑树

常用方法

还是set方法

//创建集合 

TreeSet<String> treeSet = new TreeSet<>();


//添加元素 

treeSet.add();


//删除元素 

treeSet.remove();


//遍历 1. 增强for 2. 迭代器


//判断 

treeSet.contains();

补充:TreeSet集合的使用

Comparator 实现定制比较(比较器)

Comparable 可比较的

// 重写compare,算法也用到,也可以用Lambda表达式

@override

public int compare(Person o1, Person o2){

  int n1 = o1.getAge()-o2.getAge();

  int n2 = o1.getName().comareTo(o2.getName());

  return n1 == 0 ? n2 : n1;

}

Map接口

https://www.cnblogs.com/coderzjz/p/13587167.html

特点

张三是人,李四也是人。

  1. 用于存储任意键值对(key - value)
  2. 键:无序、无下标、不允许重复(唯一)
  3. 值:无序、无下标、允许重复

常用方法

map.put()增加(如果之前有对应的健,则直接覆盖)

map.get()获取

map.remove()删除

map.keySet()返回所有健

map.values()返回包含所有值的Collection集合

map.entrySet()键值匹配的Set集合

/**

 * @author 伍六七

 * @date 2022/8/13 14:50

 * map接口特点

 * 1. 用于存储任意键值对(key - value)

 * 2. 键:无序、无下标、不允许重复(唯一)

 * 3. 值:无序、无下标、允许重复

 * 4.键值对这里可以理解为张三是人,李四也是人,前键后值

 */

public class map_demo {

    public static void main(String[] args) {

        //创建Map集合

        Map<String, String> map = new HashMap<>();



        // 1. 添加元素

        map.put("cike","wuliuqi");

        map.put("lifashi","wuliuqi");

        map.put("cike","wuliuqi1hao");//会替换前面的值

        map.put("lvshi","luoxiang");//{lvshi=luoxiang, cike=wuliuqi1hao, lifashi=wuliuqi}

        System.out.println(map);


        // 2. 删除

        map.remove("cike");

        System.out.println(map);//{lvshi=luoxiang, lifashi=wuliuqi}


        // 3.根据健返回值

        map.get("lifashi");//wuliuqi


        // 4. 遍历

        // 4.1 使用KeySet()所有Key的set集合

        Set<String> keyset = map.keySet(); // [lvshi, lifashi]


        // 4.2获取值的集合

        Collection<String> values = map.values();//[luoxiang, wuliuqi]


        // 4.3 使用entrySet()

        Set<Map.Entry<String, String>> entries = map.entrySet();//[lvshi=luoxiang, lifashi=wuliuqi]

    }

}


删除必须有健

image

HashMap【重点】

常用方法与map一致

基于哈希表对Map接口的实现,允许空值传入,但是遍历顺序不确定

线程不安全,多个线程同时写入HashMap,可能导致数据的不一致

存储结构:

  • 1.7 数组 + 链表----链表就是解决 hash 值冲突的,使用的是头插法。
  • 1.8 数组 + (链表 | 红黑树)--hashmap 的初始容量是 16,加载因子是 0.75,就是 16x0.75=12,超过就需要扩容为原来的两倍,当数组扩容大于 等于64,且链表长度大于阈值 8,链表就会转成红黑树,查询较快,在链表小于阈值 8 时,使用的是尾插法

基本属性

元素结构--Node

HashMap类中的元素是Node类,翻译过来就是节点,是定义在HashMap中的一个内部类

imageimage

  • hash:key的哈希值
  • key:节点的key,类型和定义HashMap时的key相同
  • value:节点的value,类型和定义HashMap时的value相同
  • next:该节点的下一节点

HashMap 的索引--Node的存储位置

对16取余

image

扩容介绍

  • 1.7 数组 + 链表----链表就是解决 hash 值冲突的,使用的是头插法。
  • 1.8 数组 + (链表 | 红黑树)--hashmap 的初始容量是 16,加载因子是 0.75,就是 16x0.75=12,超过就需要扩容为原来的两倍,当数组扩容大于 等于64,且链表长度大于阈值 8,链表就会转成红黑树,查询较快,在链表小于阈值 8 时,使用的是尾插法

树化----链表与红黑树的转换

链表--->红黑树是链表长度达到阈值是8,红黑树--->链表阈值为6。

链表长度设置为8和6的原因

基于泊松分布,因为经过计算,在hash函数设计合理的情况下,发生hash碰撞8次的几率为百万分之6,用概率证明。因为8够用了,至于为什么转回来是6,因为如果hash碰撞次数在8附近徘徊,会一直发生链表和红黑树的互相转化,为了预防这种情况的发生,设置为6

image

扩容结构--

  • size------------------HashMap中实际存在的键值对数量
  • modCount----------记录HashMap内部结构发生变化的次数
  • threshold-----------阈值,表示能容纳的键值对的临界值,等于数组长度*负载因子
  • loadFactor----------负载因子,默认0.75
  • HashMap默认容量--16

/**

 * 默认初始化容量16

     */

    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16


    /**

     *  最大容量,如果其中一个带参数的构造函数隐式指定更高的值,则使用该最大容量。

     *  必须是2的幂次方 

     */

    static final int MAXIMUM_CAPACITY = 1 << 30;


    /**

     * 默认负载因子,负责管理HashMap在何时开始扩容

     */

    static final float DEFAULT_LOAD_FACTOR = 0.75f;


    /**

     * 转为树的阈值

     */

    static final int TREEIFY_THRESHOLD = 8;


    /**

     * 取消树的值

     */

    static final int UNTREEIFY_THRESHOLD = 6;


    /**

     * 冲突严重时转为红黑树之前的最小阈值

     */

    static final int MIN_TREEIFY_CAPACITY = 64;

    

    

    /**

    *  存储数据的Node数组

    */

    transient Node<K,V>[] table;


    /**

     * Holds cached entrySet(). Note that AbstractMap fields are used

     * for keySet() and values().

     */

    transient Set<Map.Entry<K,V>> entrySet;


   /**

    *  大小

      */

    transient int size;


    /**

     * fail-fast.  (See ConcurrentModificationException).

     */

    transient int modCount;


    /**

     * 下一次应该扩容的大小 (capacity * load factor).

     * 如果尚未扩容,则该字段保存初始entry数组的容量,或用零表示

     */

    int threshold;


    /**

     * 负载因子

     */

    final float loadFactor;

image

image


注意!!长度扩大以后,Hash的规则也随之改变。

treeifyBin方法--扩容判断

image

image

final void treeifyBin(Node<K,V>[] tab, int hash) {

  //n数组长度,index 当前下标,e当前节点

        int n, index; Node<K,V> e;

  //判断数组是否为null,判断数组长度是否小于64,如果小于走扩容,不小于走链表转红黑树

        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)

            resize(); //扩容

  //数组长度减1和hash做与运算的当前下标index,取下标内元素,如果为null结束,不为null赋值给e 

        else if ((e = tab[index = (n - 1) & hash]) != null) {

   //hd头节点 tl尾节点

            TreeNode<K,V> hd = null, tl = null;

            do {

    //replacementTreeNode 添加接点e 进TreeNode

                TreeNode<K,V> p = replacementTreeNode(e, null);

    //判断尾节点 为null 说明没有根节点

                if (tl == null)

     //首节点(根节点) 指向当前节点

                    hd = p;

                else {

     //当前树节点的 前一个节点指向 尾节点

                    p.prev = tl;

     //尾节点的 后一个节点指向 当前节点

                    tl.next = p;

                }

    //把当前节点设置为尾节点

                tl = p;

            } while ((e = e.next) != null); //判断当前节点的下 当前节点的下一个节点是否为null 不为null 遍历

   //目前为止 也只是把Node改为TreeNode 也就是单向链表改为双向链表

   //根节点判断是否为 null 

            if ((tab[index] = hd) != null) 

                hd.treeify(tab); //转红黑树

        }

    }

为什么不一开始就使用红黑树,还要有一个转换的过程

单个 TreeNode 需要占用的空间大约是普通 Node 的两倍,所以只有当包含足够多的 Nodes 时才会转成 TreeNodes,而是否足够多就是由 TREEIFY_THRESHOLD 的值决定的。而当桶中节点数由于移除或者 resize 变少后,又会变回普通的链表的形式,以便节省空间。

image

重新实现hash方法-----为什么HashMap重新实现hash方法,直接用hashcode不行么?

减少碰撞

当向 HashMap 中添加一个元素的时候,需要根据 key 的 hash 值,去确定其在数组中的具体位置。HashMap 为了存取高效,减少碰撞,就是要尽量把数据分配均匀,每个链表长度大致相同,这个实现的关键就在把数据存到哪个链表中的算法。我们知道Object的hashcode有32位,而HashMap扩容之前的数组初始大小才16。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算,得到的余数才能用来访问数组下标。hash % length实际就是取模,计算机中直接求余效率不如位移运算。所以源码中做了优化,使用 hash & (length - 1),而实际上 hash % length 等于 hash & ( length - 1) 的前提是 length 是 2 的 n 次幂。这也是数组容量为何是 2 的 n 次幂。

小知识:

hash % length 等于 hash & ( length - 1)

hash % length

a=10,b=8,a%8=2

    

hash & ( length - 1) 

(前提b为2的整数次幂)

a=1010,b=1000

b-1=0111(任何数&(b-1)得到的数不会大于b,也就相当于对b取余)

      a  1010 10

    b-1  0111  8

a&(b-1)  0010  2

tab[i = (n - 1) & hash])

image

为什么要进行二次 hash?


HashMap 的 put 流程

网上借来的图

image

TreeMap

  • TreeMap存储 Key-Value 对时,需要根据 key-value 对进行排序。TreeMap 可以保证所有的 Key-Value 对处于有序状态。
  • TreeSet底层使用红黑树结构存储数据
  • TreeMap 的 Key 的排序:
  • 自然排序:TreeMap 的所有的 Key 必须实现 Comparable 接口,而且所有的 Key 应该是同一个类的对象,否则将会抛出 ClasssCastException
  • 定制排序:创建 TreeMap 时,传入一个 Comparator 对象,该对象负责对TreeMap 中的所有 key 进行排序。此时不需要 Map 的 Key 实现Comparable 接口
  • TreeMap判断两个key相等的标准:两个key通过compareTo()方法或者compare()方法返回0。

线程安全,运行效率慢;不允许null作为key或是value

Hashtable

线程安全,运行效率慢;不允许null作为key或是value

Properties

hashtable的子类,要求key和value都是string,通常用于配置文件的读取

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
体验总结
上手难度低 官网查询便捷
202 0
集合
set 什么是集合? 1.不同元素组成2.集合是无序的3.集合中的元素必须是不可变类型。 定义集合 s = {1,2,3,4,33,3,4,5} print(type(s)) --- class 'set' print(s) --- {33, 2, 3, 4, 5, 1} 集合是无序的,去重的。
1082 0
一周总结(十一)
距离上次总结过了两个星期了,时间过得真的很快。 上次总结,提到了自己做了Google Chrome浏览器插件,然后app基本可以使用了。毕竟之前有些闭门造车,没有拿出去给用户使用。
753 0
集合
集合由若干个元素组成,有三个特点。 1.确定性。集合中的元素必须是确定的; 2.互异性。集合中的元素互不相同; 3.无序性。集合中的元素没有先后之分。 符号表示 我们通常用大写字母如A,B,S,T,…表示集合,而用小写字母如a,b,x,y,…表示集合的元素。 元素与集合 若x是集合S的元素,则称x属于S,记为x∈Sx \in S。若y不是集合S的元素,则称y
935 0
总结---3
Email relay 和Email access分别用了什么协议?答:SMTP,POP3 1:多态是如何实现绑定的?   多态的绑定可以分为运行是多态和编译时多态 ● 编译时的多态性 编译时的多态性是通过重载来实现的。
719 0
10
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载