Java集合详解【面试+提高】 在说集合前我们不得不说一下数组 存放一组相同的数据类型(基本或对象)的数据,从而实现对数据的管理 一、数组和集合的比较 数组不是面向对象的,存在明显的缺陷,集合弥补了数组的缺点,比数组更灵活更实用,而且不同的集合框架类可适用不同场合。如下: 二、Java集合 此图可用Windows系统自带画图工具查看比较清晰 Collection和Map,是集合框架的根接口。 Collection的子接口: Set:接口 ---实现类: HashSet、LinkedHashSet List集合 有序列表,允许存放重复的元素; ArrayList 底层是Object数组,所以ArrayList具有数组的查询速度快的优点以及增删速度慢的缺点。 而在LinkedList的底层是一种双向循环链表。在此链表上每一个数据节点都由三部分组成:前指针(指向前面的节点的位置),数据,后指针(指向后面的节点的位置)。最后一个节点的后指针指向第一个节点的前指针,形成一个循环。 双向循环链表的查询效率低但是增删效率高。 ArrayList和LinkedList在用法上没有区别,但是在功能上还是有区别的。 LinkedList LinkedList是采用双向循环链表实现的。 经常用在增删操作较多而查询操作很少的情况下: 队列和堆栈。 队列:先进先出的数据结构。 栈:后进先出的数据结构。 注意:使用栈的时候一定不能提供方法让不是最后一个元素的元素获得出栈的机会。 Vector (与ArrayList相似,区别是Vector是重量级的组件,使用使消耗的资源比较多。) 结论:在考虑并发的情况下用Vector(保证线程的安全)。 在不考虑并发的情况下用ArrayList(不能保证线程的安全)。 ArrayList自动扩充机制
List常用方法: Set集合 扩展Collection接口 HashSet 的后台有一个HashMap;初始化后台容量;只不过生成一个HashSet的话,系统只提供key的访问; 如果有两个Key重复,那么会覆盖之前的; HashSet类HashSet类直接实现了Set接口, 其底层其实是包装了一个HashMap去实现的。HashSet采用HashCode算法来存取集合中的元素,因此具有比较好的读取和查找性能。 HashSet的特征
HashSet的equals和HashCode前面说过,Set集合是不允许重复元素的,否则将会引发各种奇怪的问题。那么HashSet如何判断元素重复呢? HashSet需要同时通过equals和HashCode来判断两个元素是否相等,具体规则是,如果两个元素通过equals为true,并且两个元素的hashCode相等,则这两个元素相等(即重复)。 所以如果要重写保存在HashSet中的对象的equals方法,也要重写hashCode方法,重写前后hashCode返回的结果相等(即保证保存在同一个位置)。所有参与计算 hashCode() 返回值的关键属性,都应该用于作为 equals() 比较的标准。 试想如果重写了equals方法但不重写hashCode方法,即相同equals结果的两个对象将会被HashSet当作两个元素保存起来,这与我们设计HashSet的初衷不符(元素不重复)。 另外如果两个元素哈市Code相等但equals结果不为true,HashSet会将这两个元素保存在同一个位置,并将超过一个的元素以链表方式保存,这将影响HashSet的效率。 如果重写了equals方法但没有重写hashCode方法,则HashSet可能无法正常工作,比如下面的例子。 上面注释了hashCode方法,所以你将会看到下面的结果。 false [R[count:9 # hashCode:14927396], R[count:5 # hashCode:24417480], R[count:-2 # hashCode:31817359], R[count:-3 # hashCode:13884241]] 取消注释,则结果就正确了 copy true [R[count:5 # hashCode:5], R[count:9 # hashCode:9], R[count:-3 # hashCode:-3], R[count:-2 # hashCode:-2]]
LinkedHashSet的特征 LinkedHashSet是HashSet的一个子类,LinkedHashSet也根据HashCode的值来决定元素的存储位置,但同时它还用一个链表来维护元素的插入顺序,插入的时候即要计算hashCode又要维护链表,而遍历的时候只需要按链表来访问元素。查看LinkedHashSet的源码发现它是样的, 在JAVA7中, LinkedHashSet没有定义任何方法,只有四个构造函数,它的构造函数调用了父类(HashSet)的带三个参数的构造方法,父类的构造函数如下, 由此可知,LinkedHashSet本质上也是从LinkedHashMap而来,LinkedHashSet的所有方法都继承自HashSet, 而它能维持元素的插入顺序的性质则继承自LinkedHashMap. 下面是一个LinkedHashSet维持元素插入顺序的例子, 输入如下 TreeSet类的特征TreeSet实现了SortedSet接口,顾名思义这是一种排序的Set集合,查看jdk源码发现底层是用TreeMap实现的,本质上是一个红黑树原理。 正因为它是排序了的,所以相对HashSet来说,TreeSet提供了一些额外的按排序位置访问元素的方法,例如first(), last(), lower(), higher(), subSet(), headSet(), tailSet(). TreeSet的排序分两种类型,一种是自然排序,另一种是定制排序。 自然排序(在元素中写排序规则)TreeSet 会调用compareTo方法比较元素大小,然后按升序排序。所以自然排序中的元素对象,都必须实现了Comparable接口,否则会跑出异常。对于TreeSet判断元素是否重复的标准,也是调用元素从Comparable接口继承而来额compareTo方法,如果返回0则是重复元素(两个元素I相等)。Java的常见类都已经实现了Comparable接口,下面举例说明没有实现Comparable存入TreeSet时引发异常的情况。 运行程序会抛出如下异常 将上面的Err类实现Comparable接口之后程序就能正常运行了 还有个重要问题是,因为TreeSet会调用元素的compareTo方法,这就要求所有元素的类型都相同,否则也会发生异常。也就是说,TreeSet只允许存入同一类的元素。例如下面这个例子就会抛出类型转换异常 运行结果 定制排序(在集合中写排序规则)TreeSet还有一种排序就是定制排序,定制排序时候,需要关联一个 Comparator对象,由Comparator提供排序逻辑。下面就是一个使用Lambda表达式代替Comparator对象来提供定制排序的例子。 下面是一个定制排序的列子 当然将Comparator直接写入TreeSet初始化中也可以。如下。 TreeSet是依靠TreeMap来实现的。 Comparable和Comparator EnumSet特征EnumSet顾名思义就是专为枚举类型设计的集合,因此集合元素必须是枚举类型,否则会抛出异常。 EnumSet集合也是有序的,其顺序就是Enum类内元素定义的顺序。EnumSet存取的速度非常快,批量操作的速度也很快。EnumSet主要提供以下方法,allOf, complementOf, copyOf, noneOf, of, range等。注意到EnumSet并没有提供任何构造函数,要创建一个EnumSet集合对象,只需要调用allOf等方法,下面是一个EnumSet的例子。 执行结果
各种Set集合性能分析
Map 集合框架的第二类接口树。 实现类: HashMap、TreeMap、LinkedHashMap、Hashtable等
Map常用方法: 集合遍历 1、增强for循环 for(Obj o:c){syso(o)} 代码实例 总结与面试 1.ArrayList: 元素单个,效率高,多用于查询 2.Vector: 元素单个,线程安全,多用于查询 3.LinkedList:元素单个,多用于插入和删除 4.HashMap: 元素成对,元素可为空 5.HashTable: 元素成对,线程安全,元素不可为空 HashMap和Hashtable的区别: HashMap和Hashtable都是java的集合类,都可以用来存放java对象,这是他们的相同点 以下是他们的区别: 1.历史原因: Hashtable是基于陈旧的Dictionary类的,HashMap是java 1.2引进的Map接口的一个现实。 2.同步性: Hashtable是同步的,这个类中的一些方法保证了Hashtable中的对象是线程安全的,而HashMap则是异步的,因此HashMap中的对象并不是线程安全的,因为同步的要求会影响执行的效率,所以如果你不需要线程安全的结合那么使用HashMap是一个很好的选择,这样可以避免由于同步带来的不必要的性能开销,从而提高效率,我们一般所编写的程序都是异步的,但如果是服务器端的代码除外。 3.值: HashMap可以让你将空值作为一个表的条目的key或value Hashtable是不能放入空值(null)的 ArrayList和Vector的区别: ArrayList与Vector都是java的集合类,都是用来存放java对象,这是他们的相同点, 区别: 1.同步性: Vector是同步的,这个类的一些方法保证了Vector中的对象的线程安全的,而ArrayList则是异步的,因此ArrayList中的对象并不 是线程安全的,因为同步要求会影响执行的效率,所以你不需要线程安全的集合那么使用ArrayList是一个很好的选择,这样可以避免由于同步带来的不必 要的性能开销。 2.数据增长: 从内部实现的机制来讲,ArrayList和Vector都是使用数组(Array)来控制集合中的对象,当你向两种类型中增加元素的时候,如果元素的数目超过了内部数组目前的长度他们都需要扩展内部数组的长度,Vector缺省情况下自动增长原来一倍的数组长度,ArrayList是原来的50%,所以最后你获得的这个集合所占的空间总是比你实际需要的要大,所以如果你要在集合中保存大量的数据,那么使用Vector有一些优势,因为你可以通过设置集合的初始大小来避免不必要的资源开销。 总结: 1)如果要求线程安全,使用Vector,Hashtable 2)如果不要求线程安全,使用ArrayList,LinkedList,HashMap 3)如果要求键值对,则使用HashMap,Hashtable 4)如果数据量很大,又要求线程安全考虑Vector arraylist和linkedlist联系与区别 HashMap与TreeMap联系与区别 同样做测试: |
|