【Java学习笔记】集合

集合

集合(Collection)：一种能够存储多个对象且长度可变的容器

数组与集合的区别：

1. 数组是固定长度的，集合的长度可变
2. 数组存储的基本数据类型，集合存储的是引用数据类型
3. 数组不存在“键值对”，Set集合有一一对应的关系

集合框架

集合类型	集合子类	集合实现类
Collection(单列集合）	List(唯一具有增删改查)(有序，可以重复,可以为null)	LinkedList（链表结构） ArrayList（数组结构）
	Set（无序，不可以重复，可以为null）	HashSet（哈希表结构） LinkedHashSet TreeSet（树状结构）
	Queue（无序，不可以重复）
Map（对列结合）	-	HashTable：内部结构是哈希表，同步的。不允许null作为键值对； HashMap（哈希表结构），不同步的，允许null作为键值对。（hashSet底层用HashMap编写的） TreeMap（二叉树结构），不同步的，可以对Map的集合进行键值的排序

Collection

Collection接口是处理对象集合的根接口，其中定义了很多对元素进行操作的方法，AbstractCollection是提供Collection部分实现的抽象类

常用的方法
- add();添加一个元素到集合中去
- addAll();将指定集合中的所有元素添加到集合中
- toArray();返回一个表示集合的数组

List

概念

一个元素有序的，可以重复，可以为null的集合。
List的数据结构就是一个序列，存储内容时直接在内存中开辟一个块连续的内存空间，然后将空间地址与索引对应。

唯一一个具有增删改查功能的集合
可以操作角标

增删改查

1，添加
    void add(index,element);
    void add(index,collection)
2，删除；
    Object remove(index):
3，修改：
    Object set(index,element);
4，获取：
    Object get(index);
    int lastIndexOf(object);
    List subList(from,to);
    int indexOf(object);

List子类

子类	结构	使用场合
Vector	内部是数组数据结构，同步的。	增删，查询的很慢（已淘汰）
ArraryList	内部是数组数据结构，不同步的。	替代Vector，查找速度快
LinkedList	内部是链表数据结构，不同步的。	插入速度快。

ArrayList

本质上是数组，特点是查找速度快，比较常用

ArrayList构造器

ArrayList的构造函数总共有三个：
（1）ArrayList()构造一个初始容量为 10 的空列表。
（2）ArrayList(Collection

ArrayList的动态库容机制

根据传入的最小需要容量minCapacity来和数组的容量长度对比，若minCapactity大于或等于数组容量，则需要进行扩容。

• jdk1.6中，如果通过无参构造器，初始数组的容量为10，每次通过copeOf的方式扩容为原来的1.5倍+1
• jdk1.7开始，如果通过无参构造器，初始数组的容量为0，每次通过copeOf的方式扩容为原来的1.5倍

LinkedList

本质上是链表结构，特点是插入快。

ArrayList 和LinkedList的区别相当于顺序表和链表的区别

package name.liushiyao.collection.list;

import java.util.LinkedList;
import org.junit.Test;

/*

  利用LinkedList结构特性，模拟队列（FIFO先进先出）

 */
public class Queue<T> {

  private LinkedList linkedList;


  public Queue() {
    this.linkedList = new LinkedList();
  }

  //往队列中添加元素
  public void add(T para){
    linkedList.addLast(para);
  }
  //往队列里删除元素
  public T get(){
    return (T) linkedList.removeFirst(); //获取最后一个元素但是同时也会删除
  }
  //is null?
  public boolean isEmpty(){
    return linkedList.isEmpty();
  }

  @Test
  public void test(){

    Queue<String> queue = new Queue<String>(  );
    queue.add("liushiyao");
    queue.add("刘石尧");
    queue.add("123");
    String string = queue.get();
    System.out.println(string);

  }

}

ListIterator

一个能够双向遍历线性表的新列表迭代器ListIterator

在迭代器过程中，尽量不要使用集合操作元素，但是可以使用ListIterator完成迭代中对元素进行更多的操作。
功能：1.双向迭代 //next(); previous
2.修改List中的内容//set();

/*
  实现ListIterator的双向迭代和集合元素的操作
   */
  @Test
  public void Demo4(){
    List<String>  list = new ArrayList<String>();
    list.add("liushiyao");
    list.add("刘石尧");
    list.add("123");

    ListIterator listIterator = list.listIterator();
    while (listIterator.hasNext()){
      if(listIterator.next().equals("liushiyao")){
        listIterator.set("shiyao");
      }
    }

    while (listIterator.hasPrevious()){
      System.out.println(listIterator.previous());
    }
  }

在循环体中不要使用集合的remove方法，这样容易出错
1. 错误

@Test
  public void listRemoveTest() {

    List list = new ArrayList();
    list.add("我是元素一");
    list.add("我是元素二");
    list.add("我是元素三");
    Iterator iterator = list.iterator();
    while (iterator.hasNext()) {
      String string = (String) iterator.next();
      System.out.println(string);
      if (string.equals("我是元素二")) {
       list.remove("我是元素二");//不安全
      }
    }
    System.out.println(Arrays.toString(list.toArray()));
  }

输出：

我是元素一
我是元素二
[我是元素一, 我是元素三]

本想先依次输出List中的所有元素，结果只输出两个，因为当输出第二个元素的时候，符合删除条件，使用List.remove会影响到Iterator的遍历，造成遍历到第二个就结束了遍历。

1. 正确

@Test
  public void listRemoveTest() {

    List list = new ArrayList();
    list.add("我是元素一");
    list.add("我是元素二");
    list.add("我是元素三");
    Iterator iterator = list.iterator();
    while (iterator.hasNext()) {
      String string = (String) iterator.next();
      System.out.println(string);
      if (string.equals("我是元素二")) {
        iterator.remove();
      }
    }
    System.out.println(Arrays.toString(list.toArray()));
  }

输出：

我是元素一
我是元素二
我是元素三
[我是元素一, 我是元素三]

Set

概念

Set集合是无序的，不重复，可以为null

Set子类

Set接口中的方法与Collection一致。
- HashSet :内部结构是哈希表，为了快速查询
- LinkedHashSet：获取有序的链式哈希表
- TreeSet : 对Set集合中的元素进行排序

HashSet

HashSet集合数据结构是哈希表，所以存储元素的时候，
使用的元素的hashCode方法来确定位置(故Set集合为无序的)，如果位置相同，在通过元素的equals来确定是否相同。（通常会覆盖Object中的hashCode();和equals();方法）

注：
- 存储对象的时候，使用HashSet时，该类必须覆写hashCode();和equals();方法。
必须覆写hashCode();原因是如果是同一个对象，其hashCode一定相同，即使内容被修改不同，
则依然会被认为是同一个对象而不会被添加至集合中。而且覆写hashCode时最好依赖自身对象
进行解析，这样可以降低冲突率。
- HashSet底层是通过HashMap实现的。

【HashSet唯一性判断】

package name.liushiyao.collection.set;

/**
 * Created by 电子小孩 on 2017/3/18.
 */
public class Person {

  private String name;
  private int age;

  public Person(String name, int age) {
    this.name = name;
    this.age = age;
  }


  /**
   * 必须要覆写hashCode和equals方法 覆写hashCode时最好以对象的属性作为基数，这样可以减少冲突率
   */
  @Override
  public int hashCode() {
    return name.hashCode() + age * 10;
  }

  @Override
  public boolean equals(Object obj) {

    if (this == obj) {
      return true;
    }
    if (!(obj instanceof Person)) {

      throw new ClassCastException("类型错误");
    }

    Person person = (Person) obj;

    return this.name.equals(person.name) && this.age == person.age;
  }

  public String getName() {
    return name;
  }

  public void setName(String name) {
    this.name = name;
  }

  public int getAge() {
    return age;
  }

  public void setAge(int age) {
    this.age = age;
  }
}

/**
* HashSet的元素唯一性试验
*/
  @Test
  public void Demo2() {
    Set<Person> hashSet = new HashSet<Person>();
    hashSet.add(new Person("1", 123));
    Person person = new Person("2", 456);
    hashSet.add(person);
    hashSet.add(new Person("1", 321));
    hashSet.add(new Person("3", 456));
    for (Person person1 : hashSet) {
      System.out.println(person1.getName() + "=" + person1.getAge());
    }
  }

LinkedHashSet

可以通过LinkedHashSet();获取有序的链式哈希表。

TreeSet

如果需要对元素进行排序操作，通常使用TreeSet。

判断元素的唯一方式：根据比较方法（compareTo）返回的结果，若为0，则相同；

对元素进行排序

方式一：让类实现Comparable（自然顺序）接口，覆盖compareTo方法（让元素自身具备比较功能）。（用于类是由程序员自己编写的）

package name.liushiyao.collection.set;

/**
 * Created by 电子小孩 on 2017/3/18.
 */


/**
 * 实现Comparable，实现compareTo方法，针对性较强，但是灵活性较差
 */
public class Student implements Comparable {

  private String name;
  private int score;
  Student(String name, int score) {

    this.name = name;
    this.score = score;

  }
  public String getName() {
    return name;
  }

  public void setName(String name) {
    this.name = name;
  }

  public int getScore() {
    return score;
  }

  public void setScore(int score) {
    this.score = score;
  }

  @Override
  public int hashCode() {
    return score * 19 + name.hashCode();
  }

  @Override
  public boolean equals(Object obj) {

    if (this == obj) {
      return true;
    }
    if (!(obj instanceof Student)) {
      new ClassCastException("类型错误异常");
    }
    Student student = (Student) obj;

    return student.getName().equals(this.name) && this.score == student.getScore();
  }

  /**
   * 覆写compareTo方法
   *
   * 排序原理： >0:return 整数 <0:return 负数 =0:return 0
   */
  @Override
  public int compareTo(Object o) {

    Student person = (Student) o;
    //从小到大（因为this在前）
    int i = this.score - person.getScore();
    //如果score相同则比较name
    return i == 0 ? this.name.compareTo(person.getName()) : i;
  }

  @Override
  public String toString() {
    return "Student{" +
        "name='" + name + '\'' +
        ", score=" + score +
        '}';
  }
}

/**
   * TreeSet集合的排序(Comparable) 针对性强，但灵活性差
   */
  @Test
  public void Demo3() {
    Set<Student> students = new TreeSet<Student>();
    students.add(new Student("小明", 1));
    students.add(new Student("小红", 3));
    students.add(new Student("小刚", 2));
    for (Student student : students) {
      System.out.println(student);
    }
  }

方法二：定义一个类实现Comparator接口，覆盖compare方法，该类对象作为参数传递给TreeSet的构造函
（用于类为系统所写，可编写一个专门用于排序的类）(此方法必须在实例化TreeSet时，给予TreeSet一个Comparator参数,而方法一则不需要)

package name.liushiyao.collection.set;
import java.util.Comparator;
/**
 * Created by 电子小孩 on 2017/3/18.
 */
public class ComparatorByAge implements Comparator {
        @Override
        public int compare ( Object o1, Object o2 ) {

                Student student1 = ( Student ) o1;
                Student student2 = ( Student ) o2;
                //从大到小
                int i = student2.getScore () - student1.getScore () ;
                return i == 0? student1.getName ().compareTo ( student2.getName () ):i;

        }
}

/**
   * TreeSet集合的排序(Comparator) 单独的一个类，灵活性好，常用
   */
  public static void Demo4() {

    Set<Student> students = new TreeSet<Student>(new ComparatorByAge());
    students.add(new Student("小明", 1));
    students.add(new Student("小红", 3));
    students.add(new Student("小刚", 2));
    for (Student student : students) {
      System.out.println(student);
    }

  }

Queue

队列是一种先进先出的数据结构，元素在队列末尾添加，在队列头部删除。

常用方法
- offer()：往队列中添加一个元素
- oll()与remove()方法都是移除队列头部的元素，两者的区别在于如果队列为空，那么poll()返回的是null，而remove()会抛出一个异常。
- 方法element()与peek()主要是获取头部元素，不删除。

接口Deque，是一个扩展自Queue的双端队列，它支持在两端插入和删除元素，因为LinkedList类实现了Deque接口，所以通常我们可以使用LinkedList来创建一个队列。

Map

Map中存储的是键值对。必须要保证Map集合中的键的唯一性(不允许重复)，允许null的键和null的value，无序。

常用方法
- put();putAll();
- 查询方法，containsKey();containsValue();

Collection和Map方法中的区别
1. Collection 添加是使用add(),而Map使用的是put();
2. Collection 查询是使用contains();而Map使用的是containsKey()和containsValue();
3. Collection 中有toArrays()方法，而Map中没有

Map操作

        1.添加：
            value put(key , value);     //返回前一个与key关联的值，若没有则返回null；
                                    //存相同键，值会被替换
                                    //Map用put，Set用add
        2.删除：
            void clear();               //清除所有键值对
            value remove(Object key);  //如果存在一个键的映射关系，则将其从此映射中移除
        3.判断：
            Boolean containsKey(Object key);    //若此映射将包含指定键的映射关系，则返回true
            Boolean containsValue(Object value);//若此映射将一个或多个键的映射到指定值，则返回true
            Boolean equals(Object o);   //比较指定的对象与此映射是否相等
            Boolean isEmpty();      //若此映射未包含键-值映射关系，则返回true；
        4.获取：
            value get(Object key);          //返回指定键所映射的值，若此映射不包含该键的映射关系，则返回null；
            int size(); //获取键的个数

Map子类

• HashTable：内部结构是哈希表，同步的。不允许null作为键值对；(hash数组默认是11，增加方式是old×2+1)
• Properties：HashTable的子类，用于存储键值对型的配置文件信息，线程安全的
• HashMap：基于哈希表的Map接口的非同步实现，允许使用null值和null键，不保证映射顺序(添加的顺序)
• LinkedHashMap：
• TreeMap：内部结构是二叉树，不同步的，可以对Map的集合进行键值的排序

Map迭代

因为Map集合中不存在Interator迭代器，故不能直接用迭代器获取Map集合中的存储的元素。但可以通过Set keyset();返回此Map集合中的键的 Set 视图，然后再通过Set集合通过迭代器获取key，最后通过get();方法利用key获取Map集合中的value；

keySet

此映射中包含的键的 Set 视图（通过此方法获取Map集合中的所有的value）

/*
    通过keySet获取Map键值
   */
  public static void demo1() {
    Map<Integer, String> map = new HashMap<Integer, String>();
    map.put(1, "一");
    map.put(2, "二");
    map.put(3, "三");
    map.put(4, "四");
    /**
     * 获取键值方法一
     */
    Set<Integer> set = map.keySet();
    Iterator iterator = set.iterator();
    while (iterator.hasNext()) {
      Integer integer = (Integer) iterator.next();
      String string = map.get(integer);
      System.out.println(integer + "=" + string);
    }
}

entrySet

返回此映射中包含的映射关系的 Set视图。
public static interface Map.Entry

/**
   * 使用entrySet遍历Map
   */
  public static void demo2() {

    Map<Integer, String> map = new HashMap<Integer, String>();
    map.put(1, "一");
    map.put(2, "二");
    map.put(3, "三");
    map.put(4, "四");

    /**
     * 通过entrySet遍历方法一
     */
    /*Iterator<Map.Entry<Integer,String >> iterator = map.entrySet ().iterator ();
    while ( iterator.hasNext () ){

            Map.Entry<Integer,String >entry = iterator.next ();
            Integer integer  = entry.getKey ();
            String string  = entry.getValue ();
            System.out.println (integer+"=" + string  );


    }*/
    /**
     * 通过entrySet遍历方法二
     */
    for (Map.Entry<Integer, String> entry : map.entrySet()) {
      String string = entry.getValue();
      Integer integer = entry.getKey();
      System.out.println(integer + "=" + string);
    }
  }

values

此映射中包含的值的 collection 视图（单独获取value）

/**
   * 通过values()获取HashMap值的集合
   */
  @Test
  public void demo4(){
    HashMap<String,String>hashMap= new HashMap<String, String>();
    hashMap.put("100","liushiyao");
    hashMap.put("200","123");
    hashMap.put("300","555");
    Collection<String> collection = hashMap.values();
    for (String string :collection){
      System.out.println(string);
    }
  }

Properties

主要用于读取配置文件,存储字符串键值对。

@Test
  public void readPropertiesTest() throws IOException {

    BufferedReader bufferedReader = new BufferedReader(new FileReader("/home/liushiyao/MyCode/IDEA/JavaStudentDemo/src/main/java/name/liushiyao/collection/map/info.properties"));
    Properties properties = new Properties();
    properties.load(bufferedReader);
    System.out.println(properties.get("name"));
    System.out.println(properties.getProperty("age"));

  }

HashTable

内部结构是哈希表，同步的。不允许null作为键值对；(hash数组默认是11，增加方式是old×2+1)

HashTable和前面介绍的HashMap很类似，它也是一个散列表，存储的内容是键值对映射，不同之处在于，HashTable是继承自Dictionary的（但是也实现了Map接口），HashTable中的函数都是同步的，这意味着它也是线程安全的，另外，HashTable中key和value都不可以为null。

HashMap

基于哈希表的Map接口的非同步实现，允许使用null值和null键，不保证映射顺序(添加的顺序)

HashMap实现原理

1. HashMap的内部结构基本上是通过“数组”+“链表”来实现的，HashMap默认的大小为16

1. 不同的Key会根据Hash值映射到数组table[]的不同部分上去。

2. 如果不同的元素计算出来的hash值一样，HashMap会采用链表的结构解决

LinkedHashMap

LinkedHashMap继承自HashMap，它主要是用链表实现来扩展HashMap类，HashMap中条目是没有顺序的，但是在LinkedHashMap中元素既可以按照它们插入图的顺序排序，也可以按它们最后一次被访问的顺序排序。

TreeMap

跟TreeSet一样，主要用于排序
【对TreeMap进行排序，包括key排序和value排序】

/*
    对TreeMap的key进行排序(默认情况下，是对key进行排序的)
   */
  @Test
  public void demo5() {

    Map<Integer, String> map = new TreeMap<Integer, String>(new Comparator<Integer>() {
      @Override
      public int compare(Integer o1, Integer o2) {
        return (o1 - o2 == 0) ? 0 : o1 - o2;
      }
    });
    map.put(1, "liushiyao");
    map.put(41, "刘石尧");
    map.put(5, "123");
    map.put(10, "123213");
    for (Map.Entry<Integer, String> entry : map.entrySet()) {
      System.out.println(entry.getKey() + "   " + entry.getValue());
    }

  }

/**
   * 对TreeMap的value进行排序（使用Collection.sort()方法 ）
   */
  @Test
  public void demo6(){

    Map<Integer,String> map = new TreeMap<Integer, String>();
    map.put(123,"aaa");
    map.put(456,"刘石尧");
    map.put(678,"刘二");
    map.put(111,"刘a");
    List<Map.Entry<Integer,String>> arrayList = new ArrayList<Entry<Integer, String>>(map.entrySet());

    Collections.sort(arrayList, new Comparator<Entry<Integer, String>>() {
      @Override
      public int compare(Entry<Integer, String> o1, Entry<Integer, String> o2) {
        return o1.getValue().compareTo(o2.getValue());
      }
    });
    for (Map.Entry<Integer,String >entry :arrayList){
      System.out.println(entry.getKey()+"   "+entry.getValue());
    }

  }

其他集合类

1. ConcurrentHashMap

   并发，从名字就可以看出来ConcurrentHashMap是HashMap的线程安全版。同HashMap相比，ConcurrentHashMap不仅保证了访问的线程安全性，而且在效率上与HashTable相比，也有较大的提高。

2. CopyOnWriteArrayList

   CopyOnWriteArrayList，是一个线程安全的List接口的实现，它使用了ReentrantLock锁来保证在并发情况下提供高性能的并发读取。

HashMap和HashTable

1.继承父类不同
Hashtable继承自Dictionary类，而HashMap继承自AbstractMap类。但二者都实现了Map接口。

2.是否允许空值
HashMap可以存储null键和null值；
HashTable不能存储null键和null值；

3.线程安全问题
HashMap是非synchronized，而Hashtable是synchronized，这意味着Hashtable是线程安全的，多个线程可以共享一个Hashtable；而如果没有正确的同步的话，多个线程是不能共享HashMap的。

4.速度问题
因为HashMap是线程不安全的，所以在速度上 会比HashTable要快一些。

5.hash值不同
Hashtable计算hash值，直接用key的hashCode()，而HashMap重新计算了key的hash值，Hashtable在求hash值对应的位置索引时，用取模运算，而HashMap在求位置索引时，则用与运算

6.内部初始化及扩容方式不同
HashTable中hash数组默认大小是11，增加的方式是 old*2+1。而HashMap扩容时，将容量变为原来的2倍。

7.是否提供contains方法
Hashtable则保留了contains，containsValue和containsKey三个方法，其中contains和containsValue功能相同。

HashMap把Hashtable的contains方法去掉了，改成containsValue和containsKey，因为contains方法容易让人引起误解。