1. Collection
Collection 是所有集合类的父接口,它定义了集合类最基本的操作方法:
Collection 接口
2. List
列表(List)实现了Collection,并拥有自己的特性:可以有重复元素,且是有序的,以元素添加顺序为序。该类集合中有索引【角标】。
ArrayList 底层数据结构是数组存储,查询速度快,但是增删改慢,非线程安全,长度大约0.5倍增长(len += len>>1)
ArrayList 用法
ArrayList 实现原理
LinkedList 底层数据链结构是表结构,增删改速度快,但查询慢,非线程安全,链表长度即为元素长度。
LinkedList 用法
Vector 底层实现与ArrayList一样,但是线程同步的,相比于ArrayList,查询增删都慢,长度1倍增长。
Stack 继承于 Vector ,实现了一种后进先出(LIFO)的数据结构,栈。
3. Set
集(Set)也实现了 Collection 接口,它与列表的区别在于,不允许与重复元素,且元素是无序的(元素的有序性是指与插入顺序一致)。这类集合中没有索引。
Set有两种实现类,且底层都是用Map实现的:
HashSet:底层用HashMap实现,元素存在map的key中(key, new Object()),元素无序。
TreeSet: 底层用TreeMap实现,元素存在map的key中(key, new Object()),元素无序,但是元素是升序排列的。
HashSet
底层数据: 底层使用哈希表作为数据结构。
元素唯一性: 是通过元素的两个方法: hashCode 和 equals 来完成的。
如果两个元素的HashCode值相同,就会判断equals是否为true。
如果两个元素的HashCode值不同,就不会调用equals方法。
注意:对于判断元素是否存在、删除等操作,都依赖于元素的hashCode、equals等方法。
哈希表:给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,
则称表M为哈希(Hash)表,函数f(key)为哈希(Hash) 函数。
(哈希值与内存地址值之间的关系:默认的哈希值是内存地址值计算的哈希值,但是只是为了给人看的,真正在
内存中还是依靠内存地址值来进行运算的,而不是哈希值)
TreeSet
底层数据结构: 二叉树 (保证元素唯一性的方法是保证compareTo 方法return 0)
比较方式:
方式一、就是让元素自己具有比较性,元素需要实现comparable接口,重写其中得compareTo方法,这个排序叫做自然排序(默认排序)
1、 无序性(按照输入元素类中自定义的compareTo方法来排定存储对象。)
2、 单一性(通过判断元素类中自定义的compareTo方法放回值是否为0来判断元素是否相等。)
3、 让需要存入到TreeSet中的元素,实现comparable接口,该接口中定义了一个public int compareTo方法
4、 compareTo 方法:我们需要在类定义中重写该方法, public int compareTo,
使得: 当有pareTo(e1)时,
如果e大于e1则返回正数,当e小于e1则返回负数, 等于则返回0.
而且当有e等于e1时, 可以定义附属判断条件来判断 两个对象的大小。
注意:TreeSet 本情况的所有的底层比较原理只是调用了元素的compareTo方法,与 equals等方法都无关。
(add、contains、remove等需要用到比较的方法)
所以我们定义所有的比较都返回正数,那么靠遍历迭代器取出的元素顺序和存入顺序一样。
如果定义所有的比较都返回负数,那么靠遍历迭代器去除的元素顺序和存入的顺序相反。
如果定义所有比较都返回0 ,那么就只能存入一个元素,最后也只能取出一个元素。
方式二、当元素自身没有比较性或者具有的比较性不是自身所需要的,那么就要让集合自身具有比较性。
那么就要在集合一初始化时定义比较方式(也就是调用集合的构造方法)
1、 无序性(按照集合实例化的时候的比较器来排布元素的存储顺序。)
2、 单一性(通过集合的比较器的compare方法返回值是否为0 来判断元素是否相等。)
3、 定义一个比价器的类,使其实现comparator接口, 重写覆盖其中的 int compare(T o1, T o2) 方法。
4、 compare 方法:我们需要在比较器类定义中重写该方法,int compare(Object o1, Object o2),
使得: 我们在该方法中比较两个对象,或者比较其对象的方法,或者直接定义一个数值返回。
当返回值为正时代表o1大于o2,当返回值为负时代表o1小于o2,返回值为0 则代表两个对象相等。
而且当初步判断有o1等于o1时, 可以定义附属判断条件来判断 两个对象的大小。
注意:TreeSet 本情况的所有的底层比较原理只是调用了集合比较器的compare方法,与 元素equals等方法都无关。
(add、contains、remove等需要用到比较的方法)
所以我们定义所有的比较都返回正数,那么靠遍历迭代器取出的元素顺序和存入顺序一样。
如果定义所有的比较都返回负数,那么靠遍历迭代器去除的元素顺序和存入的顺序相反。
如果定义所有比较都返回0 ,那么就只能存入一个元素,最后也只能取出一个元素。
4. Map
映射(Map)没有实现 Collection 接口,它的每一项都是成对存储的,(key, value)。存储的每一个数据都有一个对应的关键字key,key 是唯一的。
key虽然决定了数据在映射中存储的位置,检索数据时,需要提供相应的Key。但是并不是靠key本身来确定的,而是使用了一种散列(hashing)技术来处理,产生一个被称为散列码(hash code)的整数值,它通常作为一个偏置量,该偏置量是相对于数据存储位置与map内存起始位置的偏移,由此来确定(key, value)的存储位置。
理想情况下,散列处理应该产生给定范围内均匀分布的值,而且每个关键字应得到不同的散列码。
Map有多种实现:
HashMap:非线程安全,底层为散列表,允许存储一个 null key,和多个 null value。
HashTable:线程安全,执行效率较低。所有的 key 必须非null。为了能更高效的工作,所有的类必须实现 equal()和 hashcode()方法。
LinkedHashMap:非线程安全,底层实现为散列表,能够保证元素的插入顺序(相对于读取而言的)。
WeakHashMap:非线程安全,底层实现为散列表,当某个键不在被引用时,其对应的键值对可能会对GC回收,从map中清除。
TreeMap:底层为二叉树结构,元素按key值升序排列,不是按插入顺序。
如果觉得《collection集合 地址_有容乃大--Java 集合(List/Set/Map)》对你有帮助,请点赞、收藏,并留下你的观点哦!