Java中级-集合框架

ArrayList

数组的长度声明即固定，存在局限性，为了解决该局限性，引入了容器

容器：其容量capacity会随着对象的增加自动增长，无须担心数组的边界问题
常用方法
- add()：增加一个元素
- contains()：判断是否存在某个元素
- get()：获取指定位置的对象
- indexOf()：获取对象所处的位置
- remove()：删除指定元素（下标或具体对象）
- set()：替换元素
- size()：获取大小
- toArray()：转换为数组
- addAll()：把另一个容器的所有对象都加进来
- clear()：清空

遍历

使用get()和size()进行指定位置的遍历

package how2j;
import java.util.ArrayList;
public class TestCollection {
    public static void main(String[] args) {
        ArrayList<String> strs = new ArrayList<>();
        strs.add("aaa");
        for (int i = 0; i < strs.size(); i++) {
            System.out.println(strs.get(i));
        }
    }
}

使用迭代器进行遍历

package how2j;

import java.util.ArrayList;
import java.util.Iterator;

public class TestCollection {
    public static void main(String[] args) {
        ArrayList<String> strs = new ArrayList<>();
        strs.add("aaa");
        Iterator<String> str = strs.iterator();
        while(str.hasNext()){
            String s = str.next();
            System.out.println(str);
        }
    }
}

使用增强型for循环进行遍历

package how2j;
import java.util.ArrayList;
public class TestCollection {
    public static void main(String[] args) {
        ArrayList<String> strs = new ArrayList<>();
        strs.add("aaa");
        for (String s : strs) {
            System.out.println(s);
        }
    }
}

LinkedList

和ArrayList一样，同样实现了List接口，也同样有add,remove,contains等方法

LinkedList实现了双向链表结构Deque（增加了前驱节点的指针），可以方便地在头尾插入数据：addFirst()、getFirst()、removeFirst() ；Last同理

package how2j;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;

public class TestCollection {
    public static void main(String[] args) {
        LinkedList<String> strs = new LinkedList<>();
        strs.addFirst("0"); //在最前面插入
        strs.addLast("9");  //在最后面插入
        System.out.println(strs.getFirst());    //查看第一个元素
        System.out.println(strs.getLast());     //查看最后一个元素
        System.out.println(strs.removeFirst());     //查看并取出第一个元素
        for (String s : strs) {
            System.out.println(s);
        }
    }
}

由于Deque继承了Queue(FIFO)，因此ArrayList也具有队列的特点（队尾加，队首取）

add()：在队尾添加元素，队列满了会抛出异常
offer()：在队尾添加元素，队列满了会返回false，因此尽量用offer来添加元素
poll()：返回并删除队列的头部元素
peek()：返回第一个元素但不取出

package how2j;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
public class TestCollection {
    public static void main(String[] args) {
        LinkedList<String> strs = new LinkedList<>();
        strs.offer("1");
        strs.offer("2");
        strs.offer("3");
        System.out.println(strs.poll());    //返回并弹出3
        System.out.println(strs.peek());    //返回2
    }
}

二叉树

排序二叉树

package how2j;
import java.util.ArrayList;
import java.util.List;
public class Node{
    Node leftNode;
    Node rightNode;
    Object value;
    public void add(Object v){
        if (value == null)  this.value = v;
        else if ((Integer) v < (Integer) value){
            if(leftNode ==null) leftNode = new Node();
            leftNode.add(v);
        }else{
            if(rightNode ==null) rightNode = new Node();
            rightNode.add(v);
        }
    }
    public List<Object> values(){
        List<Object> list = new ArrayList<Object>();
        if(leftNode != null)    list.addAll(leftNode.values());
        list.add(value);
        if(rightNode != null)   list.addAll(rightNode.values());
        return list;
    }
    public static void main(String[] args) {
        Node root = new Node();
        int[] randoms = { 67, 7, 30, 73, 10, 0, 78, 81, 10, 74 };
        for(int i: randoms){
            root.add(i);
        }
        System.out.println(root.values());
    }
}

HashMap

HashMap储存数据的方式——键值对

值可以重复，键不能重复（值以最后插入时的值为准）

package how2j;
import java.util.HashMap;

public class TestCollection {
    public static void main(String[] args) {
        HashMap<String, String> map = new HashMap<>();
        map.put("one","1");
        map.put("two","3");
        map.put("two","2"); //只会保留后面一项
        System.out.println(map.get("two"));
        map.clear();    //清空map
    }
}

HashSet

Set中的元素不能重复（重复的元素无法插入）
Set中的元素没有顺序
HashSet没有独立代码的实现，而是在里面封装了HashMap，HashSet是作为Map的key存在的

Collection

Collection是存储一个一个对象的，Map是存放键值对的，两者没有关系

Colletions

Collections是容器的工具类，如同Arrays是数组的工具类
常用方法
- reverse：反转
- shuffle：混淆
- sort：排序
- swap：交换
- rotate：滚动
- synchronizedList：线程安全化

集合间关系和区别

ArrayList和HashSet

顺序性：ArrayList有顺序，HashSet无顺序（不同条件下，元素的顺序有可能不一样）
重复性：ArrayList可以重复，HashSet不可以重复（判断hashcode和equals）

HashMap和Hashtable

HashMap可以存放Null，Hashtable不能存放Null
HashMap不是线程安全的类，Hashtable是线程安全的类

hashcode原理

所有的对象都有一个对应的hashcode（散列值）
给定一个长度固定的数组，并设定hashcode，使一个对象经过计算后随机散落在数组里
查找数据时只要根据下标（哈希值）进行查找，效率很高
是一种以空间换时间的思想

比较器

使用Comparator并重写compare方法

使类继承Comparable接口并重写compareTo()方法，即可直接使用Collections.sort()进行排序

package how2j;
import java.util.*;

public class TestCollection {
    public static void main(String[] args) {
        Random r = new Random();
        List<Hero> heros = new ArrayList<Hero>();
        for (int i = 0; i < 10; i++) {
            Hero hero = new Hero("hero"+i,r.nextInt(1000));
            heros.add(hero);
        }
        Collections.sort(heros);
        System.out.println(heros);
    }
}

class Hero implements Comparable<Hero>{
    String name;
    Integer age;
    Hero(String name, Integer age){
        this.name = name;
        this.age = age;
    }

    public int compareTo(Hero o1){
        if(this.age > o1.age) return 1;
        else return -1;
    }

    public String toString() {
        return new String("hero:"+name+";"+"age:"+age);
    }

}