LinkedList、ArrayList、 Vector、HashSe ...区别（转）

集合框架：Java中预定义的一些数据结构类
集合框架是定义在Java.util包中


Collection  
        |--------List
                    |----------LinkedList
                    |----------ArrayList
                    |----------Vector
                                     |-----Stack
        |--------Set
                    |----------HashSet
                    |----------TreeSet
Map
        |---------HashMap
        |---------TreeMap


Collection ：  表示一组数据的类
  List和Set都继承了Collection
         列表List: 有序的 Collection
                  常用的List实现类：       (取出元素可以用迭代器和下标)
          ArrayList, LinkedList,Vector 都是List的实现类
            Stack是Vector的子类
               ArrayList  数组序列
               LinkedList 链表
               Stack      栈  
               Vector     向量 
          集合Set: 无重复的 Collection
                 常用的Set实现类：   取出元素用迭代器（没有get方法）
              HashSet() 
            TreeSet()

映射 Map<K,V>
          将键映射到值的一种结构
          键是一个Set，键不能重复
          每一个键都对应一个值
               常用的Map实现类：
         HashMap():键是一个HashSet         
       TreeMap():键是一个TreeSet
        

*********************************************
ArrayList:
      数组序列   ：有序的，可重复的，长度可变的，有下标的，地址连续的[基于数组]
                  优势：因为地址连续， 一旦数据存储好了，查询操作效率比较高
                     劣势：插入和删除操作效率比较低  ，不是线程同步的  
                
      add()
      set()
      get()  只是获取
      size()
      remove() 获取并移除
      contains()
      indexof()
 
练习：班上有20位同学 ，学号是从1001~1020
             从班上抽出一个一等奖
                                两个二等奖
                                五个三等奖    
                                八个安慰奖
              所有获奖的人不能重复

public class ListDeno2 {
public static void main(String[] args) {

    ArrayList<Integer> list=new ArrayList<Integer>();
    for(int i=1001;i<=1020;i++){
        list.add(i);
    }
    // 创建随机数对象
    Random rd=new Random();

    //抽取一等奖
    int index=rd.nextInt(list.size());// 随机下标
    // 将抽到的数据移除
    //int n=list.get(index);  get()是获取下标为index的元素
    //list.remove(index);     remove()是移除下标为index的元素，并返回下标
    int  n= list.remove(index);//所以可以直接用remove()
    System.out.println("一等奖是"+"学号为"+n);

    //抽取二等奖
    for(int i=0;i<2;i++){
        int index2=rd.nextInt(list.size());
        int n2=list.remove(index2);
        System.out.println("二等奖是"+"学号为"+n2);
    }
    //抽取一等奖
    for(int i=0;i<5;i++){
        int n3=list.remove(rd.nextInt(list.size()));
        System.out.println("三等奖是"+"学号为"+n3);
    }
    //抽取一等奖
    for(int i=0;i<8;i++){
        int n4=list.remove(rd.nextInt(list.size()));
        System.out.println("安慰奖是"+"学号为"+n4);
    }

}
}

            
***************************************************            
LinkedList：链表，链式序列
                 有序的，可重复的，长度可变的，有下标的，地址任意的
                 地址任意的,各个数据之间通过引用[相当于C语言中的指针]关联
                 优势和劣势：     
                 地址是任意的，适合进行插入和删除的操作
                 查询操作性能比较低       
取出元素：
LinkedList<String> list = new LinkedList<String>();
方法一：下标
   for(int i=0;i<list.size();i++){
String str = list.get(i);
System.out.println(str);
}
方法二：poll()方法
   while (!list.isEmpty()) {
String str = list.poll();
System.out.println(str);
}

数组查询方式：                        
int[] t=new int[5];
      创建对象时 开辟了地址连续的内存空间  0x10 0x11 0x12 0x13 0x14
  t -->0x10(t指向内存地址为0x10的存储空间)
t[0] -->0x10+0
t[1] -->0x10+1
t[4] -->0x10+4=0x1014
所以ArrayList查询操作效率比较高，
*****************************************************
Vector:向量
       Vector和 ArrayList一样，都是大小可变的数组的实现
                       区别： ArrayList不是同步的
             Vector是同步的，在多线程中一般采用Vector
           使用方式和 ArrayList一样

stack:栈
            它通过五个操作对类 Vector 进行了扩展
            它提供了通常的 push 和 pop 操作，
                    取堆栈顶点的 peek 方法
                    测试堆栈是否为空的 empty 方法
                   在堆栈中查找项并确定到堆栈顶距离的 search 方法。
          后进先出
          最先放入的数据在栈的底部
          最后放入的数据在栈的顶部
          每次取数据都只能取到栈顶的数据
***************************************************         
HashSet() : 无序的，不可重复的，长度可变的        
     (如果添加内容不变，则输出顺序不变  因为HashSet()将内容通过哈希算法转化为内存地址，输出是按内存地址大小输出)
TreeSet():根据内容的自然顺序进行排序
     (如果是字符或字符串，按照ASC码大小输出)
练习：
   String[] item = {"张三疯","李四光","王二小","张三疯","赵六子",
   "童胖子","周芷若","张无忌","王二小","小昭","周芷若","赵敏","谢逊"};
                   去掉数组中重复
                      按照名字排序

public class SetDemo2 {
    public static void main(String[] args) {

       TreeSet<String> set=new TreeSet<String>();

      String[] item = {"a张三疯","李四光","王二小","张三疯","赵六子",
       "童胖子","周芷若","张无忌","王二小","小昭","周芷若","赵敏",
       "谢逊","张无忌","王二小","b小昭","周芷若","赵敏","谢逊"};
         for(int i=0;i<item.length;i++){
             set.add(item[i]);
         }
        Iterator<String> iter=set.iterator();
        while(iter.hasNext()){
        String str=iter.next();
        System.out.println(str);
        }
//      char a='张';
//      char b= '李';
//      char c= '王';
//      System.out.println(a+0);
//      System.out.println(b+0);
//      System.out.println(c+0);


    }
}

******************************************************
List实现类：      取出元素可以用迭代器和下标
eg：ArrayList<String> list=new ArrayList<String>();
//取出元素三种方法：1.使用下标
for(int i=0;i<list.size();i++){
String str=list.get(i);
System.out.println(str);
}
//2.使用迭代器
Iterator<String> iter=list.iterator();
while(iter.hasNext()){
String str=iter.next();
System.out.println(str);
}
//3.增强的For循环
for(String str:list){
System.out.println(str);
}                  
Set实现类：   取出元素用迭代器（没有get方法）
eg:
方法一：
  1.将Set中的数据放入迭代器，并返回该迭代器     
    HashSet<String> set = new HashSet<String>();
    Iterator<String> iter = set.iterator();
  2.开始迭代
    while (iter.hasNext()) {// 判断迭代器中是否还有元素
     String str = iter.next();// 取出一个元素，取出一个，迭代器中就少一个
     System.out.println(str);
}
方法二：
   增强版的for循环
   for (String str : set) {
System.out.println(str);
}
********************************************************
HashMap():k是一个HashSet
TreeMap():k是一个TreeSet
         所有的K不能重复，每一K都对应一个Value
         如果在加入数据的时候，出现相同的K，则替换掉原有的Value
取出数据：
1.取得所有的k
   HashMap<String,Integer> map = new HashMap<String,Integer>();
   Set<String> set = map.keySet();
2.迭代Set
Iterator<String> iter = set.iterator();
while(iter.hasNext()){
//取得一个K
String key = iter.next();
//根据K获得Value
int value = map.get(key);
System.out.println(key+" "+value);
}

练习：
    String str = "abbcccddddeeeeeffffffggggggg";
统计这个字符串中每个字符出现的次数
(提示：Map  k:字符   V：次数)

public class MapDemo {
public static void main(String[] args) {
     HashMap<Character,Integer>  map=new HashMap<Character,Integer>();

     String str = "abbcccddddeeeeeffffffggggggg";
     // 循环取出字符串中的字符
     for(int i=0;i<str.length();i++){
        //根据下标取得字符
       char c=str.charAt(i);

        //将字符放入map
        //判断该字符是否已经存在于map的K中
        boolean b=map.containsKey(c);
       if(b){//如果b为true，则该字符已经出现过
            //如果已经出现过，就先获得该字符已经出现过的次数
          int value= map.get(c);
          value++;
          map.put(c,value) ;
       }else{//如果b为false，这字符是第一次出现
            //如果是第一次出现，就直接放入Map中，次数为1
          map.put(c, 1) ;
       }

     }

     //取出数据
    Set<Character> set=map.keySet();
    Iterator<Character> iter=set.iterator();
    while(iter.hasNext()){
        Character key=iter.next();
        int value=map.get(key);
        System.out.println(key+" "+value);
    }
}
}

********************************************************
泛型：在定义类的时候，定义一个不具体的类型，这个类型会在类中的代码中使用到
           在加载类的时候，并没有明确是什么类型
           在创建对象的时候，在指定具体的类型
            如果没有制定具体的类型，则默认采用Object类
*************************************************************

总结内容：
1. ArrayList和LinkedList的区别和使用场景  
ArryList 与linkedList 都实现了List 接口
    ArrayList:实现list接口 采用数组结构保存对象
              优点：便于对集合进行快速的随机访问 查询操作效率比较高
              缺点：插入和删除操作效率比较低
              原因：指定位置索引插入对象时，会同时将此索引位置之后的所有对象相应的向后移动一位。删除会同时向前移动一位。
    linkedList:实现list接口 采用链表结构保存对象
              优点：插入和删除操作效率比较高
              缺点:查询操作效率比较低
              原因：链表结构在插入对象时只需要简单的需该链接位置，省去了移动对象的操作 在查询上LinkedList只能从链表的一端移动到另一端故效率较低
使用场景：
  ArrayList使用场景:一般顺序遍历情况下使用ArrayList 尽量不对ArrayList进行插入或删除操作(删除尾部除外),若有多次删除/插入操作又有随机遍历的需求，可以再构建一个ArrayList，把复合 条件的对象放入新ArrayList，而不要频繁操作原ArrayList

  LinkedList使用场景:经常有删除/插入操作而顺序遍历列表


2. ArrayList和Vector的区别和使用场景
相同点：
ArrayList 和Vector是实现List接口，采用数组方式存储数据，此数组元素数大于实际存储的数据以便增加和插入元素，都允许直接序号索引元素，但是插入、删除数据要涉及到数组元素移动等内存操作，所以索引数据快 插入、删除数据慢.
区别：
1.Vector是同步的。这个类中的一些方法保证了Vector中的对象是线程安全的。而ArrayList则是异步的，因此ArrayList中的对象并不是线程安全的
2.ArrayList有3个构造函数，而Vector有4个构造函数。Vector除了包括和ArrayList类似的3个构造函数之外，另外的一个构造函数可以指定容量增加系数。
3.当你向这两种类型中增加元素的时候，如果元素的数目超出了内部数组目前的长度它们都需要扩展内部数组的长度，Vector缺省情况下自动增长原来一倍的数组长度，ArrayList是原来的50%
使用场景：
  ArrayList使用场景:因为同步的要求会影响执行的效率，所以如果你不需要线程安全的集合那么使用ArrayList是一个很好的选择，这样可以避免由于同步带来的不必要的性能开销
  Vector使用场景: 如果你要在集合中保存大量的数据那么使用Vector有一些优势，因为你可以通过设置集合的初始化大小来避免不必要的资源开销。 


3. HashSet与TreeSet的使用场景
HashSet：哈希表是通过使用称为散列法的机制来存储信息的，元素并没有以某种特定顺序来存放
TreeSet：提供一个使用树结构存储Set接口的实现(红黑树算法)，对象以升序顺序存储，访问和遍历的时间很快。
使用场景:HashSet是基于Hash算法实现的，其性能通常都优于TreeSet。我们通常都应该使用HashSet，在我们需要排序的功能时，我们才使用TreeSet。


4.HashSet与TreeSet的底层运行方式:
TreeSet集合对象的加入过程：
TreeSet的底层是通过二叉树来完成存储的，无序的集合
当我们将一个对象加入treeset中，treeset会将第一个对象作为根对象，然后调用对象的compareTo方法拿第二个对象和第一个比 较，当返回至=0时，说明2个对象内容相等，treeset就不把第二个对象加入集合。返回>1时，说明第二个对象大于第一个对象，将第二个对象放 在右边，返回-1时，则将第二个对象放在左边，依次类推

HashSet集合对象的加入过程：
hashset底层是hash值的地址，它里面存的对象是无序的。
第一个对象进入集合时，hashset会调用object类的hashcode根据对象在堆内存里的地址调用对象重写的hashcode计算出一个hash值，然后第一个对象就进入hashset集合中的任意一个位置。
第二个对象开始进入集合，hashset先根据第二个对象在堆内存的地址调用对象的计算出一个hash值，如果第二个对象和第一个对象在堆内存里 的地址是相同的，那么得到的hash值也是相同的，直接返回true，hash得到true后就不把第二个元素加入集合（这段是hash源码程序中的操 作）。如果第二个对象和第一个对象在堆内存里地址是不同的，这时hashset类会先调用自己的方法遍历集合中的元素，当遍历到某个元素时，调用对象的 equals方法，如果相等，返回true，则说明这两个对象的内容是相同的，hashset得到true后不会把第二个对象加入集合。


5. HashMap与TreeMap的使用场景
HashMap通过hashcode对其内容进行快速查找，而 TreeMap中所有的元素都保持着某种固定的顺序，如果你需要得到一个有序的结果你就应该使用TreeMap（HashMap中元素的排列顺序是不固定的）。
使用场景
HashMap:适用于在Map中插入、删除和定位元素。
Treemap:适用于按自然顺序或自定义顺序遍历键（key）