Java 集合

一、集合框架的基本思想

    如果需要处理一些类型相同的数据，人们习惯上使用数组这种数据结构，但数组在使用之前必须定义大小，而且不能动态定义大小。有时可能给数组分配了太多的单元而浪费了宝贵的内存资源，糟糕的是，程序运行时需要处理的数据可能多于数组的单元。当需要动态地减少或增加数据项时，可以使用集合这种数据结构。

    所谓框架（framework），就是一个类的集合，是构成创建高级功能的基础。框架包含许多子类，这些子类拥有非常有用的功能、政策和机制。框架用户建立的子类可以扩展类的功能，而不必重新创建基本的机制。

    实现与接口相分离：列表

 

二、对列表的两种实现方式

1、循环数组：效率高，有限集合

2、链表序列：效率低，无限集合

 

三、有两个用于集合的基本接口

1、Collection（集合）

2、Map（映像）à键值对à找到键就找到值。

 

四、集合的继承与实现关系

Collection（集合）                          Map（映像） Iterator（迭代器）

↑                                        ↑                ↑

    ----------------------------------                        ↑                ↑

↑                              ↑                        ↑                ↑

List（列表有序，元素可重复）   Set（集，无序，不重复）  SortedMap       ListIterator

                                ↑                    （存储式映像）    （列表迭代器）

                            SortedSet（存储集）

   

RandomAccess（随机存取，接口），可以使用该接口来测试某个集合是否支持有效的随机访问。

 

1、集合框架中各个类之间关系（用于本地机器，效率高，不考虑安全问题，即线程不安全）

            AbstractCollection                          AbstractMap

                    ↑                                       ↑

――――――――――――――――――――                ―――――――

↑                          ↑                  ↑         ↑

 AbstractList                  AbstractSet           HashMap  TreeMap

↑                          ↑

 ________________________­____   __________________

        ↑                  ↑          ↑          ↑

AbstractSequentialList  ArrayList    HashSet    Treeset

    ↑             

LinkedSet

 

2、集合框架中的旧类（用于网络中，因为线程安全，但效率低）

        List                            Map

        ↑                              ↑

 AbstractList                      Hashtable

        ↑                              ↑

     Vector ------  RandomAccess    Properties

        ↑

      Stack

 

五、链表（LinkedList），又称链接列表

    链表是由若干个称做节点的对象组成的一种数据结构，每个节点含有一个数据和下一个节点对象的引用（单链表），或含有一个数据并含有上一个节点对象的引用和下一个节点对象的引用（双链表）。该类在java.util包中。

1、new LinkedList();//创建链表

2、add//增加元素，这时不需要去安排节点中所存放的对下一个或上一个节点的引用。

3、可以使用get方法获取第I个节点中存储的数据。注意：由于任何类都是Object类的子类，因此可以把任何一个对象作为链表的节点对象。需要注意的是当使用get方法获取一个节点对象后，要用类型转换运算符转化回原来的类型。

3、iterator：取行迭代器

4、循环

1）是否有下一个：hasNext

2）如果有下移：next

3）下移返回的结果可以输出或修改

 

六、数组列表（ArrayList）

    ArrayList封装了一个动态再分配的Object[]数组。

    注意：如果你是个经验丰富的Java编程员，那么每当你需要一个动态数组时，你可能使用过Vector类。那么现在为什么使用ArrayList而不使用Vector了呢？这里有一个简单的理由。Vector类的所有方法都是同步式（synchronized）方法。你可以安全地从两个线程来访问Vector对象。但是，如果你只从单个线程来访问Vector对象，（这是更加常见的情况），那么你的代码将会在同步操作上浪费相当多的时间。相反，ArrayList方法不属于同步式方法。建议你在不需要同步时使用ArrayList方法，而不使用Vector方法。

 

七、散列集（Set）

1、如要找某个元素但不记得该元素的位置只能遍历。如果集合中含有许多个元素，那么这个查找过程是很费时间的。

2、如不在乎元素的顺序有多种数据结构能快速找到该元素

3、缺点：这些数据结构无法使你控制元素出现的顺序。这些数据结构将根据它们自己的方便来组织各个元素的顺序。

4、所谓散列集：就是存在不重复的多个元素的集合

5、有一种叫“散列表”的结构，可以查找所需对象

1）散列表为每个对象计算一个整数，叫散列码

2）散列表是个链接式列表的阵列，每个列表称为一个散列单元，若要查找表中的某个对象的位置，只要算出它的散列表码，再将它减以散列表元的总数为模的值，得到拥有该元素的散列表的索引。

3）如要更好的控制散列表的运行性能，可设定一个初始的散列表元的数量。

4）初始表无数量设置为预期元素数量的150％.

6、java加载因子（load facter）将决定何时对散列表进行再散列。默认值0.75，对于大多数应用应保持此值。

7、散列集的add方法将设法找出要添加的对象，并且只有在该对象不存在的情况下才添加该对象。

8、HashSet类用于根据散列表来实现一个散列集，默认构造器能建立拥有一个101个散列表加载因子为0.75的散列表。

9、加载因子初始化容量可以在构造器中指定:HashSet(int initialCapacity)、HashSet(int intitialCapaicty,float loadfactor)

10、可以用add方法来添加元素。Contains方法已经被重新进行了定义，它可以用来进行快速查找，以便了解散列集中是否已经存在某个元素。它只检查某个表元中的各个元素，而不检查集合中的所有元素。

11、散列集迭代器依次访问所有散列表元

12、由于散列表机制将各个元素放置在攻列表中的各个位置上，因此这些元素显然以随机顺序访问的，只有在不在乎集合中各元素的顺序时，才使用散列表。

13、可以将字符串插入到散列集内，因为String类配有一个hashCode方法，可以用于计算字符串的散列码。散列码是个根据字符串中的字符计算得出的一个整数。散列码可以由String类的hashCode函数产生的。HashCode方法是在Object类中定义的。因此，每个对象都有一个默认散列码。该散列码是由对象的内存地址派生而来的。

八、树集（TreeSet）

    1、树集是由一些节点对象组成的数据结构，节点按着树形一层一层地排列。

2、树集是个有序集合。可以按照任何顺序将元素插入该集合。当迭代通过该集合时，各个值将自动按照排序后的顺序出现。

3、将一个元素添加给树集的速度要比将它添加给散列表要慢，但是仍然比将它添加到数组或链接式列表中的正确位置要快。

4、树集的排序顺序必须是个综合顺序，也就是说任何两个元素都必须是可比的，同时，只有当元素相同时才能对它们进行比较。

5、和链表不同，当使用构造方法TreeSet()创建树集，再用add方法增加节点时，节点会按其存放数据的字典顺序一层一层地依次排列，在同一层中的节点从左到右按字典顺序递增排列，下一层的都比上一层的小。

6、有很多对象不适合用字典顺序进行比较，这时创建树集可自己规定节点按照什么样的“大小”顺序排序。需要实现接口Comparable。Comparable接口中有一个方法，compareTo(Object b)，通过实现这个接口来规定它创建的对象的大小关系。如例2。

 

九、映像（Map）

1、散列集是个集合，它能迅速找到某个现有的元素，但是若要找一个元素，须拥有要查找元素的确切拷贝

2、若要快速定位某个元素通常要拥有某些关键字的信息

3、映像（Map）用于存放许多关键字／值对。如果你提供了关键字，就能找到它对应的值

4、java库提供了用于映象的两种通用的实现方法

1）散列映像：HashMap用于对关键字进行散列

2）树状映像：TreeMap使用关键字的综合排序顺序，在搜索树中对关键字进行组织。

5、散列函数或比较函数只能作用于关键字，与关键字相关的值不能进行散列或者比较。

6、散列映像的运行速度较快，如不需按照顺序来访问关键字，最好选用散列映像

7、关键字必须是独一无二的。不能为同一个关键字存放两个值。如使用同一个关键字两次调用put方法，那么第二个值便取代第一个值。

       8、put()、get()、remove()、size()

十、哈希表（Hashtable）

    散列表是使用相关关键字查找被存储的数据项的一种数据结构，关键字不可以发生逻辑冲突，即不要让两个数据项使用相同的关键字。散列表在它需要更多的存储空间时会自动增大容量。默认加载因子为0.75。

典型Hashtable类的作用与HashMap是相同的，实际上它们拥有相同的接口。与Vector类的方法一样，Hashtable类的各个方法也是同步的。如果不需要同步，或者不需要与旧代码相兼容，应该使用HashMap类。

 

十一、枚举接口

老的集合使用Enumeration接口来遍历各个元素序列。Enumeration接口配有两个方法，即hasMoreElements和nextElement。这些方法与Iterator接口的hasNext和next方法完全相似。

 

十二、属性集（Properties）

属性集是个类型非常特殊的映像结构。用于实现一组属性的Java平台类称为Properties。属性集可以用于为程序设定配置选项。有3个特殊的特性：

       1、关键字和值都是字符串。

       2、表可以保存到一个文件，也可以从一个文件那里加载。

       3、有一个默认辅助表。

 

Properties类扩展了Hashtable类的功能。这意味着Hashtable的所有方法都可以用于Properties对象。 

十三、栈（Stack）

堆栈是一种“后进先出”的数据结构，只能在一端进行输入或输出数据的操作。堆栈把第一个放入该堆栈的数据放在最底下，而把后续放入的数据放在已有数据的顶上。向堆栈中输入数据的操作称为“压栈”，从栈中输出数据的操作称为“弹栈”。由于堆栈总是在顶端进行数据的输入输出操作，所以弹栈总是先输出（删除）最后压入堆栈中的数据，这就是“后进先出”的来历。

从1.0版开始，Java标准库便拥有一个Stack类，它配有我们熟悉的方法push和pop。不过，Stack类扩展了Vector类的功能，因为从理论上讲，Vector类的功能是不能令人满意的，而在Stack类中，可以使用不同于栈的操作，比如insert和remove，将值插入到任何位置，并且可以从任何位置上删除有关的值，而不是仅仅能对栈的顶部的值进行这些操作。

 

 

十四、向量（Vector）

    Java的java.util包中的Vector类负责创建一个向量对象。当创建一个向量时不用像数组那样必须给出数组的大小。向量创建后，可以使用add方法把任何对象添加到向量的末尾，向量的大小会自动地增加。也可以用另一个add方法把一个对象追加到该向量的指定位置。可以使用elementAt方法获取指定索引处的向量的元素（索引初始位置是0）。可以使用size方法获取向量所含有的元素的个数。与数组不同的是向量的元素类型不要求一致。

1、创建：new

2、增加元素：add

3、取得迭代器：i=vector.elements()->Enumeration的对象

4、循环遍历。while(i.hasMoreElements()){Object o=i.nextElement();}

5、操作每个元素。

6、常用方法：构造函数，增加元素add(){通过添加若Vector内容有改变则返回true,反之则返回false}，删除元素remove()，清空clear()，判断为空isEmpty，首/末元素first(last)Element。

7、Hashtable与Vector的使用方法是一样的。它的值可以重复，但键不可以重复。