<返回更多

Java集合详解

2020-03-01    
加入收藏

集合类简述

在没有集合类之前,实际上在JAVA语言里已经有一种方法可以存储对象,那就是数组。数组不仅可以存放基本数据类型也可以容纳属于同一种类型的对象。数组的操作是高效率的,但也有缺点。比如数组的长度是不可以变的,数组只能存放同一种类型的对象(或者说对象的引用)。

为了使程序方便地存储和操纵数目不固定的一组数据,JDK中提供了Java集合类,所有Java集合类都位于Java.util包中,与Java数组不同,Java集合不能存放基本数据类型数据,而只能存放对象的引用。

集合特点

集合类的特点有三个:

第一点,集合类这种框架是高性能的。对基本类集(动态数组,链接表,树和散列表)的实现是高效率的。一般人很少去改动这些已经很成熟并且高效的APl;

第二点,集合类允许不同类型的集合以相同的方式和高度互操作方式工作;

第三点,集合类容易扩展和修改,程序员可以很容易地稍加改造就能满足自己的数据结构需求。

集合分类

Java中的集合类可以分为两大类:一类是实现Collection接口;另一类是实现Map接口

Collection是一个基本的集合接口,Collection中可以容纳一组集合元素(Element)。

Collection接口中定义了一些操作集合的API:

Java集合详解

 

Collection有两个重要的子接口List和Set,它们都有各自经常使用的实现类,关系如下:

Java集合详解

 

Map没有继承Collection接口,与Collection是并列关系。Map提供键(key)到值(value)的映射。一个Map中不能包含相同的键,每个键只能映射一个值。

Map中也提供了一些操作Map的API:

Java集合详解

 

Map接口的一些常用实现类如下:

Java集合详解

 

List

List表达一个有序的集合,List中的每个元素都有索引,使用此接口能够准确的控制每个元素插入的位置。用户也能够使用索引来访问List中的元素,List类似于Java的数组。

List接口有两个经常使用的实现类,ArrayList和LinkedList。还有一个实现类Vector,不过实际开发中很少用。它们之间的区别为:

适用场景分析:当需要对数据进行对此访问的情况下选用ArrayList,当需要对数据进行多次增加删除修改时采用LinkedList。

Java集合详解

 

Set

Set接口的特点是不能包含重复的元素。对Set中任意的两个元素element1和element2都有elementl.equals(element2)= false。另外,Set最多有一个null元素。

Set接口常用的两个实现类是HashSet和TreeSet,两者的区别如下:

适用场景分析:HashSet是基于Hash算法实现的,其性能通常都优于TreeSet。为快速查找而设计的Set,我们通常都应该使用HashSet,在我们需要排序的功能时,我们才使用TreeSet。

此外,还有一种Set类型,LinkedHashSet,它是HashSet的子类,底层数据结构采用链表+哈希表,链表保证元素的添加顺序,哈希表保证元素的唯一性。

Java集合详解

 

延伸一个面试题:HashSet是如何保证元素的唯一性?

当调用add()方法向集合中存入对象的时候,首先会使用 hash() 函数生成一个 int 类型的 hashCode 散列值,然后与已经存储的元素的 hashCode 值作比较,如果 hashCode 值不相等,则所存储的两个对象一定不相等,此时把这个新元素存储在它的 hashCode 位置上;如果 hashCode 相等,存储元素的对象还是不一定相等,此时会调用 equals() 方法判断两个对象的内容是否相等,如果 equals() 返回true,则是同一个对象,无需存储;如果 equals() 返回 false,那么就是不同的对象,就需要存储,不过由于 hashCode 相同,HashSet会以链式结构将两个对象保存在同一位置,这将导致性能下降,因此在编码时应避免出现这种情况。

List与Set选型

List与Set都是存储对象的,那我们实际开发中应该如何选择呢?可以参考下图:

Java集合详解

 

Map

Map用于保存具有映射关系的数据,Map里保存着两组数据:key和value,它们都可以使任何引用类型的数据,但key不能重复。所以通过指定的key就可以取出对应的value。

Map接口有四个比较重要的实现类,分别是HashMap、LinkedHashMap、TreeMap和HashTable。它们的区别如下:

Java集合详解

 

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

遍历Map的四种方式

Map不同于List和Set,它存储的是key-value的键值对,不能像List和Set那样直接使用 for 循环遍历,可以通过下面四种方式遍历Map:

Java集合详解

 

必问面试题:HashMap的底层实现

HashMap采用Entry数组来存储key-value对,每一个键值对组成了一个Entry实体,Entry类实际上是一个单向的链表结构,它具有Next指针,可以连接下一个Entry实体。 只是在JDK1.8中,链表长度大于8的时候,链表会转成红黑树。

在调用 HashMap 的 put 方法添加元素时,会对key的hashCode()做hash运算,计算index; 如果没碰撞直接放到bucket里; 如果碰撞了,以链表的形式存在buckets后; 如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD),就把链表转换成红黑树(JDK1.8中的改动); 如果节点已经存在就替换old value(保证key的唯一性) 如果bucket满了(超过load factor*current capacity),就要resize。

在调用 HashMap 的 get 方法获取元素时,会对key的hashCode()做hash运算,计算index; 如果在bucket里的第一个节点里直接命中,则直接返回; 如果有冲突,则通过key.equals(k)去查找对应的Entry。

上面只是简单的说了下 HashMap 在 put 和 get 时的主要过程,后期我会单独开一篇文章,根据 HashMap 的源码来说明它的具体原理。

声明:本站部分内容来自互联网,如有版权侵犯或其他问题请与我们联系,我们将立即删除或处理。
▍最近更新
更多资讯 >>>