liujijiang

java学习笔记 --17-- 容器深入研究

2020.04.03

填充

public static void main(String [] args) throws NoSuchFieldException, IllegalAccessException {
        List<Test2> list = new ArrayList<>(Collections.nCopies(10,new Test2()));

        System.out.println(list);

        Collections.fill(list,new Test2());

        System.out.println(list);

    }

List容器创建时可以使用Collections.nCopies初始化容器,并且只能初始化为相同的元素
fill方法只能替换元素,不能添加元素

Set

  • Set(interface):元素唯一,元素必须定义equals方法,不保证元素的次序
  • HashSet:为快速查找设计的Set,元素必须定义hashCode方法
  • TreeSet:保证顺序,底层为树结构,元素必须实现Comparable
  • LinkedHashSet:有HashSet的查询速度,用LinkedList维护插入的次序

没有特殊需求,用HashSet就够了

良好的编程风格:覆盖equals和hashCode方法

package com.company;
import java.util.*;
/**
 * @ClassName Test
 * @Description
 * @Auther liuxiansen
 * @Date 2020/3/29 8:55 上午
 **/
public class Test{
    public static void main(String [] args) throws NoSuchFieldException, IllegalAccessException {
        Random random = new Random(10);
        Set<Test2> hashSet = new HashSet<>();
        Set<Test2> treeSet = new TreeSet<>();
        Set<Test2> linkedHashSet = new LinkedHashSet<>();

        for(int i=0;i<10;i++){
            hashSet.add(new Test2(random.nextInt(10)));
            treeSet.add(new Test2(random.nextInt(10)));
            linkedHashSet.add(new Test2(random.nextInt(10)));
        }

        System.out.println(hashSet);
        System.out.println(treeSet);
        System.out.println(linkedHashSet);

    }

}
class Test2 implements Comparable<Test2>{
    private int a;

    public Test2(int a){
        this.a = a;
    }

    public void print(){
        System.out.println("a: " + a);
    }

    @Override
    public int compareTo(Test2 o) {
        return this.a - o.a > 0 ? 1 : (this.a == o.a ? 0 : -1);
    }

    @Override
    public boolean equals(Object obj) {
        return obj instanceof Test2 && this.a == ((Test2)obj).a;
    }
    
    public int hashCode(){
        return a;
    }

    public String toString(){
        return "a: " + a;
    }
}

结果:[a: 0, a: 1, a: 3, a: 4, a: 5, a: 7, a: 9]
[a: 0, a: 3, a: 5, a: 6, a: 8, a: 9]
[a: 3, a: 6, a: 1, a: 9, a: 5, a: 8, a: 4, a: 0]
HashSet:按照。。。顺序排序
TreeSet:按照compareTo的方式进行排序
LinkedHashSet:按照插入的顺序进行排序
实现compareTo的时候不能使用this.a-o.a,因为java中int是有符号的,如果一个非常大的整数减去负数就会溢出返回负值

Queue

Queue的两个实现:

  • Linkedlist:入队顺序出队
  • PriorityQueue:优先级出队
    区别:排序的方式不同,性能差异不大
package com.company;
import java.util.*;
/**
 * @ClassName Test
 * @Description
 * @Auther liuxiansen
 * @Date 2020/3/29 8:55 上午
 **/
public class Test{
    public static void main(String [] args) throws NoSuchFieldException, IllegalAccessException {
        Random random = new Random(10);
        Queue<Test2> queue = new PriorityQueue<>();

        for(int i=0;i<10;i++){
            queue.add(new Test2(random.nextInt(10)));
        }

        for (int i=0;i<10;i++){
            System.out.println(queue.poll());
        }
    }

}
class Test2 implements Comparable<Test2>{
    private int a;

    public Test2(int a){
        this.a = a;
    }

    public void print(){
        System.out.println("a: " + a);
    }

    @Override
    public int compareTo(Test2 o) {
        return this.a - o.a > 0 ? 1 : (this.a == o.a ? 0 : -1);
    }

    @Override
    public boolean equals(Object obj) {
        return obj instanceof Test2 && this.a == ((Test2)obj).a;
    }

    public int hashCode(){
        return a;
    }

    public String toString(){
        return "a: " + a;
    }
}

有限队列的出队顺序是CompareTo的顺序

Map

Map接口的多种实现:

  • HashMap:基于散列表的实现,插入和查询的开销是固定的,可以通过构造器设置容量和负载因子调整容器性能
  • TreeMap:基于红黑树的实现,查看键值对时会按照顺序查看(Comparable的顺序),唯一一个有subMap方法的Map,返回一个子树
  • LinkedHashMap:键值对的顺序是插入的顺序,比HashMap慢一点,但在迭代查找时更快,使用LinkedList维护内部次序
  • WeakHashMap:弱键映射,如果键没有引用指向,键会被自动回收
  • ConcurrentHashMap:线程安全的Map
  • IdentityHashMap:使用==代替equals的Map

Map要求:任何键有equals方法,如果用于散列Map要有hashCode方法,TreeMap要实现Comparable

SortedMap

public static void main(String [] args) throws NoSuchFieldException, IllegalAccessException {
        Random random = new Random(10);
        SortedMap<String , String> map = new TreeMap<>();
        map.put("jjboy","nb");
        map.put("redarm","nb");
        System.out.println(map.comparator());
        System.out.println(map.entrySet());
        System.out.println(map.firstKey());
        System.out.println(map.lastKey());
        System.out.println(map.keySet());
        System.out.println(map.values());
        System.out.println(map.subMap("jjboy","redarm"));
    }

TreeMap是SortedMap的唯一实现

散列与散列码

HashMap使用元素的hashCode当做键,默认是对象的地址的hashCode
可以覆盖hashCode方法,同时必须也覆盖equals方法

package com.company;
import java.util.*;
/**
 * @ClassName Test
 * @Description
 * @Auther liuxiansen
 * @Date 2020/3/29 8:55 上午
 **/
public class Test{
    public static void main(String [] args) throws NoSuchFieldException, IllegalAccessException {
        Map<Test1,String> map = new HashMap<>();
        Random random = new Random(1);
        for(int i=0;i<10;i++){
            map.put(new Test1(random.nextInt(10)),UUID.randomUUID().toString());
        }

        Iterator<Test1> iterator = map.keySet().iterator();

        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }
    }

}
class Test1{
    private int a;

    public Test1(int a){
        this.a = a;
    }

    @Override
    public int hashCode() {
        return super.hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        return obj instanceof Test1 && this.a == ((Test1)obj).a;
    }

    public int getA() {
        return a;
    }

    public void setA(int a) {
        this.a = a;
    }
}


保存的键的信息就是hashCode

为速度而散列

HashMap:键的hashCode作为数组的下标,数组的元素是list,list中存的是值,不同键的hashCode可能相同,所以同一个键的list中的值可能是多个,散列函数越好,list中的值就可能是一个,查询速度就越快

hashCode:同一个对象的hashCode必须相同

容器选择

List

  • ArrayList:因为底层是数组,所以即使数据越来越多,查询速度也不会变慢很多,但是如果数据很多,插入和删除就变得越来越慢
  • LinkedList:底层是双向链表,插入和删除的时间是变化不大的,虽然在插入和删除的时候需要查询,但是和ArrayList的插入删除数据的时间相比,仍然是可以忽略的,但是查询的速度是比ArrayList慢的

Set

  • HashSet:HashSet的性能几乎总是比TreeSet好的,特别是在添加和删除元素的时候,TreeSet存在的唯一原因可能就是因为他可以维持元素的排序状态
  • TreeSet的迭代比HashSet快
  • LinkedHashSet的插入比HashSet慢

Map

  • HashMap:插入的代价随着元素的增加变得越来越大,但是查找的代价比较小
  • HashMap是用来代替HashTable的
  • TreeMap通常比HashMap慢
  • 第一选择HashMap,对元素顺序有要求才选TreeMap
  • LinkedHashMap插入慢一点,但是迭代快

HashMap性能因子

  • 容量:表中桶位数
  • 初始容量:初始桶位数,HashMap和HashSet的构造器支持自定义初始容量
  • 尺寸:当前存储的元素的个数
  • 负载因子:尺寸/容量,负载轻冲突的可能性就笑,构造器运行自定义负载因子,当超过负载因子时容器桶位大致加倍,对象重新分配到桶位中(再散列)
  • HashMap默认的负载因子是0.75,这个数在时间和空间中大致达到了平衡,再大可能空间小了,但是时间就多了,时间影响了容器的主要操作

Collection静态方法

  • max
  • min
  • indexOfSubList(List list1,List list2):返回list1在list2中第一次出现的位置,没有返回-1
  • lastIndexOfSubList(List list1,List list2):返回最后一次出现的位置
  • replaceAll(List , old, new):list中所有的old用new代替
  • reverse(List):逆向list顺序
  • rotate(list,distance):将list中所有的元素向后移动distance个位置,然后溢出的元素到前面去
  • shuffle(list):随机list中元素的顺序
  • sort(list,comparator):可以自定义排序规则排序
  • copy(list1,list2):将list2中的元素copy到list1中
  • swap(list,i,j):将list中i位置的元素和j位置的元素位置互换
  • fill(list,x):list填充相同的x
  • disjoint(col1,col2):连个集合没有相同元素时返回true
  • frequency(col,x):返回集合中等于x的元素个数

快速报错

java不允许多个进程对一个容器同时操作,但一个进程在迭代一个容器时,另一个容器对这个容器进行操作,java会立马报错

public static void main(String [] args) throws NoSuchFieldException, IllegalAccessException {
        List<String> list = new ArrayList<>();
        list.add("jjboy");
        ListIterator<String > iterator = list.listIterator();
        try {
            list.add("jj");
            String ss = iterator.next();

        } catch (ConcurrentModificationException e){
            System.out.println(e);
        }
    }

在进行迭代的时候对容器进行插入操作

持有引用

如果有引用指向对象,那么这个对象就是有用的,垃圾回收器就不能回收他
如果没有引用指向对象,那么你的系统就不会用到这个对象,这是垃圾回收器回收就是安全的
java.lang.ref包含一组类给垃圾回收器增加了灵活性
接口Reference有三个实现(由强到弱排序):

  • SoftReference
  • WeakReference
  • PhantomReference

如果你希望一个引用一直指向一个对象,但是在内存快耗尽的时候垃圾回收器还能回收他,就可以使用Reference
让Reference在对象和普通引用之间成为媒介并且没有其他的引用直接指向对象就可以达到这个目的