黑马程序员技术交流社区

标题: ArrayList、Linklist的问题 [打印本页]

作者: java.love 时间: 2013-4-27 22:39
标题: ArrayList、Linklist的问题
本帖最后由 java.love 于 2013-4-28 13:22 编辑

ArrayList、Linklist、HashSet、TreeSet的区别和关系。学的有点蒙，哪位大神能解释一下他们的相同点和不同点，在编程中的用途

作者: 夏晓彤 时间: 2013-4-27 22:48
ArrayList和LinkList的父类接口是List前底层数据结构是数组，查询比较快修改慢，后者是链表机构，修改快查询慢，HashSet和TreeSet是Set集合，集合中的元素不可重复 TreeSetj可以实现对集合内的数据进行排序

作者: 海不扬波 时间: 2013-4-27 22:53
java的集合就那么几种总体为：List，Set，Map (都是接口由其子类去实现具体的方法)

ArrayList，LinkedList，Vector都属于List

List：元素是有顺序的，元素可以重复因为每个元素有自己的角标（索引）
  |-- ArrayList:底层的数据结构是数组结构，特点是：查询很快，增删稍微慢点，线程不同步

  |-- LinkedList：底层使用的是链表数据结构，特点是：增删很快，查询慢。

  |--Vector:底层是数组数据结构，线程同步，被ArrayList代替了，现在用的只有他的枚举。

Set：元素是无序的，且不可以重复（存入和取出的顺序不一定一致），线程不同步。

  |--HashSet：底层是哈希表数据结构。根据hashCode和equals方法来确定元素的唯一性

  |--TreeSet：可以对Set集合中的元素进行排序（自然循序），底层的数据结构是二叉树，也可以自己写个类实现Comparable 或者 Comparator 接口，定义自己的比较器，将其作为参数传递给TreeSet的构造函数。

Map：这个集合是存储键值对的，一对一对往里存，而且要确保键的唯一性（01，张三）这样的形式打印出来就是  01=张三
|--HashTable：底层是哈希表数据结构，不可以存入null键和null值，该集合线程是同步的，效率比较低。出现于JDK1.0

|--HashMap：底层是哈希表数据结构，可以存入null键和null值，线程不同步，效率较高，代替了HashTable，出现于JDK 1.2

|--TreeMap:底层是二叉树数据结构，线程不同步，可以用于个map集合中的键进行排序

作者: 赵崇友 时间: 2013-4-27 23:39
首先明确它们关系，ArrayList和LinkedList属于List集合的子类，HashSet和TreeSet属于Set集合，而List和Set属于Collection集合。
List集合中存放的元素可以重复且是有序的，Set集合中存放的元素不可重复且无序（注：可以通过TreeSet实现有序）。
List集合下的两个子类ArrayList和LinkedList继承了List的特性，只是两个集合的底层实现的数据结构不同，导致了它们的用途不同。
ArrayList使用了数组结构，因此可以操纵数组脚标快速实现查询功能，但是要用到增加和删除操作的话，由于要移动数组元素因此效率会较低。
LinkedList使用的是链表结构，它使用指针来逐个查询元素，导致效率较低，不过增加和删除操作比较快，这是由于当增删操作时，只需要更改前一个元素和后一个元素指针的指向就可以完成了，效率是很高的。
同样的，Set集合下的两个子类HashSet和TreeSet集合，也由于它们的数据结构不一样，功能也不同。
HashSet使用哈希表，它保证元素唯一性的原理是复写hashCode和equals方法，因此当我们自定义类的时候，且需要存入HashSet集合中，这两个方法一般是必须覆盖的。但是，这个集合输出是无序的。
TreeSet使用二叉树结构，因此利用二叉树的原理可以实现排序，但是当我们自己定义类存入TreeSet集合，需要自定义类实现Comparable接口，并覆盖其中的compareTo方法，或者自定义一个比较器实现Comparator接口，复写compare方法（这里要注意泛型的界定），然后将比较器作为参数传递给TreeSet集合即可。
具体使用哪个，楼主应该清楚了吧。不知道我说清楚了没……{:soso_e117:}

作者: 李大伟 时间: 2013-4-28 09:26
这是毕老师视频截的图，

参考此图
Collection
       --List 元素有序的，元素可以重复，因为该集合有索引
         --ArrayList  底层数组结构，特点：查询，修改速度快，增加删除稍慢，线程不同步，
             默认长度10，超过10 ，new 50%增加的数组。
                   判断和删除以来equals
             --LinkedList 链表结构，特点：查询稍慢，增加删除快
                       --Vector    底层是数组数据结构，线程同步。被ArrayList替代
                     默认长度10，超过10 ，new 100%增加的数组。支持枚举

       --Set 元素是无序（存入和取出数序不一定一致，元素不可以重复
   --HastSet 底层数据结构是哈希表 ,线程是非同步的。
                        如何保证元素唯一性，
                        通过元素的两个方法，hashCode和equals来完成
                              如果元素hashCode值相同，才会判断equals是否为true
                              如元素hashCode值不同，不会调用equals

                              判断元素是否存在，以及删除，依赖的方法是元素的hashCode和equals方法。
        --TreeSet 底层数据结构是二叉树，
              可以对Set集合中的元素进行排序
              保证元素唯一性的方法是compareTo方法return 0；

                    TreeSet排序的第一种方式，让元素自身具备比较性
              元素需要实现Compareable接口，覆盖compareTo方法。
              这种方法也称为元素自然顺序

               TreeSet排序第二种方式，自定义比较器
              当两种排序都存在时，以比较器为主
定义比较器
定义一个类，实现Comparator接口，覆盖compare方法。
以return 0 判断元素是否相同

   set集合功能和Collection是一致的

Map
      --Hashtable  底层是哈希表数据结构，不可以存入空，线程同步  jdk1.0
      --HashMap 底层是哈希表数据结构，可以存入空，线程不同步。jdk1.2 效率高
      --TreeMap 底层是二叉树数据结构，线程不同步，可以用于给map集合中的键进行排序。
      和Set很像，其实Set底层就是使用了Map集合。

map集合两种取出方式
1 Set<key> keySet:将map中所有的键存入到Set结合，因为set集合具备迭代器
      所有可以迭代方式取出所有的键，在根据get方法，获取每一个键对应的值
         map集合取出原理：将map集合转成set集合，通过迭代器取出。

   2 entrySet
          Set<Map.Entry<K,V>> entrySet()
      返回此映射中包含的映射关系的 Set 视图。
      将map集合中的映射关系存入到了set集合中
     而这个关系的数据类型就是：Map.Entry

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

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