List接口和Set接口及其常用实现类概述

小灰灰 2021-11-19 13:20 475阅读 0赞

### 一、List接口 ###

List:有序的 collection（也称为序列）。此接口的用户可以对列表中每个元素的插入位置进行精确地控制。用户可以根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素。 List接口：有序的、允许多个null元素、具体实现常用的有ArrayList、Vector、LinkedList常用实现类有ArrayList、Vector、LinkedList

#### ArrayList定义及特点 ####

public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, Serializable

1.  实现原理，采用动态对象数组实现，默认构造方法创建了一个空数组
2.  第一次添加元素，扩展容量为10，之后的扩充算法：原来的数组大小+原数组大小的一半
3.  不适合进行删除或插入操作
4.  为了防防止数组动态扩充次数过多，建议在创建时给定初始容量
5.  线程不安全，适合在单线程使用，效率较高

#### Vector定义及特点 ####

public class Vector extends AbstractList implements List, RandomAccess, Cloneable, Serializable

1.  实现原理，采用动态数组实现，默认构造方法创建了一个大小为10的对象数组
2.  扩充的算法：当增量为0时，扩充为原来大小的两倍，当增量大于0时，扩充为原来大小+增量
3.  不适合删除或插入操作
4.  为了防防止数组动态扩充次数过多，建议在创建时给定初始容量
5.  线程安全，适合在多线程访问时使用，效率较低

#### LinkedList定义及特点 ####

public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, Serializable

1.  实现原理，采用双向链表结构实现
2.  适合插入、删除操作，性能高

在实际开发中，如何选择List接口的具体实现？需要考虑的问题有：

*  安全性问题
 *  是否频繁插入、删除（LinkedList）
 *  是否存储后遍历

### 二、Set接口 ###

一个不包含重复元素的 collection。更确切地讲，set 不包含满足 e1.equals(e2) 的元素对 e1 和 e2，并且最多包含一个 null 元素。常用的实现类有HashSet、LinkedHashSet、TreeSet

#### HashSet定义及特点 ####

public class HashSet extends AbstractSet implements Set, Cloneable, Serializable

1.  实现原理，基于哈希表（HashMap）实现
2.  不允许重复，最多可以有一个null元素
3.  不保证顺序恒久不变
4.  添加元素时把元素作为HashMap的key保存，HashMap的value使用一个固定的Object对象
5.  排除重复是通过equals方法来检查对象是否相等
6.  判断两个对象是否相同，先判断两个对象的hashCode是否相同（两个对象的hashCode相等不一定是同一个对象，但如果不同，一定不是同一个对象），若不同，则两个对象不是同一个对象；若相同，还要进行equals判断。equals方法返回true则为同一个对象，返回false则不是同一个对象。
7.  自定义类存入HashSet时，建议重写类的hashCode和equals方法

哈希表的存储结构：数组+链表，数组里的每个元素以链表的形式存储  
如何把对象存储到哈希表中？先计算对象的hashCode值再对数组的长度求余数，来决定对象要存储在数组中的哪个位置。

#### TreeSet定义及特点 ####

public class TreeSet extends AbstractSet implements NavigableSet, Cloneable, Serializable

*  基于 TreeMap 的 NavigableSet 实现。使用元素的自然顺序对元素进行排序，或者根据创建 set 时提供的 Comparator 进行排序，具体取决于使用的构造方法。
 *  有序的，基于TreeMap(二叉树数据结构)实现，对象需要比较大小，通过对象比较器来实现。对象比较器还可以用来去除重复元素，若自定义的类没有实现比较器（Comparable）接口，将无法添加到TreeSet中。

#### LinkedHashSet定义及特点 ####

public class LinkedHashSet extends HashSet implements Set, Cloneable, Serializable

具有可预知迭代顺序的 Set 接口的哈希表和链接列表实现。此实现与 HashSet 的不同之外在于，后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，即按照将元素插入到set 中的顺序（插入顺序）进行迭代。注意，插入顺序不 受在 set 中重新插入的 元素的影响。如果在 s.contains(e) 返回 true 后立即调用 s.add(e)，则元素 e 会被重新插入到 set s 中。）

如何选择Set接口的具体实现？

*  如果要排序，选TreeSet
 *  如果不用排序，也不用保证顺序，选HashSet
 *  如果不用排序，要保证顺序，选LinkedHashSet

转载于:https://www.cnblogs.com/zxfei/p/10901965.html