黑马程序员--javaSE--java集合容器总结

java的集合类的知识点多而杂，如果单从某一部分开始学习，是很吃力的，而且学的不牢固，很容易忘记。
不过java的集合类从整的来说是一个框架，是一个体系，我们学习的时候只要从上到下，一层一层的去剖析，
再结合java面向对象中继承，多态，封装的思想，我想会容易搞清楚java集合框架的体系和应用的。

一、在学习java集合容器之前，我们还是要先了解一些基本知识
1、数组与java容器类的区别：
数组：是Java提供的，能随机存储和访问reference（对象的引用）序列的诸多方法中的，最高效的一种。数组是一个简单的线性序列，
所有它可以快速的访问其中的元素。但是速度是有代价的；当你创建了一个数组之后，它的容量就固定了，而且在其生命周期里不能改变。
数组可以存储对象元素，也可以存储基本数据类型元素。数组的长度是固定的。

集合：java是面向对象的语言，我们经常的操作就是操作对象。 假如我们要操作多个对象，可以使用我们前面讲过的对象数组。
但是，数组定义的时候，要明确元素个数或者明确元素值。而很多时候，这些我们都不明确，所以，java就提供了集合来存储对象元素。
集合只能存储对象元素(它存储的基本数据类型，其实是由一个装箱的过程)。集合的长度是可以变化的。

2、集合类型主要有3种：set(集）、list(列表）和map(映射)。
(1)集
集（set）是最简单的一种集合，它的对象不按特定方式排序，只是简单的把对象加入集合中，就像往口袋里放东西。
对集中成员的访问和操作是通过集中对象的引用进行的，所以集中不能有重复对象。
集也有多种变体，可以实现排序等功能，如TreeSet，它把对象添加到集中的操作将变为按照某种比较规则将其插入到有序的对象序列中。
它实现的是SortedSet接口，也就是加入了对象比较的方法。通过对集中的对象迭代，我们可以得到一个升序的对象集合。

(2)列表
列表的主要特征是其对象以线性方式存储，没有特定顺序，只有一个开头和一个结尾，当然，它与根本没有顺序的集是不同的。
列表在数据结构中分别表现为：数组和向量、链表、堆栈、队列。
关于实现列表的集合类，是我们日常工作中经常用到的，将在后边的笔记详细介绍。

(3)映射
映射与集或列表有明显区别，映射中每个项都是成对的。映射中存储的每个对象都有一个相关的关键字（Key）对象，
关键字决定了对象在映射中的存储位置，检索对象时必须提供相应的关键字，就像在字典中查单词一样。关键字应该是唯一的。
关键字本身并不能决定对象的存储位置，它需要对过一种散列(hashing)技术来处理，产生一个被称作散列码(hash code)的整数值，
散列码通常用作一个偏置量，该偏置量是相对于分配给映射的内存区域起始位置的，由此确定关键字/对象对的存储位置。
理想情况下，散列处理应该产生给定范围内均匀分布的值，而且每个关键字应得到不同的散列码。
《在后面的内容中会详细介绍这三种类型在java集合类中的具体体现，所以读者可以在阅读后面的内容时可回顾这里的内容》

3、常用的数据结构：
数据结构是按某种方式组织数据的格式，java中的集合类在底层的实现都是通过某个数据结构的。
常见的数据结构有：数组（上面已经介绍过），栈，队列，链表。

栈：有元素A,B,C想用栈进行存储，存入顺序是A--B--C,取出顺序是C--B--A,其结构特点是：先进后出
队列：有元素A,B,C想用队列进行存储，存入顺序是A--B--C,取出顺序是A--B--C,其结构特点是：先进先出

链表：链表数据结构是由一个个存储单元上非连续的节点组成。每个节点又由数据域和指针域组成，指针域存储的是，
该数据单元指向的下一个数据单元额引用地址。
哈希表：这种结构的数据结构是根据数据的哈希值存储的。

二、下面就是根据集合类的框架体系，从上往下介绍集合类以及关于集合类常用的方法，因为没有什么特别的综合运用，
下面的代码实现，只是单纯的举个案列，演示集合类或者是方法的功能。

Collection接口，是最基本的集合接口，声明了适用于java集合（只包括Set和List）的通用方法。Set和List都继承了Collection，Map咩有。
集合顶层接口Collection中的方法：
A:存储元素
boolean add(Object o)   --向集合中加入一个对象的引用
boolean addAll(Collection c) --向集合中添加整个集合所包含的的对象的引用
B:删除元素
Object remove(Object obj) --从集合中删除一个对象的引用，并返回这个对象的引用
boolean removeAll(Collection c) --移除此 collection 中那些也包含在指定 collection 中的所有元素（
void clear() --移除此 collection 中的所有元素
C:判断
 boolean isEmpty() --如果此 collection 不包含元素，则返回 true 
 boolean contains(Object o) -- 如果此 collection 包含指定的元素，则返回 true。 
boolean containsAll(Collection<?> c) --如果此 collection 包含指定 collection 中的所有元素，则返回 true 
D:长度
 int size()  --返回此 collection 中的元素数。 
E:迭代器
Iterator<E> iterator() --返回在此 collection 的元素上进行迭代的迭代器。  用于循环遍历取出集合中的元素
（返回的是Iterator接口的子类对象）
G:转成数组
Object[] toArray() -- 返回包含此 collection 中所有元素的数组。 

Iterator接口
方法：
hasNext(): 判断集合中元素是否遍历完毕，如果没有，就返回true
next()       :返回下一个元素
remove():从集合中删除上一个有next()方法返回的元素。
Iterator的理解：其实，集合的对象通过iterator方法，返回的是迭代器的子类对象。每种集合获取元素的方式是不同的，
所以，他们会自己去实现如果获取元素。但是，他们都有共性内容：就是先判断是否有数据，然后获取数据。所以，就抽取出了一个接口Iterator。
在使用这个接口时有几个注意点:
迭代器在Collcection接口中是通用的，它替代了Vector类中的Enumeration(枚举)。
迭代器的next方法是自动向下取元素，要避免出现NoSuchElementException。
迭代器的next方法返回值类型是Object，所以要记得类型转换。

List接口
List继承了Collection接口是有序的Collection，使用此接口使用此接口能够精确的控制每个元素插入的位置。
用户能够使用索引（元素在List中的位置，类似于数组下标）来访问List中的元素，这类似于Java的数组。和下面要提到的Set不同，List允许有相同的元素。
特有的方法：
A:add(int index,Object obj)  -- 在指定位置加入元素
B:remove(int index) --移除指定位置的元素
C:set(int index,Object obj) --修改指定位置的元素
D:get(int index) --获取指定位置的元素
E:indexOf(Object obj) --获取指定元素的位置
F:subList(int start,int end) --从一个大的List中截取一个小的List
G:listIterator() --返回一个List接口特有的迭代器：
2:List的子实现类
List
|--ArrayList
底层数据结构是数组，而且是线程不安全的。
增删慢，查询快
|--Vector
底层数据结构是数组，而且是线程安全的。
增删慢，查询快。但是，又由于线程安全，所以，它是都慢。一般不选择。
|--LinkedList
底层数据结构是链表，而且是线程不安全的。
增删快，查询慢


一般情况下，使用哪种List接口下的实现类呢？
如果要求增删快，考虑使用LinkedList
如果要求查询快，考虑使用ArrayList
如果要求线程安全，考虑使用Vector。
如果考虑不到任何问题，就使用ArrayList

代码实现：主要是向集合中添加元素和集合的遍历

package com.ithei.com;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
/*
* 演示list接口相关的方法应用，以及集合的遍历
*/
public class ListTest {
public static void main(String[] args) {
//定义一个List集合
List list = new ArrayList();
//向里面添加对象的引用
list.add(new Person("张三", 12));
list.add(new Person("李四", 13));
list.add(new Person("王五", 14));
//第一种遍历方法，Iterator迭代器的方式
Iterator it = list.iterator();
while(it.hasNext()){
System.out.println(it.next());
}
System.out.println("***********************");
//第二种遍历方法,增强for循环的方式
for(Object obj:list){
Person p= (Person) obj;
System.out.println(p);
}
System.out.println("***********************");
//第三种遍历方式
for(int i=0;i<list.size();i++){
Person p = (Person) list.get(i);
System.out.println(p);
}
}
}
//自定义对象的类
class Person{
private String name;
private int age;
public Person(String name, int age) {
super();
this.name = name;
this.age = age;
}
//重写toString（）方法
@Override
public String toString() {
return name+":"+age;
}
}

Set接口：
继承了Collection接口，具有和Collection完全一样的接口，没有任何额外的功能。它是一种不包含重复的元素的Collection，
即任意的两个元素e1和e2都有e1.equals(e2)=false，Set最多有一个null元素。
很明显，Set的构造函数有一个约束条件，传入的Collection参数不能包含重复的元素。
Set接口的实现类
Set 元素无序(存储顺序和取出顺序不一致)，不可重复。
|--HashSet
底层数据结构是哈希表。线程不安全。
如果保证元素的唯一性呢？
A:首先根据hashCode值判断。
B:如果hashCode值不同，那么，这就是不同的元素。直接存储。
 如果hashCode值相同，那么，会继续根据equals方法进行判断，
 根据自己的需求来决定元素是否相同。如果相同，就不存储。否则，存储。


一般，用HashSet的时候，要重写hashCode和equals方法。
|--LinkedHashSet
底层数据结构是链表和哈希表。
链表用于保证元素有序，哈希表用于保证元素唯一。
|--TreeSet
底层数据结构是二叉树，线程不安全。
如何保证元素的排序呢？两种方式
A:让元素本身具备比较性
实现Compareable接口中的compareTo方法。
B:让集合具备比较性
实现Comparator接口中的compare方法。

以后到底用哪个集合呢？
A:如果要元素唯一，就用Set。否则，用List。
B:如果元素唯一并且要排序用TreeSet，否则，用HashSet。
C:如果元素可重复，且考虑线程问题，用Vector。
  否则，用ArrayList或者LinkedList。
  如果要求，增删快，那么，考虑LinkedList。
  如果要求，查询快，那么，考虑ArrayList。
D:当你什么都不清楚的时候，就使用ArrayList。

在介绍具体的代码实现时，先说一下java中的泛型：（因为本篇博客的着重点是java的集合容器，所以对于java中的泛型只是做简单的介绍，
读者如果有兴趣，可自行查找相关资料，嘿嘿-。。-）
首先先说明一下java集合容器的一个缺点：Java的容器有个缺点，就是往容器里面放对象的时候，会把对象的类型信息给弄丢了。
这是因为开发容器类的程序员不会知道你要用它来保存什么类型的对象，而让容器仅只保存特定类型的对象又会影响它的通用性。
所以容器被做成只有持有Object，也就是所有对象的根类的reference，这样它就能持有任何类型的对象了。
在以上的collection集合列举的方法中，我们也不难发现对于从集合中取出来的元素，其类型都是Object的，所以取出来之后我们还要强转。
但是由于java泛型的出现，却大大避免了这个问题。
泛型的概念：
泛型是提供给javac编译器使用的，可以限定集合中的输入类型，让编译器挡住源程序中的非法输入，编译器编译带类型说明的集合时会去除掉“类型”信息，
使程序运行效率不受影响，对于参数化的泛型类型，getClass()方法的返回值和原始类型完全一样。由于编译生成的字节码会去掉泛型的类型信息，
只要能跳过编译器，就可以往某个泛型集合中加入其它类型的数据，例如，用反射得到集合，再调用其add方法即可。
泛型的特点：
提高了程序的安全性
将运行期遇到的问题转移到了编译期
省去了类型强转的麻烦
泛型类的出现优化了程序设计

代码实现：此案例是以TreeSet集合说明的，包含了集合中泛型的简单应用，还有TreeSet实现集合元素排序的两种方式

package com.ithei.collection;
public class Student implements Comparable<Student>{
private String name;
private int age;
public Student(String name, int age) {
super();
this.name = name;
this.age = age;
}
//根据自己需要实现compareTo
@Override
public int compareTo(Student stu) {
//返回值：正数表示大，负数表示小，0表示相等
/*
1:名字的长度
2:年龄的排序
3:姓名的字符串值是否相同
*/
int num = this.getName().length()-stu.getName().length();
int num2 = this.getAge()-stu.getAge();
int num3 = this.getName().compareTo(stu.getName());
return (num==0)?(num2==0?num3:num2):(num);
}
//重写toString方法
@Override
public String toString() {
return name+"--"+age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
}
package com.ithei.collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;
public class TreeSetDemo {
public static void main(String[] args) {
//方法一：TreeSet集合元素的排序，元素自己实现接口Comparable
//利用泛型定义TreeSet集合，泛型参数是Student类，说明此集合只能存储Student类型的变量的引用
Set<Student> stus = new TreeSet<Student>();
//添加元素(添加元素时会调用Student类实现的compareTo()的方法，进行比较排序，从而保证
//集合元素的唯一性)
stus.add(new Student("张三", 33));
stus.add(new Student("李四", 24));
stus.add(new Student("王五", 12));
stus.add(new Student("张三", 13));
stus.add(new Student("李四", 24)); //这个元素与上面的相同不会被添加进集合
//遍历集合
Iterator<Student> it = stus.iterator();
while(it.hasNext()){
//不用强转，取出来的元素的类型就是Student类，直接打印
System.out.println(it.next());
}
System.out.println("***************************");
//方法二，TreeSet集合自己实现元素的比较器（通过构造方法）
Set<Student> stus2 = new TreeSet<Student>(new Comparator<Student>() {
@Override
public int compare(Student st1,Student st2) {
/*
1:名字的长度
2:年龄的排序
3:姓名的字符串值是否相同
*/
int num = st1.getName().length()-st2.getName().length();
int num2 = st1.getAge()-st2.getAge();
int num3 = st1.getName().compareTo(st2.getName());
return (num==0)?(num2==0?num3:num2):(num);
}
});
//添加元素
stus2.add(new Student("张三", 33));
stus2.add(new Student("李四", 24));
stus2.add(new Student("王五", 12));
stus2.add(new Student("张三", 13));
stus2.add(new Student("李四", 24)); //这个元素与上面的相同不会被添加进集合
//遍历集合
Iterator<Student> it2 = stus.iterator();
while(it2.hasNext()){
//不用强转，取出来的元素的类型就是Student类，直接打印
System.out.println(it2.next());
}
}
}

Map接口：Map没有继承Collection接口，Map提供key到value的映射。一个Map中不能包含相同的key，每个key只能映射一个 value。
Map接口提供3种集合的视图，Map的内容可以被当作一组key集合，一组value集合，或者一组key-value映射。
数据必须以键值成对出现。
常用方法：
A:存储元素
 V put(K key, V value) --将指定的值与此映射中的指定键关联
B:删除元素
 V remove(Object key) -- 如果存在一个键的映射关系，则将其从此映射中移除 
C:判断
boolean containsKey(Object key) --如果此映射包含指定键的映射关系，则返回 true。 
boolean containsValue(Object value) -- 如果此映射将一个或多个键映射到指定值，则返回 true 
D:长度
 int size() 返回此映射中的键-值映射关系数 
E:获取元素
 V get(Object key) -- 返回指定键所映射的值；如果此映射不包含该键的映射关系，则返回 null 
Collection<V> values() --返回此映射中包含的值的 Collection 视图。 
Set<K> keySet() -- 返回此映射中包含的键的 Set 视图。 
Set<Map.Entry<K,V>> entrySet() -- 返回此映射中包含的映射关系的 Set 视图。 

Map接口的实现类
Map
|--Hashtable
底层是哈希表结构
线程安全的，并且键和值不能为null。
|--HashMap
底层是哈希表结构
线程不安全的，键和值可以为null。
|--LinkedHashMap
底层是链表和哈希表
线程不安全
|--TreeMap
底层是二叉树
线程不安全的

其中用的比较多的是HashMap。

代码实现，主要是演示的是向map集合中添加元素和map集合的遍历

package com.ithei.collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
public class HashMapTest {
public static void main(String[] args) {
//用泛型的方式定义HashMap对象
Map<Integer,Person> map = new HashMap<Integer, Person>();
//添加元素
map.put(001, new Person("张三", 13));
map.put(002, new Person("李四", 14));
map.put(003, new Person("王五", 15));
//第一种方法遍历集合
//map集合的遍历Map集合的内部类Map.Entry<K,V>
Set<Entry<Integer, Person>> entrySet = map.entrySet();
for(Map.Entry<Integer, Person> entry:entrySet){
System.out.println(entry.getKey()+"---"+entry.getValue());
}
//第二种方法遍历集合
//获取键的set类型的集合
Set<Integer> keySet = map.keySet();
Iterator<Integer> it = keySet.iterator();
while(it.hasNext()){
//获得键
Integer key = it.next();
//很据键获得对应的值
Person person = map.get(key);
System.out.println(key+"---"+person);
}
}
}
//自定义对象的类
class Person{
private String name;
private int age;
public Person(String name, int age) {
super();
this.name = name;
this.age = age;
}
//重写toString（）方法
@Override
public String toString() {
return name+":"+age;
}
}

总结Java标准类库的容器类： 
1。数组把对象和数字形式的下标联系起来。它持有的是类型确定的对象，这样提取对象的时候就不用再作类型传递了。它可以是多维的，也可以持有primitive。但是创建之后它的容量不能改了。
2。Collection持有单个元素，而Map持有相关联的pair。
3。和数组一样，List也把数字下标同对象联系起来，你可以把数组和List想成有序的容器。List会随元素的增加自动调整容量。但是List只能持有Object reference，所以不能存放primitive，而且把Object提取出来之后，还要做类型传递。
4。如果要做很多随机访问，那么请用ArrayList，但是如果要再List的中间做很多插入和删除的话，就应该用LinkedList了。
5。LinkedList能提供队列，双向队列和栈的功能。
6。Map提供的不是对象与数组的关联，而是对象和对象的关联。
HashMap看重的是访问速度，而TreeMap各国那看重键的顺序，因而它不如HashMap那么快。而LinkedHashMap则保持对象插入的顺序，但是也可以用LRU算法为它重新排序。

ps：本来还想再写一个案例的，但考虑到本篇博客已经是又臭又长了，所以就不写了，但在这里给出案例的要求，读者如果有兴趣可以自己尝试写一下：
案例要求："cbxzbvavdvgd"获取字符串中，每一个字母出现的次数。
          要求结果是："a(1)b(2)c(1)d(2)g(1)v(3)x(1)z(1)"