单值集合Collection和键值对集合Map(一)

一、集合概念

1、类集的出现

（1）普通对象数组最大的问题在于长度是固定，不能动态扩充大小；最早的时候通过链表实现动态数组。有时候把类集称为java对数据结构的实现。类集的概念是jdk1.2(java2)开始引入的。

（2）类集中最大的几个接口操作：Collection、Map、Iterator。

所有的类集操作的接口或类都在java.util包中。

2、集合结构图

存放单值数据考虑使用Collection接口，存放键值对考虑使用Map接口
Collection接口不直接使用，一般使用List接口和Set接口；List接口存放重复数据且是有序的，Set接口存放不重复数据且是无序的；
List接口常用实现类：ArrayList和LinkedList，Set接口常用实现类：HashSet和TreeSet
ArrayList内部是数组结构，特点是增删慢、查找快，日常开发中最常用操作是查找遍历元素，所以ArrayList最常用；LinkedList内部是双向链表，增删快，存在大量首尾操作方法，可以作为堆栈和队列使用；
HashSet内部采用哈希表存储，哈希表实现方式数组+链表(JDK1.8以后采用数组+链表+红黑树)，因此具有良好的存储和查找性能。TreeSet内部使用有序二叉树存储，输出的时候按照内部排序进行输出，因此如果存储自定义类需要实现类的Comparable接口。
Map接口（Map是Mapping映射的意思）常用实现类：HashMap、TreeMap;
HashMap采用哈希表存储，是无序的；TreeMap采用二叉树存储，是有序的，按照key进行排序，不过如果key是对象则对象必须实现Comparable接口。
集合的常用操作工具类：Collections和Arrays。
进行排序除了可以实现类对象自己的Comparable接口，也可以通过创建Comparator比较器实现。

二、Collection接口

（1）Collection接口是在整个java类集中保存单值的最大操作父接口，里面每次操作都只能保存一个对象的数据。

（2）接口定义：public interface Collection<E> extends Iterable<E>

（3）常用方法：

开发中不会直接使用Collection接口。而是使用其操作的子接口List、Set。

子接口List、Set都会继承上面的方法，开发中经常使用到方法(红色部分)：

add()、iterator()、size()

1、List接口

list是Collection的子接口，里面的所有内容都是允许重复的。

public interface List<E> extends Collection<E>

此接口相较于Collection有如下扩充方法。

开发中常用的：add()、iterator()、size()、get()

List接口常用实现类：ArrayList(95%)、Vector(4%)、LinkedList(1%)

2、ArrayList实现类

ArrayList是List接口的子类，定义如下：

public class ArrayList<E> extends AbstractList<E> implements List<E>,RandomAccess,Cloneable,Serializable

特点：

（1）AbstractList 是 List的子类，且是一个抽象类，适配器设计模式。

（2）内部使用数组结构：增加删除慢，查找快。

内部实现不定长度数据存储办法采用动态扩容。

（3）构造函数：

ArrayList其实最开始创建的数组是一个空数组，长度为0。

无参构造函数，初始创建10个长度的数组，每次扩容1.5倍。

有参构造函数，如果初始需要一个非常大容量的对象，一定要使用该构造方法。

3、Vector实现类

Vector本身也是List接口的子类，定义如下：

public class Vector<E> extends AbstractList<E> implements List<E>,RandomAccess,Cloneable,Serializable

使用Vector操作结果与ArrayList没有任何区别，它是一个比ArrayList古老的实现类。

4、ArrayList类和Vector类的区别

最大的区别在于ArrayList的性能较高，采用异步处理；而Vector采用同步处理，性能较低。

两者都支持Iterator、ListIterator输出，但是Vector多了一种Enumeration输出。

5、LinkedList实现类

使用概率较低，定义：

public class LinkedList<E> extends AbstractSequentialList<E>

implements List<E>,Deque<E>,Cloneable,Serializable

此类继承了AbstractList,所以是List的子类。但此类也是Queue接口的子类，Queue接口定义了如下方法：

（1）LinkedList当做堆栈使用

压栈：push()方法

弹栈：pop()方法

（2）LinkedList当做队列使用

入队：addFirst()

出队：removeLast()

6、Set接口

Set接口也是Collection的子接口，与List接口最大的不同在于Set里面的内容不允许重复。

Set接口没有对Collection接口进行扩充，基本和Collection保持一致。

特点

List中的get(int index)方法。
add、remove方法，没有set方法，
(1)调用iterator()得到迭代器、(2)toArray()转为数组对象访问。

接口中两个常用子类：Hash、Tree

7、HashSet实现类

HashSet属于散列存放的类集（哈希表）内部实现是HashMap，里面的内容是无序存放的。

将HashSet循环输出，需要将其转换为数组，使用Set中定义的toArray方法可以实现。

使用泛型方法转换为数组：<T> T[] toArray(T[] a)

特点：

（1）HashSet中是不能有任何重复元素的。

（2）HashSet输出元素是无序(即与存储顺序无关)。

8、TreeSet实现类

（1）特点

（1）内部实现是一个有序的二叉树存储 TreeMap；

（2）遍历输出的时候，会按照内部数据顺序进行排序输出。

（2）定义

Public class TreeSet<E> extends AbstractSet<E>

implements NavigableSet<E>,Cloneable,Serializable

(3)排序的说明

Set<Person> all=new TreeSet<Person>();

all.add(new Person("张三",10));

all.add(new Person("李四",11));

（1）TreeSet存储自定义对象时候，如果会抛出异常 java.lang.ClassCastException

想要进行正常使用，需要在Person类中实现Comparable接口（因为TreeSet需要保证数据存入的有序和不重复性）

（2）即使实现了Comparable比较了年龄，如果存入同样的年龄，那么数据也不会存入，因为年龄相同，所以程序任务存入数据和以前的数据是同一个数据。

all.add(new Person("王五",11));

public class Person implements Comparable<Person>{
private String name;
private int age;
@Override
public int compareTo(Person per){
//比较 this 和传入 per
//如果返回负数  this小 / 零 一样大 / 正数  this 大
if(this.age>per.age){
return 1;
}else if(this.age<per.age){
return -1;
}else{
return 0;
}
}
......省略
}

此时，如果添加的Person对象中有年龄相同的对象也只会出现一个，如果还想要比较姓名，则需要修改compareTo方法的实现：

将 return 0修改为：return this.name.compareTo(per.name);

其他扩展：

（1）java中字符排序按照ASCII码进行排序，常见：A->65,a->97。

查看编码对应字符，通过强制转换可以查看：

System.out.println((char)65);

System.out.println((char)1);

（2）Comparator:

ArrayList<Book> list=new ArrayList<>();
list.add(new Book("三国志","A0001"));
list.add(new Book("吕氏春秋","A1001"));
list.add(new Book("国风","M0001"));
Collections.sort(list, new Comparator<Book>() {
    @Override
    public int compare(Book o1, Book o2) {
        return o1.getNumber().compareTo(o2.getNumber());
    }
});

9、关于重复元素的说明

如果要判断两个元素是否相等必须使用Object的equals()方法。

从正规的来讲，要判断两个对象是否相等有两种办法：

（1）判断两个对象编码是否一致，这个方法需要通过hashCode完成，

（2）还需要进一步验证对象的每个属性是否相等，通过equals来完成

public boolean equals(Object obj){

if(this==obj){

return true;

}

if(! obj instanceOf Person){

return false;

}

Person per=(Person)obj;

if(per.name.equals(this.name)&&per.age==this.age){

return true;

}else{

return false;

}

}

public int hashCode(){

return this.name.hashCode() * this.age;

}

小结：

（1）关于treeSet的排序实现，如果是集合中的对象是自定义的或者说其他系统定义的类没有实现Comparable接口，则不能实现TreeSet的排序，会报类型转换（转向Comparable接口）错误。

换句话说添加到TreeSet集合中的对象的类型必须实现Comparable接口。

（2）不过TreeSet的集合因为借用了Comparable接口，同时可以去除重复值，而HashSet虽然是Set接口子类，但是对于没有复写Object中hashCode和equals方法的对象，加入HashSet中也是不能去除重复值的。

三、集合输出Iterator接口

集合的输出本身也是有多种形式的：

Iterator 迭代输出（90%）

ListIterator （5%）

foreach （4%）

Enumeration（1%）

1、Iterator

基本原理：不断判断是否有下个元素，有的话，则直接输出。

定义：public interface Iterator<E>

想要使用此接口必须使用Collection接口，在Collection中规定了一个iterator()方法可以用于为Iterator接口实例化操作。

此接口中规定三个方法：

（1）boolean hasNext()

是否有一个元素

（2）E next()

指针向下移动，并且取出指向的内容

（3）void remove()

删除当前内容

使用注意：必须先移动，即先调用next()方法，然后才能remove()，否则没有指向直接remove会报错。

通过Collection接口为其实例化之后，一定要记住，Iterator中的操作指针在第一条元素上，当调用next()时，获取当前指针指向的值并向下移动，使用hashNext()可以检查序列中是否还有元素。

示例：

Collection<String> all=new ArrayList<String>();

all.add("A");

all.add("B");

all.add("C");

all.add("D");

all.add("E");

Iterator<String> iter=all.iterator();

while(iter.hashNext()){

String str=iter.next();

}

Iterator只能向后单向输出，如果想要进行双向输出必须使用其子类：ListIterator

2、双向输出ListIterator接口

ListIterator是可以进行双向输出的迭代接口，定义：

public interface ListIterator<E> extends Iterator<E>

此接口中定义了如下操作方法：

如果想要使用ListIterator，必须使用List对其进行实例化。

如果想要进行由后向前的输出，先要进行由前向后的输出。

此接口使用较少

注意：调用previous()前提，必须先向下走，才能往上走。因为初始的时候，指针没有指向元素，上面已经没有元素了。

3、介绍废弃的接口Enumeration

public interface Enumeration<E>

Vector<String> v = new Vector<String>();

v.add("A");

v.add("B");

v.add("C");

Enumeration<String> enu = v.elements();

while (enu.hasMoreElements()) {

System.out.println(enu.nextElement());

}

4、foreach输出集合（增强for）

格式：for(数据类型变量名：集合或数组){}

Collection<String> all= new ArrayList<String>();

all.add("A");

all.add("B");

all.add("C");

all.add("D");

all.add("E");

for (String str : all){

System.out.println(str) ;

}

四、Map集合

1、Map接口

Map：是Mapping映射的意思，不是地图

特点

（1）map，存储键值对key->value；

（2）map的key键不可以重复。

collection中每次操作的都是一个对象，如果要操作一对对象就必须使用Map,Map中所有的对象都按照key->value形式保存，也称二元偶对象。

定义：public interface Map<K,V>

此接口与Collection没有什么关系，是第二大类的集合操作接口。

常见方法如下：

Map本身是一个接口，所以一般会用到几个子类：HashMap、TreeMap、HashTable

2、Map接口与Set接口关系

大多数Set集合的内部都使用了Map集合进行存储，因为Map的特性key不能重复，而Set的特性数据不能重复，所以Set内部采用Map存储，存储的时候第一个键是不同且不重复的，第二个值是相同的new Object()。

HashSet、TreeSet、LinkedHashSet (单值存储)

HashMap、TreeMap、LinkedHashMap (键值对存储)

3、HashMap实现类

HashMap是Map的子类，定义：

public class HashMap<K,V> extends AbstractMap<K,V>

implements Map<K,V>,Cloneable,Serializable

此类继承了AbstractMap,同时可被克隆和序列化

HashMap本身时无序存放的。

位运算：<<

1 << 4 =16 (1左移4位等于16)

二进制数：0001 变为了 10000

左移、右移即位移运算速度非常快。

位运算：&

相当于取余运算。

内部源码实现原理：

当一个对象作为HashMap的键进行存储时，不要改变对象中的属性值，会出错：找不到哈希值。

4、哈希算法的存储实现原理

（1）存储方式:对象数组+链表

（2）哈希表扩容

桶的初始数量是：16，散列因子是：0.75

当桶的使用量超过0.75时，会进行2倍的扩容。

哈希表扩容之后存储数据位置可能就变了，一开始的下标为取余length，扩容后的下标为取余length*2，下标结果可能发生变化。

（3）哈希表的重新散列

HashMap的初始大小和散列因子，决定了其性能：

散列：重建哈希表结构

初始大小：合理的初始大小很重要。

散列因子：越大，空间利用率越高，查询效率越低；

越小，空间利用率越低，查询效率越高；

5、Hashtable类和HashMap类的区别

jdk1.0推出的，与HashMap操作类似。

Hashtable不能向集合中插入null值。

Hashtable与HashMap的区别：

HashMap：异步处理，性能较高；Hashtable：同步处理，性能较低；

而且Hashtable不允许设置null,会出现空指向异常；HashMap允许设置为null。

（1） HashMap 线程不安全（效率高），并行操作

（2）Hashtable 线程安全（效率低），排队，等待

（3）ConcurrentHashMap

采用分段锁机制，保证线程安全，效率又比较高。

6、TreeMap类

TreeMap操作时，按照key进行排序。key中的类可以是任意对象，但是要求对象所在的类必须实现Comparable接口。

TreeMap，有序存储，采用二叉树存储。

7、Map集合的输出讲解

Map接口本身不能直接使用Iterator输出的。Map接口存放的每一个内容都是一对值，而使用Iterator接口输出的时候，每一次都是取出一个完整的对象。如果此时非要使用Iterator输出，可以如下操作：

（1）使用Map中的entrySet()方法将Map接口的全部内容变成Set集合。

（2）可以使用Set接口中的iterator()方法为Iterator接口进行实例化。

（3）之后使用Iterator接口进行迭代输出，每一次都可以输出一个Map.Entry实例

（4）通过Map.Entry进行key和value分离。

Map.Entry本身是一个接口，定义在Map内部，是Map的内部接口。

此内部接口使用static定义，所以此接口成为外部接口。

实际上每一个存放在Map中的key和value值都是将其转变成为了Map.Entry并且将Map.Entry保存在Map集合中。

在Map.Entry中常用的方法：

（1）K getKey()

得到Key

（2）V getValue()

得到value

示例：使用Iterator输出Map接口

Map<String,String> map=HashMap<String,String>();

map.add("ZS","张三")；

map.add("LS","李四")；

map.add("WW","王五")；

map.add("ZL","赵六")；

map.add("SQ","孙七")；

Set<Map.Entry<String,String>> set=map.entrySet();

Iterator<Map.Entry<String,String>> iter=set.iterator();

while(iter.hashNext()){

Map.Entry<String,String> me=iter.next();

System.out.println(me.getKey()+"-->"+me.getValue());

}

五、常见集合工具类Collections

Collections是集合的操作类,与Collection没有任何关系，是一个单独存在的类，定义：

public class Collections extends Object

1、分析hashCode、equals和内存泄漏

（1）equals()：

比较两个对象地址值是否相等。

equals()方法在Object中的定义：

public boolean equals(Object obj){

return (this==obj);

}

但是：String、Math、Double、Interger这些封装类在使用equals()时已经覆盖了Object类的equals()方法，不再是地址的比较而是内容的比较。

（2）hashCode()：

方法在Object中定义如下：

public native int hashCode();

说明是一个本地方法，它的实现是根据本地机器相关的。当然也可以在自己的类中复写hashCode(),例如：String、Interger、Double、

（3）java.lang.Object中对hashCode的约定：

1、在一个应用程序执行期间，如果一个对象的equals方法做比较的信息没有被修改的话，则对该对象调用多次hashCode方法，它始终如一的返回同一个整数。

2、如果两个对象根据equals(Object o)方法是相等的，则调用两个对象中的任意一个对象的hashCode方法必须产生相同的整数对象结果。

3、如果两个对象根据equals(Object o)方法是不相等的，则调用两个对象中的任意一个对象的hashCode方法不要求产生不同的整数结果，但如果能不同，则有可能提高散列表的性能。

（4）在java集合中，判断两个对象是否相等：

1、判断两个对象的hashCode是否相等：

如果不相等，认为两个对象不相等，完毕；

如果相等，进入2

（这一点是为了提高存储效率的要求，理论上可以没有，但如果没有，实际使用效率会大大降低，所以要求必须）

2、判断两个对象用equals运算是否相等

如果不相等，认为两个对象也不相等

如果相等，认为两个对象相等

（5）内存溢出：

当一个对象被存进HashSet集合中，就不能修改这个对象中那些参与计算hash值的那些字段了，否则对象被修改的hash值与最初存进HashSet中的hash值就不同。

在这种情况下，即使在contains方法中使用该对象的当前引用作为参数去HashSet中检索对象，也将返回找不到对象结果，这也会导致无法从HashSet中删除当前对象，从而造成内存溢出。

六、总结

1、类集就是一个动态的对象数组，可以向集合中加入任意多的内容。

2、List接口中是允许有重复元素的，Set接口中不允许有重复元素。

3、所有重复的元素依靠hashCode和equals进行区分。

4、List接口常用子类：ArrayList、Vector

5、Set接口常用子类：HashSet、TreeSet

6、TreeSet可以排序，一个类的对象依靠Comparable接口排序。

7、Map接口中允许存放一对内容：key->value

8、Map接口的子类：HashMap、TreeMap、Hashtable

9、Map使用Iterator输出的详细步骤