list、map、set等常用集合框架

1. Java集合框架概述

集合就是将若干用途相同、近似的“数据”结合成一个整体，从体系上分为三种：

(1)Collection：是顶层接口，描述普遍性操作方法

(2)List:线性表，有序集合

(3)Set:不包含重复元素得无序集合，并且最多包含一个null元素，就是一个只有key的Map集合

(4)Map:Key：Value对的集合。一个映射不能包含充分的键：每个键最多只能映射到一个值

集合框架的类图关系：

其中List：

ArrayList：数组实现线性表

Vector：数组实现线性表

LinkedList：双选循环链表实现的线性表

Set：

HashSet:基于HashMap实现的Set集合

TreeSet：基于TreeMap实现的Set集合

Map：

HashMap：散列表实现的Map

HashTable：散列表实现的Map

TreeMap：二叉排序树表实现的Map

简单说下散列表的存取原理：

先来看看Collection接口方法的清单

2. List接口以及实现类

List是Collection的子接口，实现List接口的容器中存放的对象是有顺序的，而且可以重复。List容器中存放的对象都有一个整数型的序号，记录该对象在容器中的位置，可以根据序号来访问容器中的元素，JDK提供实现List接口的类有ArrayList、LinkedList等。接口主要方法如下：

   

（1） List接口的实现类-ArrayList

java.util.ArrayList实现了List接口，用于描述长度可变的数组列表(底层采用数组实现)。ArrayList允许元素取值为null,提供了一些新增的方法来操作列表的容量的大小。

public ArrayList()(默认大小是10)

public ArrayList(intinitialCapacity)

public void ensureCapacity(intminCapacity)

public void trimToSize()

（2） List接口的实现类-Vector

java.util.Vector实现了List接口，用于描述长度可变的数组向量(底层采用数组实现)。与ArrayList的区别：Vector是线程安全的(同步),用在多线程环境中，运行效率慢。ArrayList不是线程安全的，用在单线程环境中。

Vector类的新增方法：

public Vector()(默认大小是10)

public Object elementAt(int index)

public void removeElement(int index)

public void insertElement(Object obj,int index)

public booleanremoveElement(Object obj)

public void removeAllElements()

public Object toArray()

（3）Vector类的子类Stack类

java.util.Statck继承自Vector类，对应”First In,Last out”的数据结构-栈。

Stack类的常用方法:

public Statck()

public Object push(Object obj)

public Object pop()

public Object peek()

public booleanisEmpty()

public void clear()

public int search(Object obj)   

3. Set接口以及实现类

Set接口是Collection的子接口，Set接口没有提供新增的方法，但实现Set接口的容器中元素是没有顺序的且不可以重复。Set容器可以与数学中的“集合”概念相对应。

JDK中提供的实现Set接口的类有HashSet、TreeSet等

（1）HashSet与List大部分相同

（2）Set接口的实现类-TreeSet

TreeSet描述的是Set的一个变体-可实现排序功能的集合。将对象插入到TreeSet中时，会按照某种比较规则将对象插入到一个有序序列中，以保证TreeSet集合中的对象序列保持“升序”排列

（3）Comparable接口

所有可排序的类都实现了java.lang.Comparable接口，该接口中只有一个抽象方法:

   public int compareTo(Object obj)

 注意：用户在实现compareTo()方法确定比较逻辑时，比较结果应该和equals()方法比较的结果一致。

4. Map接口以及实现类

实现Map接口的类用来存储”键-值”对。可理解为一张二维表，这个二维表只有两列，一列是Key，一列是Value。Map中存储的“键-值”对由键来标识，所以键不能重复。

Map接口的实现类有HashMap和TreeMap。

Map接口的常用方法：

Object put(Object key,Object value)

Object get(Object key)

Object remove(Object key)

boolean containsKey(Object key)

boolean containsValue(Object value)

int size()

boolean isEmpty()

void putAll(Map t)

voidclear()

（1）Map接口的实现类-HashMap

java.util.HashMap类实现了java.util.Map接口，基于哈希表实现“键”-“值”对的映射关系。HashMap不确定“K”-”value”对的先后顺序，允许使用null“K”和null”value”。

影响HashMap性能的两个因素：

  初始容量(InitialCapacity)

  加载因子(LoadFactor)   (小于1的数)

（2）Map接口的实现类-Hashtable

java.util.Hashtable实现了java.util.Map接口，也是采用哈希表的形式将”Key”映射到”Value”，用法与HashMap基本相同。HashMap与Hashtable的区别：

1. Hashtable中的“key”和“value”都不允许null，而HashMap允许。

 2. Hashtable是线程安全的，适合在多用户环境中使用，效率稍低；HashMap不是线程安全的，效率稍高，适合在单线程环境下使用

5. Iterator接口

Iterator(称作迭代器)接口主要提供了对容器中元素进行遍历的方法。所有实现了Collection接口的类都有一个iterator()方法来返回一个实现了Iterator接口的类的对象。

该接口中定义了如下抽象方法：

booleanhasNext() //判断游标右边是否还有元素

Object next() //返回游标右边的元素并将游标移动到该元素后

void remove() //删除游标左边的元素，通常在next()方法之后执行，只执行一次。

6. List常用算法-由Collections类实现

java.util.Collections类提供了一些静态方法，实现了基于List容器的常用算法。

void sort(List list)      对容器内的元素进行升序排序

void reverse(List list)对容器内的元素进行逆序排列

void shuffle(List list)  对List容器内的元素进行随机排列

void fill(List list,Objectobj) 对特定的对象来填充list

void copy(List des,Listsrc)  将src容器中的内容拷贝到des容器中

Object max(Colletion c)       Object min(Collection c)

void rotate(List list,int distance) 对列表中元素按distance进行移位操作

int binarySearch(List list,Objectobj)

采用折半查找在list中寻找obj对象，返回这个对象在容器中的位置 (注意调用此方法前必须对列表进行升序排序，否则结果不确定)

 

下期继续。。。。