List、Set、Map的了解及区别

List、Set、Map的之间关系及区别

一、List接口

List是一个继承于Collection的接口,即List是集合的一种.List是有序的队列,List中的每一个元素都有一个索引;第一个元素的索引值是0,往后的元素的索引值依次+1.和Set不同的是,List中允许有重复的元素.实现List接口的集合主要有: ArrayList、LinkedList、Vector、Stack.

ArrayList

ArrayList是一个动态数组,也是我们最常用的集合.它允许任何符合规则的元素插入甚至包括NULL.每一个ArrayList都有一个初始容量:

private static final int DEFAULT_CAPACITY = 10;

随着容量中的元素不断增加,容量的大小也会随着增加.在每个向容器中增加元素的同事都会进行容量检查,当快溢出时,就会进行扩容操作.所以如果我们明确所插入元素的多少,最好指定一个初始容量值,避免过多的进行扩容操作而浪费时间、效率.

size、isEmpty、get、set、iterator和listIterator操作都以固定时间运行.add操作以分摊的固定时间运行,也就是说,添加n个元素要T(n)时间(由于要考虑到扩容,所以这不只是添加元素会带来分摊固定时间开销那样).

ArrayList擅长于随机访问.同时ArrayList是非同步的.(同步与非同步篇请看另篇博客)

LinkedList

同样实现List接口的LinkedList与ArrayList不同, ArrayList是一个动态数组,而LinkedList是以一个双向链表. 所以它除了有ArrayList的基本操作方法外还额外提供了get,remove,insert 方法在LinkedList的首部或尾部.

由于实现的方式不同,LinkedList不能随机访问,它所有的操作都是要按照双重链表的需要执行.在列表中索引的操作将从开头或者结尾遍历列表(从靠近指定索引的一段,节约一半时间).这样做的好处就是可以通过较低的代价在List中进行插入和删除操作.

与ArrayList一样,LinkedList也是非同步的.如果多个线程同时访问一个List,则必须自己实现访问同步.一种解决方法是创建List时构造一个同步的List:

List list = Collection.synchronizedList(new LinkedList(...));

Vector

与ArrayList相似,但是Vector是同步的.所以说Vector是线程安全的动态数组.它的操作与ArrayList几乎一样.

Stack

Stack继承自Vector,实现一个后进先出的堆栈,Stack提供5个额外的方法使得Vector得以被当做堆栈使用.基本的push和pop方法,还有peek方法得到栈顶的元素,empty方法测试堆栈是否为空,search方法检测一个元素在堆栈中的位置,Stack刚创建后是空栈.

二、Set接口

Set是一个继承于Collection的接口,Set是一种不包括重复元素的Collection.它维持它自己的内部排序,所以随机访问没有任何意义.与List一样,它同样运行null的存在但是仅有一个.由于Set接口的特殊性,所有传入Set集合中的元素都必须不同.关于API方面,Set的API和Collectoin完全一样,实现Set接口的集合有: HashSet、TreeSet、LinkedHashSet、EnumSet.

HashSet

HashSet堪称查询速度最快的集合,因为其内部是以 HashCode 来实现的,集合元素可以是NULL,但只能放入一个null,它内部元素的顺序是由哈希码来决定的,所以它不保set的迭代顺序;特别是它不保证该顺序恒久不变.

TreeSet

TreeSet是二叉树实现的,基于TreeMap,生成一个总是处于排序状态的Set,内部以TreeMap来实现,不允许放入null值.它是使用元素的自然顺序对元素进行排序,或许根据创建Set时提供的 Comparator 进行排序,具体取决于使用的构造方法.

LinkedHashSet

LinkedHashSet集合同样是根据元素的hashCode值来决定元素的存储位置,但是它同时使用链表维护元素的次序.这样使得元素看起来像是以插入顺序保存的,也就是说,当遍历该集合时候,LinkedHashSet将会以元素的添加顺序访问集合的元素.LinkedHashSet在迭代访问Set中的全部元素时,性能比HashSet好,但是插入时性能稍微逊色于HashSet.

HashMap

以哈希表数据结构实现,查找对象时通过哈希函数计算其位置,它是为快速查询而设计的,其内部定义了一个hash表数组(Entry[]table),元素会通过哈希转换函数将元素的哈希地址转换成数组中存放的索引,如果有冲突,则使用散列链表的形式将所有相同哈希地址的元素串起来,可能通过查看HashMap.Entry的源码 它是一个单链表结构.

HashTable

HashTable也是以哈希表数据结构实现的,解决冲突时与HashMap也一样是采用了散列链表的形式.HashTable继承Dictionary类,实现Map接口.其中Dictionary类是任何可将键映射到相应值的类(如 HashTable)的抽象父类.每个键和每个值都是一个对象.在任何一个Dictionary对象中,每个键之多与一个值相关联.Map是"key-value键值对"接口.HashTable采用"拉链法"实现哈希表不过性能比HashMap要低.

TreeMap

有序散列表,实现SortedMap接口,底层通过红黑树实现的.

WeakHashMap

谈WeakHashMap前先看一下JAVA中的引用(强度依次递减)

1.强引用: 普遍对象声明的引用,存在便不会GC
2.软引用: 有用但并非必须,发生内存溢出前,二次回收
3.弱引用: 只能生存到下次GC之前,无论是否内存足够
4.虚引用: 唯一目的是在这个对象被GC时能收到一个系统通知

以弱键实现的基于哈希表的Map.在WeakHashMap 中,当某个键不再正常使用时,将自动移除其条目.更精确地说,对于一个给定的键,其映射的存在并不阻止垃圾回收器对该键的丢弃,这就使该键成为可终止的, 被终止,然后被回收.丢弃某个键时,其条目从映射中有效地移除,因此,该类的行为与其他的Map实现有所不同.null值和null键都被支持.该类具有与HashMap类相似的性能特征,并具有相同的效能参数初始容量和加载因子.像大多数集合类一样,该类是不同步的.

四、总结

1、List、Set都是继承自Collection接口,Map则不是

2、List特点:

元素有放入顺序,元素可重复,Set特点: 元素无放入顺序,元素不可重复,重复元素会覆盖掉,(注意: 元素虽然无放入顺序,但是元素在set中的位置是有该元素的HashCode决定的,其位置其实是固定的,加入Set的Object必须定义equals()方法,另外list支持for
循环,也就是通过下标来遍历,也可以用迭代器,但是set只能用迭代,因为它无序,无法用下标取得想要的值.)

3、Set和List对比:

Set: 检索元素效率低下,删除和插入效率高,插入和删除不会引起元素位置改变.

List: 和数组类似,List可以动态增长,查找元素效率高,插入删除元素效率低,因为会引起其他位置改变.

4、Map适合储存键值对的数据

5、线程安全集合类与非线程安全集合类:

• LinkedList、ArrayList、HashSet是非线程安全的,Vector是线程安全的.

• HashMap是非线程安全的,HashTable是线程安全的.

• StringBuilder是非线程安全的,StringBuffer是线程安全的.