数组和集合哪个效率高_Java集合

1、Java集合的诞生

通常，我们的Java程序需要根据程序运行时才知道创建了多少个对象。但若非程序运行，程序开发阶段，我们根本不知道到底需要多少个数量的对象，甚至不知道它的准确类型。为了满足这些常规的编程需要，我们要求能在任何时候，任何地点创建任意数量的对象，而这些对象用什么来容纳呢？我们首先想到了数组，但是！数组只能存放同一类型的数据，而且其长度是固定的，那怎么办呢？集合便应运而生了。

2、什么是Java集合

  • Java集合类存放在java.util包中，是一个用来存放对象的容器。

  • Java集合只能存放对象，比如当我们存入int型数放入集合中，它会自动转化为Integer类型。

  • 集合存放的都是对象的引用，而非对象本身。所以我们称集合中的对象就是集合中对象的引用。对象本身还是存放在堆内存中。

  • 集合可以存放不同类型、不限数量的数据类型。

3、集合和数组的区别：

  • 长度区别：

    • 数组固定

    • 集合可变

  • 内容区别：

    • 数组可以是基本数据类型，也可以是引用类型

    • 集合只能是引用类型

  • 元素内容

    • 数组只能存储同一种类型

    • 集合可以存储不同类型

4、常用集合分类

Collection 接口：对象的集合

  • List 接口：有序、可重复

    • LinkList 接口实现类，链表、没有同步，线程不安全，增删速度快

    • ArrayList 接口实现类，数组、没有同步，线程不安全，随机访问

    • Vector 接口实现类，数组，同步，线程安全

  • Set 接口：不可重复，内部排序

    • HashSet 使用hash表(数组)存储元素

    • TreeSet 底层实现为二叉树

Map 接口：键值对的集合

  • Hashtable 接口实现类，同步，线程安全

  • HashMap 接口实现类，没有同步，线程不安全

    • LinkedHashMap 双向链表和哈希表实现

  • TreeMap 红黑树对所有的key进行排序

5、List详解

  • ArrayList 解析(底层数据结构是数组，查询快，增删慢，线程不安全，效率高，可以存储重复元素 )

026b7a5857939971651a96ba938cbfb7.png

根据上面我们可以清晰的发现：ArrayList底层其实就是一个数组，ArrayList中有扩容这么一个概念，正因为它扩容，所以它能够实现“动态”增长。

  • 构造方法

    0987c2b7ca7fcab912d4594e291ea7ab.png

  • add方法

cb764bd26c87077f65fedf8e90318936.png

步骤：

1️⃣调用 ensureCapacityInternal(size + 1); 检查是否需要扩容

2️⃣确认list容量，尝试容量加1是否满足，

02f996b13213842a8bb08387315bf458.png

3️⃣ 调用ensureExplicitCapacity(minCapacity);方法，来确定容量；如果要的最小容量比数组的长度要大，就调用grow()来扩容，相当于扩容1.5倍(当添加第11个元素时，minCapacity为11，数组长度为10，那么就需要扩容了)，

c51c2edbcf2d29d6eebfa6435544a962.png

  • get()方法

        public E get(int index) {        rangeCheck(index);   //检查角标        return elementData(index);  //返回具体元素    }

  • set()方法

        public E set(int index, E element) {        rangeCheck(index);        E oldValue = elementData(index);//检查角标        elementData[index] = element;   //替换元素        return oldValue;                    //返回旧值      }

  • remove()方法(检查角标、删除元素、计算出需要移动的个数，并移动，gc回收)

  • af176ab88a9b7fb0bbf576e53a4be0cb.png

  • ArrayList总结：

    • ArrayList是基于动态数组实现的，在增删时候，需要数组的拷贝复制。

    • ArrayList的默认初始化容量是10，每次扩容时候增加原先容量的一半，也就是变为原来的1.5倍

    • 删除元素时不会减少容量，若希望减少容量则调用trimToSize()

    • 它不是线程安全的。它能存放null值。

  • Vector解析(底层数据结构是数组，查询快，增删慢，线程安全，效率低，可以存储重复元素 )

    • Vector是jdk1.2的类了，比较老的一个集合类，Vector底层也是数组，与ArrayList最大的区别的就是：同步(线程安全)

    • 线程安全，方法都由synchronized修饰。

    • 扩容为原来的2倍

  • LinkedList解析(底层数据结构是链表，查询慢，增删快，线程不安全，效率高，可以存储重复元素)

    LinkedList的方法比ArrayList的方法多太多了，这里我就不一一说明了。具体可参考：https://blog.csdn.net/panweiwei1994/article/details/77110354。

6、set详解

  • HashSet(无序，允许为null，底层是HashMap(散列表+红黑树)，非线程同步)

    • 我们知道Map是一个映射，有key有value，既然HashSet底层用的是HashMap，那么value在哪里呢？？？

    • 从下面的源代码我们可以直接总结出：HashSet实际上就是封装了HashMap，操作HashSet元素实际上就是操作HashMap。

5210bbc01ee9675fedbae184e193b5e9.png

  • TreeSet(有序，不允许为null，底层是TreeMap(红黑树),非线程同步)

    • 底层实际上是一个TreeMap实例

5a925e37e82450ee8a85fdba5bb50798.png

  • LinkedHashSet(迭代有序，允许为null，底层是HashMap+双向链表，非线程同步)

    • 迭代是有序的

    • 允许为null

    • 底层实际上是一个HashMap+双向链表实例(其实就是LinkedHashMap)

    • 非同步

    • 性能比HashSet差一丢丢，因为要维护一个双向链表

    • 初始容量与迭代无关，LinkedHashSet迭代的是双向链表

7、Map详解

前面我们学习的Collection叫做集合，它可以快速查找现有的元素。而Map在《Core Java》中称之为-->映射，就是key----------value的形式。那为什么我们需要这种数据存储结构呢？举个例子；作为学生来说，我们是根据学号来区分不同的学生。只要我们知道学号(key)，就可以获取对应的学生信息(value)。这就是Map映射的作用！

  • Map与Collection的区别

    • Map集合储存元素是成对出现的，Map的键是唯一的，值是可以重复的。

    • Collection集合存储元素是单独出现的，Collection的儿子Set是唯一的，List是可以重复的

    • Map集合的数据结构针对键有效，跟值无关

    • Collection集合的数据结构针对元素有效

  • Map的常用方法及功能

  • 7ce04a6b959f7abc37b424c28466dd37.png

  • HashMap

    • 计算node节点的位置的算法是(n-1)&hash，n代表map的容量，扩容后的容量n只是在二进制高位多了个1，实际上去判断与之对应的hash值的二进制为0或1就可以明确map扩容后节点的位置是否需要发生变化，若hash对应的二进制为1，则证明索引需要变化，变化的大小只需要加上旧map的容量即可。(因为map扩容后容量的高位多了个1，就需要比较前后两次(n-1)&hash的值是否相同)

    • HashMap基于Map接口实现，元素以键值对的方式存储，并且允许空键和空值，但是由于key不可重复，所以只允许有一个键为空。HashMap 是无序的，HashMap是线程不安全的。HashMap是一个散列表的数据结构，即数组和链表的结合体，他的底层是一个数组结构，数组中的每一项又是一个链表结构。

    • 当我们往HashMap中put元素的时候，先根据key的hashCode重新计算hash值，根据hash值得到这个元素在数组中的位置(即下标)，如果数组该位置上已经存放有其他元素了，那么在这个位置上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。如果数组该位置上没有元素，就直接将该元素放到此数组中的该位置上。

    • jdk7是将节点重新hash，分配到新的数组中。

    • jdk8是将节点的hash值和旧hashmap的容量进行与运算，若与的结果为0，则扩容后的位置跟原位置一样。如果结果为不为0，扩容后的位置=原索引位置加上旧hashmap的容量

    • HashMap 是一个最常用的Map,它根据键的HashCode 值存储数据,根据键可以直接获取它的值，具有很快的访问速度。

    • HashMap最多只允许一条记录的键为Null;允许多条记录的值为 Null;

    • HashMap不支持线程的同步，即任一时刻可以有多个线程同时写HashMap;可能会导致数据的不一致。如果需要同步，可以用 Collections的synchronizedMap方法使HashMap具有同步的能力，或者使用ConcurrentHashMap。

    • HashMap基于哈希表结构实现的 ，当一个对象被当作键时，必须重写hasCode和equals方法。

  • LinkedHashMap

    • LinkedHashMap内部是双向链表结构，保存了元素插入的顺序，Iterator遍历元素时按照插入的顺序排列，支持线程同步。

  • TreeMap

    • TreeMap基于红黑树数据结构的实现，键值可以使用Comparable或Comparator接口来排序。TreeMap继承自AbstractMap，同时实现了接口NavigableMap，而接口NavigableMap则继承自SortedMap。SortedMap是Map的子接口，使用它可以确保图中的条目是排好序的。

    • 在实际使用中，如果更新图时不需要保持图中元素的顺序，就使用HashMap，如果需要保持图中元素的插入顺序或者访问顺序，就使用LinkedHashMap，如果需要使图按照键值排序，就使用TreeMap。

  • Hashtable

    • Hashtable和前面介绍的HashMap很类似，它也是一个散列表，存储的内容是键值对映射，不同之处在于，Hashtable是继承自Dictionary的，Hashtable中的函数都是同步的，这意味着它也是线程安全的，另外，Hashtable中key和value都不可以为null。

  • 散列表介绍

    无论是Set还是Map，我们会发现都会有对应的-->HashSet,HashMap

    首先我们也先得回顾一下数组和链表：

    而还有另外的一些存储结构：不在意元素的顺序，能够快速的查找元素的数据

    • 其中就有一种非常常见的：散列表

    • 链表和数组都可以按照人们的意愿来排列元素的次序，他们可以说是有序的(存储的顺序和取出的顺序是一致的)

    • 但同时，这会带来缺点：想要获取某个元素，就要访问所有的元素，直到找到为止。

    • 这会让我们消耗很多的时间在里边，遍历访问元素~

  • 散列表的工作原理

    散列表为每个对象计算出一个整数，称为散列码。根据这些计算出来的整数(散列码)保存在对应的位置上！在Java中，散列表用的是链表数组实现的，每个列表称之为桶。    

    94adb17fe3795233bc231077fcd5188b.png

                                       (图片来自于网络)

    一个桶上可能会遇到被占用的情况(hashCode散列码相同，就存储在同一个位置上)，这种情况是无法避免的，

    如果散列表太满，是需要对散列表再散列，创建一个桶数更多的散列表，并将原有的元素插入到新表中，丢弃原来的表~这种现象称之为：散列冲突

    • 装填因子(load factor)决定了何时对散列表再散列~

    • 装填因子默认为0.75，如果表中超过了75%的位置已经填入了元素，那么这个表就会用双倍的桶数自动进行再散列

    • 此时需要用该对象与桶上的对象进行比较，看看该对象是否存在桶子上了~如果存在，就不添加了，如果不存在则添加到桶子上

    • 当然了，如果hashcode函数设计得足够好，桶的数目也足够，这种比较是很少的~

    • 在JDK1.8中，桶满时会从链表变成平衡二叉树

  • 红黑树

    • 附上两篇文章：

    • https://riteme.github.io/blog/2016-3-12/2-3-tree-and-red-black-tree.html#fn:red-is-left

    • https://blog.csdn.net/chen_zhang_yu/article/details/52415077

  • 最后附上一篇集合详解的文章：https://www.cnblogs.com/linliquan/p/11323172.html

版权声明：本文为weixin_39929566原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。