黑马程序员技术交流社区

标题: 集合类 [打印本页]

---

作者: 薛波    时间: 2012-3-17 08:23
标题: 集合类
list \ arraylist \ linklist \ map \set 等数据结构分别是怎么样？各自在优点与不足？存储方式？查询速度？

---

作者: lucky_xingxing    时间: 2012-3-17 08:29
首先是list  set  map的区别：        List单列集合，表示有先后顺序的集合，按先来后到的顺序排序。有时候，也可以插队，即调用add(int index,Obj e)方法，就可以指定当前对象在集合中的存放位置。可有重复元素，可以根据索引取单个或多个值。
        Set 单列集合 里面不允许有重复的元素，无序集合，要取值只能通过循环遍历
        Map，它是双列的集合，以键值对的形式进行存取，不能存储重复的key，可以获得key和value组合成的Map.Entry对象的集合。

Arraylist和linkedList
ArrayList是使用数组方式存储数据，允许直接按序号索引元素，但是插入元素要涉及数组元素移动等内存操作，所以索引数据快而插入数据慢而LinkedList使用双向链表实现存储，按序号索引数据需要进行前向或后向遍历，但是插入数据时只需要记录本项的前后项即可，所以插入速度较快。LinkedList也是线程不安全的

---

作者: 叶绍亮    时间: 2012-3-17 09:23
List接口
　　List是有序的Collection，使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引（元素在List中的位置，类似于数组下标）来访问List中的元素，这类似于Java的数组。
和下面要提到的Set不同，List允许有相同的元素。
　　除了具有Collection接口必备的iterator()方法外，List还提供一个listIterator()方法，返回一个ListIterator接口，和标准的Iterator接口相比，ListIterator多了一些add()之类的方法，允许添加，删除，设定元素，还能向前或向后遍历。
　　实现List接口的常用类有LinkedList，ArrayList，Vector和Stack。

ArrayList类
　　ArrayList实现了可变大小的数组。它允许所有元素，包括null。ArrayList没有同步。
size，isEmpty，get，set方法运行时间为常数。但是add方法开销为分摊的常数，添加n个元素需要O(n)的时间。其他的方法运行时间为线性。
　　每个ArrayList实例都有一个容量（Capacity），即用于存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加，但是增长算法并没有定义。当需要插入大量元素时，在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。
　　和LinkedList一样，ArrayList也是非同步的（unsynchronized）。

LinkedList类
　　LinkedList实现了List接口，允许null元素。此外LinkedList提供额外的get，remove，insert方法在LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈（stack），队列（queue）或双向队列（deque）。
　　注意LinkedList没有同步方法。如果多个线程同时访问一个List，则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List：
　　　　List list = Collections.synchronizedList(new LinkedList(...));


Map接口
　　请注意，Map没有继承Collection接口，Map提供key到value的映射。一个Map中不能包含相同的key，每个key只能映射一个value。Map接口提供3种集合的视图，Map的内容可以被当作一组key集合，一组value集合，或者一组key-value映射。


Set接口
　　Set是一种不包含重复的元素的Collection，即任意的两个元素e1和e2都有e1.equals(e2)=false，Set最多有一个null元素。
　　很明显，Set的构造函数有一个约束条件，传入的Collection参数不能包含重复的元素。
　　请注意：必须小心操作可变对象（Mutable Object）。如果一个Set中的可变元素改变了自身状态导致Object.equals(Object)=true将导致一些问题。

---

作者: 李飞    时间: 2012-3-17 11:39
  List接口   List集合有序(存储的顺序和取出的顺序一致)、可重复、可索引

      ListIterator：当对List集合用迭代器遍历的时候，如果想同时修改或是增加元素，这时集合和迭代器同时对元素操作，容易引起修改异常，此时用ListIterator。只适用于List集合
      indexOf(str)可以获取str第一次出现的位置，比数组遍历方便
      List集合是有序的，所以可以通过for循环来遍历集合中的元素
      ArrayList：底层数据结构数组，不同步，线程不安全，增删效率慢，查询快
           底层依据equals()方法
      LinkedList：底层数据结构链表，线程不安全，对元素的增删操作效率高
                  其一个元素多了前指针和后指针，所以增删效率高
           getFirst()获取元素，集合长度不改变
           removeFirst()获取元素，删除，集合长度改变；可以通过此方法遍历集合
           addFirst()
           addLast()
        

   Set接口    Set集合无序、不可重复

      HashSet：底层数据结构哈希表

      TreeSet：底层数据结构二叉树，可以对集合进行排序
           如何确定元素的唯一性？
       HashSet依赖的是元素的hashCode()和equals()方法,：
         1）首先判断元素哈希值
         2）哈希值不同，不需要再判断元素的equals()方法，返回false
         3）哈希值相同，判断equals()方法。如果equals()方法相同返回true，视为同一个元素；不同返回false,视为不同的元素，会存储在同一个哈希值上
         4）所以我们要重写hashCode()和equals()方法，hashCode()用来判断集合元素对象，而equals()用来判断元素对象的属性值是否相同
       TreeSet根据比较方法返回值，负数，放左边，整数放右边，零就代表重复   



双序列集合Map

     1）一次存一对元素，以键值对的形式<k,v>
     2）Map集合中的键必须确定唯一性

     取出集合元素两种方法：
     1）通过keySet()取出集合所有的键，对应Set集合，遍历Set集合取出key对应的value
     2）通过entrySet()取出键值映射的关系，对应Set集合，遍历Set集合，取得键和值
        这种取法，可以把一组键值看成是一个封装的对象^_^(个人理解)

     Hashtable:底层哈希表，同步，线程安全，不允许null作为键
         Properties，多用于配置文件的定义和操作，键值之间通过=，都是字符串

     HashMap：底层哈希表，不同步，线程不安全，运行null作为键，null作为值
         LinkedHashMap：有序，存入和取出的顺序一致

     TreeMap：可以对集合的键进行排序

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2