集合框架总结
1.所有集合类都位于java.util包下。Java的集合类主要由两个接口派生而出:Collection和Map,Collection和Map是Java集合框架的根接口,这两个接口又包含了一些子接口或实现类。
Collection
1、Collection是一个接口,是高度抽象出来的集合,它包含了集合的基本操作和属性。包含了List,Set,Queue三大分支。
(1)List是一个有序的队列,每一个元素都有它的索引。第一个元素的索引值是0。可含重复元素。
(2)Set是一个不允许有重复元素的无序集合。
(3)Queue 队列,先进先出。
List
特点
- 和数组类似,可以动态增长(动态数组);
- 有序,元素可重复;
- 查找元素效率高;插入、删除元素效率低(会引起其他元素位置改变)。
查看方式:
- get(下标)
- for循环(下标)
- foreach遍历(>=JDK 1.5)
- 迭代器Iterator
主要实现类:
(1)ArrayList
- 动态数组,线程非同步。
- 可随机访问,查询快,增删慢。
- 默认长度为10,增长方式:新容量 = 旧容量 * 3 / 2 + 1(查看ArrayList类构造方法)。
- 允许元素为null。
.
(2)LinkedList
- 双向链表结构,可当做堆栈、队列或双向队列进行操作。
- 线程非同步。
- 不可随机访问,查询慢,增加、删除快。
- 没有默认分配容量。
LinkedList新增方法:
addFirst(e) |
添加到第一位置 |
addLast(e) |
添加到最后一位置 |
getFirst() |
获得第一位置元素 |
getLast() |
获得最后一位置元素 |
removeFirst() |
移除第一位置元素 |
removeFirst() |
移除最后一位置元素 |
实现同步
List list = Collections.synchronizedList(new LinkedList(...));
(3)Vector
- 线程同步。
- 安全,但效率低(一般不赞成使用);
- 默认长度为10,增长方式:n*2(比较浪费资源)。
(4)Stack
Stack继承自Vector,实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。
Stack常用方法:
Empty() |
判断栈是否为空 |
Push(x) |
将元素x压栈 |
Pop() |
将栈顶元素弹栈(删除),返回为void |
Top() |
获得栈顶元素 |
Size() |
返回栈大小,类型size_type |
Set
1.不包括重复元素,它维持它自己的内部排序,所以随机访问没有任何意义。与List一样,允许null的存在但是仅有1个。
2.查找元素效率低,插入删除元素效率高(不会引起元素位置改变)。
遍历: foreach 迭代器
对应实现类:
(1)HashSet
元素不能重复。无序(这里所说的无序是指:元素插入的顺序与输出的顺序不一 致)
允许使用null 元素。线程非同步,速度快。
HashSet的实现方式大致如下,通过一个HashMap存储元素,元素是存放在HashMap的Key中,而Value统一使用一个Object对象。
(2)LinkedHashSet
LinkedHashSet继承自HashSet,基于LinkedHashMap来实现的,有序,非同步。LinkedHashSet集合同样是根据元素的hashCode值来决定元素的存储位置,但是它同时使用链表维护元素的次序。这样使得元素看起来像是以插入顺序保存的,也就是说,当遍历该集合时候,LinkedHashSet将会以元素的添加顺序访问集合的元素。
(3)TreeSet
TreeSet是一个有序集合,基于TreeMap实现的,非线程安全。TreeSet可以确保集合元素处于排序状态。TreeSet支持两种排序方式,自然排序和定制排序,默认升序。
注意:TreeSet集合不是通过hashcode和equals函数来比较元素的.它是通过compare或者comparaeTo函数来判断元素是否相等.compare函数通过判断两个对象的id,相同的id判断为重复元素,不会被加入到集合中。
Map
- 无序。
- 以Key/Value(键/值对)的形式添加元素,且键不能重复,值可以重复。
- 没有继承Collection ,并不是一个真正意义上的集合,但是这个接口提供了三种“集合视角”,使得可以像操作集合一样操作。
1.HashMap
根据键的HashCode值存储数据,查询快,最多允许一个键为NULL,多个值为NULL。线程不同步
2.LinkedHashMap
LinkedHashMap是HashMap的一个子类,它保留插入的顺序,如果需要输出的顺序和输入时的相同,那么就选用LinkedHashMap。允许使用null值和null键。此类不保证映射的顺序,特别是它不保证该顺序恒久不变。线程不是同步的。 由于LinkedHashMap需要维护元素的插入顺序,因此性能略低于HashMap的性能。
3.TreeMap
TreeMap 是一个有序的key-value集合,非同步,基于红黑树(Red-Black tree)实现,每一个key-value节点作为红黑树的一个节点。TreeMap存储时会进行排序的,会根据key来对key-value键值对进行排序,其中排序方式也是分为两种,一种是自然排序,一种是定制排序,具体取决于使用的构造方法。
自然排序:TreeMap中所有的key必须实现Comparable接口,并且所有的key都应该是同一个类的对象,否则会报ClassCastException异常。
定制排序:定义TreeMap时,创建一个comparator对象,该对象对所有的treeMap中所有的key值进行排序,采用定制排序的时候不需要TreeMap中所有的key必须实现Comparable接口。
TreeMap判断两个元素相等的标准:两个key通过compareTo()方法返回0,则认为这两个key相等。
Iterator接口
Iterator接口是Java集合框架的成员,主要用于遍历集合的元素(又叫迭代器)。实现Iterator接口的类有增强for循环。
Iterator接口定义了三个方法:
boolean hasNext() |
如果被迭代的集合元素还有没遍历,则返回true。 |
Object next() |
返回集合里的下一个元素。 |
void remove() |
删除集合里上一次next方法返回的元素。 |