疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

浅谈Java的集合体系


 

 
集合接口
 
 
 
Java集合类库将接口(interface)与实现(implementation)分离,如上图,Set是一个集合接口,而HashSet与TreeSet都是实现了Set接口的子类。
 
从上图中也可以看出,集合的基本接口是Collection。Collection<E>接口里有个iterator()方法(来自Iterable接口),该方法返回了一个实现了Iterator接口的对象,可以使用这个迭代器对象依次访问集合中的元素。
 
既然要迭代访问集合中的元素,那么就必须要考虑到如何获取下一个元素,如何判断已经遍历到结尾,如何移除一个元素等,所以Iterator接口就定义了这三个方法分别对应上述三个问题:next()、hasNext()、remove()等。
 
使用Iterator遍历的简单方式是for…each。而由集合框架体系图可以知道,Collection扩展了Iterable接口,并且所有集合都实现自Collection接口,所以我们可以知道:标准类库的任何集合都可以使用for…each循环。
 
使用for each的简单举例如下:
 
 
 
List<String> strs = new ArrayList<String>()
 
//此处省略,add some params;
 
for(String str: strs){
 
     //do sth;
 
}
 
 
 
具体的集合
 
 
 
链表
 
如果从一个数组的中间位置删除一个元素,之后的所有元素都要向前移动一个位置。插入一个元素也是如此(之后的元素统一要向后移动),代价是比较大的。
 
 
 
而链表则不同。链表将每个对象存放在独立的节点中,每个节点还存放着下一个节点的引用,并且链表都是双向链接的(存放着上、下节点的引用)。所以,从链表中删除一个元素,只需要更新所删除元素附近的节点即可。可以想象一下,几个小朋友手拉手,站在中间的小明同学离开了,那么只要小明左边和右边的小朋友重新拉手就好了。
 
链表是一个有序集合,每个对象的位置比较重要。由于迭代器是描述集合位置的,所以,依赖位置的元素的添加由迭代器来负责。
 
使用迭代器添加元素只针对有序集合有意义,像Set这种无序集合就没有位置可言,但这些无序集合也都是Iterator的派生类,那么如果Iterator接口定义了add方法,就导致像Set这种集合也必须强制实现Iterator里的这个add方法,因此,Iterator接口里就没有定义add方法,而把add方法定义在一个子接口ListIterator中。所以你再看一下开始的框架体系图,分出来一个ListIterator接口之后,仅仅让有顺序需求的集合去实现它。
 
链表也有软肋,例如不支持快速随机访问。如果要查看链表中第n个元素,就必须从头开始,越过n-1个元素。使用链表的唯一理由是:尽可能减少在列表中间插入或删除元素所付出的代价。如果列表中只有少数几个元素,用ArrayList就OK了。如果需要对集合进行随机访问,就使用数组或者ArrayList,不要使用链表。
 
数组列表
 
有两种访问元素的协议,一种是上文提到的使用迭代器,还有一种是使用get和set来随机访问。数组对于后者很管用。
 
ArrayList封装了一个动态再分配的对象数组。Vector也是个数组。二者的区别是,Vector的所有方法都是同步的,如果只有一个线程访问Vector,代码要在同步操作上浪费大量时间。而ArrayList不是同步的,因此,在不需要同步时使用ArrayList。
 
 
散列集
散列表可以快速查找对象。散列表为每个对象计算一个散列码(hash code,由对象中的实例域产生的一个整数)。不同数据域的对象产生不同的散列码。所以,如果自己定义类,就要负责实现这个类的hashCode方法。但是要注意,自己实现的hashCode方法应该与equals兼容(a.equals(b),则a与b的散列码必须相同)。
 
在Java中,散列表用链表数组实现,每个链表称为桶(bucket)。(如上图有16个桶)。在查找表中对象的位置时,先计算对象的散列码,然后与桶的总数取余。(散列码 % 桶的总数)。如果计算出的对象所在的桶已经满了,没法放置该对象,这就造成散列冲突(hashcollision)。这时,用新对象与桶中所有对象比较,看该对象是否已存在。如果某个桶快要满了,就要进行再散列,创建一个更大的桶,并将所有元素插入到这个新桶中,丢弃原来的桶。
 
HashSet实现了基于散列表的集,不关心元素的顺序时,使用HashSet。
树集
 
TreeSet是个有序集合,以任意顺序将元素插入到集合中,对集合遍历时,每个值将自动按照排序后的顺序呈现。排序是用树结构完成的(如红黑树)。在需要排序时使用TreeSet,不需要排序时使用HashSet。
 
那么TreeSet是如何排列元素的呢?
 
TreeSet假定插入的元素都实现了Comparable接口。如果插入自定义对象,就必须通过实现Comparable接口定义排序规则,然后它就会去找这个覆盖的方法查看规则。
 
但是这样有个灾难性的问题:如果某个对象在某个集合中按A方式排序,在另一个集合中按B方式排序,那就没辙了,能覆盖的方法只有一个,规则只能定一次。
 
所以,game over?不。TreeSet基于上面的问题,便有了另一种排序方式:使用Comparator接口。该接口声明了一个compare方法。如果按照A方式排序,那么就定义一个实现了Comparator接口的类,将这个类的对象塞到TreeSet的构造器中。可能需要一个例子说明一下:
 
public static void main(String args[]){
 
           SortedSet<Item> parts = new TreeSet<Item>();
 
           parts.add(new Item("张三","100"));
 
           parts.add(new Item("李四","130"));
 
           parts.add(new Item("王二麻子","120"));
 
 
 
           SortedSet<Item> sortByWeight = new TreeSet<Item>(new Comparator<Item>(){
 
                public int compare(Item a,Item b){
 
                     String weight1 = a.getWeight();
 
                     String weight2 =b.getWeight();
 
                     return weight1.compareTo(weight2);
 
                };
 
           });
 
           sortByWeight.addAll(parts);
 
           System.out.println(sortByWeight.toString());
 
     }
 
 
 
队列和双端队列
 
 
 
队列可以让人们有效的在尾部添加一个元素,在头部删除一个元素。双端队列可以在头部、尾部同时添加或者删除元素。
 
Deque接口由ArrayDeque和LinkedList类实现。这两个类都提供了双端队列,且必要时可以增加队列长度。
 
映射表
 
HashMap和TreeMap是映射表的两个通用的实现。HashMap对键进行散列,TreeMap用键的整体排序对元素进行排序,并将其组织成搜索树。