首页 > 代码库 > 关于集合

关于集合

一、数组和集合的区别:

(1)数组是大小固定的,并且同一个数组只能存放类型一样的数数据(基本类型/引用类型)。

(2)Java集合可以存储和操作数目不固定的一组数据。

(3)在不知道需要多少对象时,使用集合。

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

(1)set(集):是最简单的一种集合,只能通过游标来取值。/它的对象不按特定方式排序,只是简单的把对象加入集合中,就像往口袋里放东西。对集中成员的访问和操作是通过集中对象的引用进行的,所以集中不能有重复对象。

(2)list(列表):列表的主要特征是其对象以线性方式存储,没有特定顺序,只有一个开头和一个结尾,当然,它与根本没有顺序的集是不同的。列表在数据结构中分别表现为:数组和向量、链表、堆栈、队列。
(3)map(映射):映射与集或列表有明显区别,映射中每个项都是成对的。映射中存储的每个对象都有一个相关的关键字(Key)对象,关键字决定了 对象在映射中的存储位置,检索对象时必须提供相应的关键字,就像在字典中查单词一样。关键字应该是唯一的。关键字本身并不能决定对象的存储位置,它需要对过一种散列(hashing)技术来处理,产生一个被称作散列码(hash code)的整数值,
散列码通常用作一个偏置量,该偏置量是相对于分配给映射的内存区域起始位置的,由此确定关键字/对象对的存储位置。理想情况 下,散列处理应该产生给定范围内均匀分布的值,而且每个关键字应得到不同的散列码。

技术分享

list和set的区别:虽然Set同List都实现了Collection接口,但是他们的实现方式却大不一样。List基本上都是以Array为基础。但是Set则是 在HashMap的基础上来实现的,这个就是Set和List的根本区别。HashSet的存储方式是把HashMap中的Key作为Set的对应存储项。看看 HashSet的add(Object obj)方法的实现就可以一目了然了。

1、ArrayList、LinkedList和Vector是三个主要的实现类。 ArrayList 是线程不安全的, Vector 是线程安全的,这两个类底层都是由数组实现的 LinkedList 是线程不安全的,底层是由链表实现的 。
(安全与快速问题的理解 :一个 ArrayList ,在添加一个元素的时候,它可能会有两步来完成: 1、在 Items[Size] 的位置存放此元素;  2. 增大 Size 的值。在单线程运行的情况下,如果 Size = 0,添加
一个
元素后,此元素在位置 0,而且 Size=1; 而如果是在多线程情况下,比如有两个线程,线程 A 先将元素存放在位置 0。但是此时 CPU 调度线程A暂停,线程 B 得到运行的机会。线程B也向此 ArrayList 添

加元素,因为此时 Size 仍然等于 0(注意哦,我们假设的是添加一个元素是要两个步骤哦,而线程A仅仅完成了步骤1),所以线程B也将元素存放在位置0。然后线程A和线程B都继续运行,都增加 Size 的值。

所以现在我们来看看 ArrayList 的情况,元素实际上只有一个,存放在位置 0,而 Size 却等于 2。这就是“线程不安全”啦。)
2、HashSet和TreeSet是Set的两个主要的实现类。

三、详情

1、ArrayList 是一个数组队列,相当于动态数组。它由数组实现,随机访问效率高,随机插入、随机删除效率低。

一个 ArrayList ,在添加一个元素的时候,它可能会有两步来完成: 
    首先第一步. 在 Items[Size] 的位置存放此元素。 第二步 ,增大 Size 的值。 在单线程运行的情况下,如果 Size = 0,添加一个元素后,此元素在位置 0,而且 Size=1;而如果是在多线程情况下,比如有两个线程 ,线程 A 先将元素存放在位置 0。但是此时 CPU 调度线程A暂停,线程 B 得到运行的机会。线程B也向此 ArrayList 添加元素,因为此时 Size 仍然等于 0 (注意哦,我们假设的是添加一个元素是要两个步骤哦,而线程A仅仅完成了步骤1),所以线程B也将元素存放在位置0。然后线程A和线程B都继续运行,都增加 Size 的值。 那好,现在我们来看看 ArrayList 的情况,元素实际上只有一个,存放在位置 0,而 Size 却等于 2。这就是“线程不安全”了。

2  、LinkedList 是一个双向链表。它也可以被当作堆栈、队列或双端队列进行操作。LinkedList随机访问效率低,但随机插入、随机删除效率高。

原理:通过add(int index, E elmt)向LinkedList插入元素时。先是在双向链表中找到要插入节点的位置index;找到之后,再插入一个新节点。双向链表查找index位置的节点时,有一个加速动作:若index < 双向链表长度的1/2,则从前向后查找; 否则,从后向前查找。

3、Vector 是矢量队列,和ArrayList一样,它也是一个动态数组,由数组实现。但是ArrayList是非线程安全的,而Vector是线程安全的。

4、HashSet:哈希表是通过使用称为散列法的机制来存储信息的,元素并没有以某种特定顺序来存放;不能保证元素的排列顺序,顺序有可能发生变化;不是同步的;集合元素可以是null,但只能放入一个null(因为集合中的元素不允许重复)

5、TreeSet:提供一个使用树结构存储Set接口的实现,对象以升序顺序存储,访问和遍历的时间很快。且TreeSet是SortedSet接口的唯一实现类,TreeSet可以确保集合元素处于排序状态。TreeSet支持两种排序方式,自然排序 和定制排序,其中自然排序为默认的排序方式。

 

关于集合