JAVA 集合框架

集合的主要接口

Collection	存放单独的值的集合，很少直接用
List	是Collection的子接口，里面的值可以重复
Set	是Collection的子接口，里面的值不能重复
Map	是存放一对值的接口，通过Key--->Value的形式保存
Iterator	集合的输出接口，用于输出集合中的内容，只能从前往后
ListIterator	Iterator的子接口，可以双向输出
Enumeration	最早的输出接口
SortedSet	单值比较接口，里面内容可以排序，使用比较器排序。
SortedMap	存放一对值的接口，里面内容按Key排序，使用比较器排序。
Queue	队列接口
Map.Entry	每个Map.Entry对象都保存着一个键值对，每个Map中都保存着多个Map.Entry

Collection接口

add（E泛型）方法向集合中插入对象

addAll（Collection＜＞）将一个集合的内容加入其中

clear（）将此集合清空

contains（Object对象）判断集合中是否有该对象

containsAll（Collection对象）判断一组对象是否在集合中存在

equals（Object对象）对象比较

hashCode（）哈希码 isEmpty（）判断集合是否为空

iterator（）为Iterator接口实例化 remove（Object）删除指定对象

还有removeAll（），retainAll（）保存指定内容

size（）返回集合大小    toArray（）将集合变为对象数组

---

List

因为是Collection的子接口，相同的方法不再赘述，仅展示扩展的方法。

indexOf(Object对象)查找指定元素的位置，LastIndexOf(Object对象)从后往前找

get(int Index)返回指定位置的元素

subList(int formIndex , int toIndex)  取出指定区间的子集合

set（int Index  ,  对象）替换指定位置的对象

常用子类：ArrayList，Vector，LinkedList

ArrayList	Vector
新的 *** 作类	旧的 *** 作类
使用异步处理，性能高，非线程安全	使用同步处理，性能低，线程安全
只能用Iterator，foreach输出	可以用Iterator，foreach，Enumeration输出

LinkList还实现了Queue接口 的方法

方法	描述
remove（）	检索并删除表头
element（）	返回表头
offer（指定元素）	将指定元素添加到链表末尾
peek（）	返回但不删除表头
poll（）	返回并删除表头
addFirst（元素）	在链表开头添加
addLsat（元素）	在链表末尾添加
removeFrist（）	删除链表的第一个元素
removeLast（）	删除链表的最后一个元素

set

set接口没有对Collection的方法进行扩充，反而更严格了，不能加入重复的元素。

有HashSet与TreeSet两种子类，HashSet散列表，无序。TreeSet可以排序。

用TreeSet时，要用覆写了compareTo（）的类

该方法返回一个 int，返回1代表比传入的对象大，0相等，-1小。

关于重复元素问题：Set判断是否是同样元素是 通过元素里 的equals（）方法判断，如果你的一个类中没有覆写equals方法的话，那么默认的equals（）仅仅是比较了他们的hash值是否相同。如果两个对象的属性完全相同，默认的

equals也会认为这两个对象是不同的元素。

因此你要覆写对象中的equals（），返回ture表示相同，false为不同

SortedSet接口

comparator（）	返回与排序有关的比较器
first（）	返回集合中的第一个元素
last（）	返回最后一个
headSet（元素）	返回从开头到指定元素的Set集合
subSet（元素1，元素2）	返回指定元素之间的集合
tailSet（元素）	返回从指定元素到最后的Set集合

集合的输出

使用迭代器才是最标准的集合输出方式

Iterator（常用）

hasNext（）	判断是否有下个值
next（）	取出当前元素
remove（）	移除当前元素

通过集合的iterator（）方法来实例化，单向迭代

在用iterator进行输出的时候可以用iterator的remove，这是可以的。但调用原先集合的remve方法的化话终止迭代输出，出现异常。

ListIterator双向迭代输出

是 Iterator的子接口，主要为List接口的类服务

add（元素）	将元素添加到集合
hasPrevious（）	判断是否有前一个
previous（）	返回下一个元素
nextIndex（）	返回下一个元素的索引号
previousIndex（）	返回前一个元素的索引号
set（元素）	替换元素

通过LIst里的ListIterator（）方法来实例化

Enumeration（废弃）

主要是为Vector类对象提供迭代输出

hasMoreElements（）	判断是否有下个值
nextElement（）	返回下一个值

Map接口

clear（）	清空Map集合
containsKey（元素key）	判断是否有该key
containsValue（元素）	判断是否有该value
entrySet（）	返回Set集合，里面的元素都是Map.Entry对象
get（key）	通过key得到value
isEmpty（）	判断是否为空
keySet（）	取得所有的key
put（key，value）	放入键值对
putAll（Map对象）	放一堆
remove（key）	根据key输出value
size（）	返回大小
values（）	返回全部的Value集合

Map.Entry是Map中的定义的一个接口，专门用来保存键值对

getKey（）	返回key
getValue（）	返回值
setValue（值）	设置值

Map的常用接口

HashMap	无序存放，新的，key不允许 重复
Hashtable	无序存放，旧的，key不允许 重复
TreeMap	可以排序，按key来排序，key不允许 重复
WeakHashMap	弱引用的Map集合
IdentityHashMap	key可以重复

HashMap与HashTable的差别 和 ArrayList与Vector的差别一样

SortedMap接口

comparator（）	返回比较器对象
firstKey（）	返回第一个key
head Map（key）	返回小于等于指定key的集合
lastKey（）	返回最后一个key
subMap（key1，key2）	返回指定范围key的集合
tailMap（key）	返回大于指定key的集合

想要使用该接口的类必须 实现Comparable接口

Collections集合工具类

一下方法皆为静态方法

addAll（集合对象，元素........）	为集合添加你传入的 元素，是可变参数，可以传任意个元素
revertse（集合对象）	将集合中的元素都反转一遍
binarySearch（集合，元素）	搜索集合中是否有指定的元素，有则返回1，没有则返回-1
replaceAll（集合，元素1，元素2）	将集合中的元素1替换为元素2
sort（集合）	排序集合
swap（集合，index1，index2）	交换index1与index2的位置

Stack栈

empty（）	判断是否为空
peek（）	返回栈顶，不删除
pop（）	返回栈顶，并删除
push（元素）	将元素放入栈
search（元素）	在栈中查找

---

集合的排序原理：二叉树

每个节点都可以有左子节点，右子节点，每一个节点都有一个值

 

插入基本逻辑是，小、相同的放左边，大的放右边

Node节点 二叉数排序速度>选择>冒泡

核心思想还是一个递归的原则

  public class Node {
    // 左子节点
    public Node leftNode;
    // 右子节点
    public Node rightNode;
    public Object value;
// 插入 数据
public void add(Object v) {
    // 如果当前节点没有值，就把数据放在当前节点上
    if (null == value)
        value = v;

    // 如果当前节点有值，就进行判断，新增的值与当前值的大小关系
    else {
        // 新增的值，比当前值小或者相同
         
        if ((Integer) v -((Integer)value) <= 0) {
            if (null == leftNode)
                leftNode = new Node();
            leftNode.add(v);
        }
        // 新增的值，比当前值大
        else {
            if (null == rightNode)
                rightNode = new Node();
            rightNode.add(v);
        }

    }

}

// 中序遍历所有的节点
    public List