集合类

集合类

Android小彩虹2021-08-25 17:54:43320A+A-

[TOC]

java 提供三种集合:

List:一种有序列表的集 Set:一种保证没有重复元素的集合 Map:一种通过键值(key-value)查找的映射表集合

Java访问集合总是通过统一的方式——迭代器(Iterator)来实现, 它最明显的好处在于无需知道集合内部元素是按什么方式存储的。 典型的用法如下:  

   Iterator it = collection.iterator(); //获得一个迭代子
                while(it.hasNext()) {

        Objectobj it= it.next(); //得到下一个元素
        } 

一.List

List有两种: 一种是基本的ArrayList其优点在于随机访问元素,另一种是更强大的LinkedList它并不是为快速随机访问设计的。 实现List接口的常用类有LinkedList,ArrayList,Vector和Stack

LinkedList类:

LinkedList实现了List接口,允许null元素。对顺序访问进行了优化,向List中间插入与删除的开销并不大,随机访问则相对较慢。还具有下列方法:addFirst(),addLast(),getFirst(),getLast(),removeFirst()和removeLast()这些方法(没有在任何接口或基类中定义过),这些操作使LinkedList可被用作堆栈(stack),队列(queue)或双向队列(deque)。

注意:LinkedList没有同步方法。如果多个线程同时访问一个List,则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List:List list = Collections.synchronizedList(newLinkedList(...));

ArrayList类:

和LinkedList一样,ArrayList也是非同步的(unsynchronized)。

import java.util.*;
 
public class Test{
 public static void main(String[] args) {
     List<String> list=new ArrayList<String>();
     list.add("Hello");
     list.add("World");
     list.add("HAHAHAHA");
     //第一种遍历方法使用 For-Each 遍历 List
     for (String str : list) {            //也可以改写 for(int i=0;i<list.size();i++) 这种形式
        System.out.println(str);
     }
 
     //第二种遍历,把链表变为数组相关的内容进行遍历
     String[] strArray=new String[list.size()];
     list.toArray(strArray);
     for(int i=0;i<strArray.length;i++) //这里也可以改写为  for(String str:strArray) 这种形式
     {
        System.out.println(strArray[i]);
     }
     
    //第三种遍历 使用迭代器进行相关遍历
     
     Iterator<String> ite=list.iterator();
     while(ite.hasNext())//判断下一个元素之后有值
     {
         System.out.println(ite.next());
     }
 }
}
Vector类:

Vector非常类似ArrayList,但是Vector是同步的。由Vector创建的Iterator,虽然和 ArrayList创建的Iterator是同一接口,但是,因为Vector是同步的,当一个Iterator被创建而且正在被使用,另一个线程改变了Vector的状态(例如,添加或删除了一些元素),这时调用Iterator的方法时将抛出ConcurrentModificationException,因此必须捕获该异常。

Stack类

Stack继承自Vector,实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。基本的push和 pop方法,还有peek方法得到栈顶的元素,empty方法测试堆栈是否为空,search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。

List转化成数组

Integer[] array = list.toArray(new Integer[list.size()]); Integer[] array = list.toArray(Integer[]::new);

数组转化成List

可以使用Arrays.asList(T...)方法把数组转换成List。

List对象的比较

List内部并不是通过==判断两个元素是否相等,而是使用equals()方法判断两个元素是否相等。

在List中查找元素时,List的实现类通过元素的equals()方法比较两个元素是否相等,因此,放入的元素必须正确覆写equals()方法,Java标准库提供的String、Integer等已经覆写了equals()方法;

编写equals()方法可借助Objects.equals()判断。

如果不在List中查找元素,就不必覆写equals()方法

public class ListCompare {
    @Test
    public void test() {
        List<Person> list = Arrays.asList(
                new Person("Xiao", "Ming", 18),
                new Person("Xiao", "Hong", 25),
                new Person("Bob", "Smith", 20)
        );
        boolean exist = list.contains(new Person("Bob", "Smith", 20));
        System.out.println(exist ? "测试成功!" : "测试失败!");
    }


    class Person {
        String firstName;
        String lastName;
        int age;

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

        public boolean equals(Object o) {
            if (o instanceof Person) {
                Person p = (Person) o;
                return this.age == p.age && Objects.equals(this.firstName, p.firstName) && Objects.equals(this.lastName, p.lastName);
            }
            return false;
        }
    }
}

二、Map接口

请注意,Map没有继承Collection接口,Map提供key到value的映射。一个Map中不能包含相同的key,每个key只能映射一个value。Map接口提供3种集合的视图,Map的内容可以被当作一组key集合,一组value集合,或者一组key-value映射。

        方法put(Object key, Object value)添加一个"值"(想要得东西)和与"值"相关的"键"(key)(使用它来查找)。方法get(Object key)返回与给定"键"相关联的"值"。可以用containsKey()和containsValue()测试Map中是否包含某个"键"或"值"。

HashTable类

Hashtable继承Map接口,实现一个key-value映射的哈希表。任何非空(non-null)的对象都可作为key或者value。Hashtable是同步的,线程安全。 添加数据使用put(key, value),取出数据使用get(key),这两个基本操作使用Java的hashCode来实现,时间开销为常数。

由于作为key的对象将通过计算其散列函数来确定与之对应的value的位置,因此任何作为key的对象都必须实现hashCode和equals方法。hashCode和equals方法继承自根类Object,如果你用自定义的类当作key的话,要相当小心,按照散列函数的定义,           如果两个对象相同,即obj1.equals(obj2)=true,则它们的hashCode必须相同,但如果两个对象不同,则它们的hashCode不一定不同,如果两个不同对象的hashCode相同,这种现象称为冲突,冲突会导致操作哈希表的时间开销增大,所以尽量定义好的hashCode()方法,能加快哈希表的操作。

  如果相同的对象有不同的hashCode,对哈希表的操作会出现意想不到的结果(期待的get方法返回null),要避免这种问题,只需要牢记一条:要同时复写equals方法和hashCode方法,而不要只写其中一个。

public class MapCompare {
    @Test
    public void test() {
        Map<Person, String> map = new HashMap<>();
        map.put(new Person("xiao", "Ming", 18), "nice");
        map.put(new Person("xiao", "hong", 20), "hong");

        System.out.println("get:"+map.get(new Person("xiao", "hong", 20)));
    }


    class Person {
        String firstName;
        String lastName;
        int age;

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

        @Override
        public boolean equals(Object o) {
            if (o instanceof Person) {
                Person p = (Person) o;
                return this.age == p.age && Objects.equals(this.firstName, p.firstName) && Objects.equals(this.lastName, p.lastName);
            }
            return false;
        }

        @Override
        public int hashCode() {
            return Objects.hash(firstName, lastName, age);
        }
    }
}
HashMap类

        HashMap和Hashtable类似,不同之处在于HashMap是非同步的,并且允许null,即null value和null key但是将HashMap视为Collection时(values()方法可返回Collection),其迭代子操作时间开销和HashMap的容量成比例。因此,如果迭代操作的性能相当重要的话,不要将HashMap的初始化容量设得过高,或者load factor过低。

import java.util.*;
 
public class Test{
     public static void main(String[] args) {
      Map<String, String> map = new HashMap<String, String>();
      map.put("1", "value1");
      map.put("2", "value2");
      map.put("3", "value3");
      
      //第一种:普遍使用,二次取值
      System.out.println("通过Map.keySet遍历key和value:");
      for (String key : map.keySet()) {
       System.out.println("key= "+ key + " and value= " + map.get(key));
      }
      
      //第二种
      System.out.println("通过Map.entrySet使用iterator遍历key和value:");
      Iterator<Map.Entry<String, String>> it = map.entrySet().iterator();
      while (it.hasNext()) {
       Map.Entry<String, String> entry = it.next();
       System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
      }
      
      //第三种:推荐,尤其是容量大时
      System.out.println("通过Map.entrySet遍历key和value");
      for (Map.Entry<String, String> entry : map.entrySet()) {
       System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
      }
    
      //第四种
      System.out.println("通过Map.values()遍历所有的value,但不能遍历key");
      for (String v : map.values()) {
       System.out.println("value= " + v);
      }
     }
}

如果作为key的对象是enum类型,那么,还可以使用Java集合库提供的一种EnumMap,它在内部以一个非常紧凑的数组存储value,并且根据enum类型的key直接定位到内部数组的索引,并不需要计算hashCode(),不但效率最高,而且没有额外的空间浪费。

我们以DayOfWeek这个枚举类型为例,为它做一个“翻译”功能:

public class Main {
    public static void main(String[] args) {
        Map<DayOfWeek, String> map = new EnumMap<>(DayOfWeek.class);
        map.put(DayOfWeek.MONDAY, "星期一");
        map.put(DayOfWeek.TUESDAY, "星期二");
        map.put(DayOfWeek.WEDNESDAY, "星期三");
        map.put(DayOfWeek.THURSDAY, "星期四");
        map.put(DayOfWeek.FRIDAY, "星期五");
        map.put(DayOfWeek.SATURDAY, "星期六");
        map.put(DayOfWeek.SUNDAY, "星期日");
        System.out.println(map);
        System.out.println(map.get(DayOfWeek.MONDAY));
    }
}
TreeMap类

        基于红黑树数据结果的实现。查看"键"或"键值对"时,它们会被排序(次序由Comparabel或Comparator决定)。TreeMap的特点在于,你得到的结果是经过排序的。TreeMap是唯一的带有subMap()方法的Map,它可以返回一个子树。

SortedMap在遍历时严格按照Key的顺序遍历,最常用的实现类是TreeMap; 作为SortedMap的Key必须实现Comparable接口,或者传入Comparator; 要严格按照compare()规范实现比较逻辑,否则,TreeMap将不能正常工作。

public class TreeMapTest {
    @Test
    public void test() {
//        Map<Student, Integer> map = new TreeMap<>(new Comparator<Student>() {
//            public int compare(Student p1, Student p2) {
////                if (p1.score == p2.score) {
////                    return 0;
////                }
////                return p1.score > p2.score ? -1 : 1;
//                return -Integer.compare(p1.score, p2.score);
//            }
//        });
        Map<Student, Integer> map = new TreeMap<>();

        map.put(new Student("Tom", 77), 1);
        map.put(new Student("Bob", 66), 2);
        map.put(new Student("Lily", 99), 3);
        for (Student key : map.keySet()) {
            System.out.println(key);
        }
        System.out.println(map.get(new Student("Bob", 66))); // null?
    }

    static class Student implements Comparable {
        public String name;
        public int score;

        Student(String name, int score) {
            this.name = name;
            this.score = score;
        }

        public String toString() {
            return String.format("{%s: score=%d}", name, score);
        }

        @Override
        public int compareTo(Object o) {
            Student student = (Student) o;
            return -Integer.compare(this.score, student.score);
        }
    }
}

WeakHashMap类

WeakHashMap是一种改进的HashMap,它对key实行“弱引用”,如果一个key不再被外部所引用,那么该key可以被GC回收。

三、Set接口

        Set是一种不包含重复的元素的Collection,即任意的两个元素e1和e2都有e1.equals(e2) = false,因此Set最多有一个null元素。

        很明显,Set的构造函数有一个约束条件,传入的Collection参数不能包含重复的元素。

        请注意:必须小心操作可变对象(Mutable Object)。如果一个Set中的可变元素改变了自身状态导致Object.equals(Object)=true将导致一些问题。

public class Main {
    public static void main(String[] args) {
        Set<String> set = new HashSet<>();
        set.add("apple");
        set.add("banana");
        set.add("pear");
        set.add("orange");
        for (String s : set) {
            System.out.println(s);
        }
    }
}

banana
orange
apple
pear
HashSet类:

HashSet是基于HashMap实现的,HashSet底层采用HashMap来保存所有元素。为快速查找设计的Set。存入HashSet的对象必须定义hashCode()。hashCode和equal()是HashMap用的,因为无需排序所以只需要关注定位和唯一性即可。hashCode用来计算hash值,hash值是用来确定hash表索引,hash表中的一个索引存放的是一张链表,所以还要通过equal方法循环比较链上的每一个对象才可以真正定位到键值对应的Entry。

        put时,如果hash表中没定定位到,就在链表前加一个Entry,如果定位到了,则更换Entry中的value(值)并返回旧value(值)。

        覆写key的hashCode()和equal()时一定要注意,不要把它们和可变属性关联上,否则属性变了之后hashCode会变,equal也会为false,这样在Map中就找不到它了而且这样的对象因为找不到它所以得不到释放,这样就变成了一个无效引用(相当于内存泄漏)。

LinkedHashSet类

HashSet类的子类,具有HashSet的查询速度,且内部使用链表维护元素的顺序(插入的次序)。于是在使用迭代器遍历Set时,结果会按元素插入的次序显示。

TreeSet类

TreeSet是依靠TreeMap来实现的,TreeSet集合类是一个有序集合,它的元素按照升序排序,默认是自然顺序排列,也就是说,TreeSet中的对象元素需要实现Comparable接口。TreeSet与HashSet类一样没有get()方法来获取列表中的元素,所以也只能通过迭代器方法来获取。

由于TreeMap需要排序,所以需要一个Comparable为键值进行大小比较,当然也是用Comparator定位的,Comparator可以在创建TreeMap时指定,这时排序时使用Comparator.compare,如果创建时没有指定Comparator那么就会使用key.compareTo()方法,这就要求key必须实现Comparable接口。

TreeMap是使用Tree数据结构实现的,所以使用compare接口就可以完成定位了。

/**
 * 在聊天软件中,发送方发送消息时,遇到网络超时后就会自动重发,因此,接收方可能会收到重复的消息,在显示给用户看的时候,需要首先去重。请练习使用Set去除重复的消息:
* */
public class TreeSetText {
    @Test
    public void test() {
        List<Message> received = Arrays.asList(
                new Message(1, "Hello!"),
                new Message(2, "发工资了吗?"),
                new Message(2, "发工资了吗?"),
                new Message(3, "去哪吃饭?"),
                new Message(3, "去哪吃饭?"),
                new Message(4, "Bye")
        );
        List<Message> displayMessages = process(received);
        for (Message message : displayMessages) {
            System.out.println(message.text);
        }
    }

    static List<Message> process(List<Message> received) {
        Set messageSet = new TreeSet<>(new Comparator<Message>() {
            @Override
            public int compare(Message o1, Message o2) {
                return Integer.compare(o1.sequence, o2.sequence);
            }
        });

        messageSet.addAll(received);
        return new ArrayList<>(messageSet);
    }

    static class Message {
        public final int sequence;
        public final String text;

        public Message(int sequence, String text) {
            this.sequence = sequence;
            this.text = text;
        }
    }
}

Queue接口

 Queue接口与List、Set同一级别,都是继承了Collection接口。LinkedList实现了Queue接口。Queue接口窄化了对LinkedList的方法的访问权限(即在方法中的参数类型如果是Queue时,就完全只能访问Queue接口所定义的方法了,而不能直接访问 LinkedList的非Queue的方法),以使得只有恰当的方法才可以使用。要避免把null添加到队列。

方法 说明 备注
add 增加一个元素 队列已满,抛出IIIegaISlabEepeplian
remove 移除并返回队列头部元素 队列为空,抛出oSuchElementException
element 返回队列头部的元素 队列为空,抛出NoSuchElementException
offer 添加一个元素并返回true 如果队列已满,则返回false
poll 移除并返问队列头部元素 如果队列为空,则返回null
peek 返回队列头部的元素 如果队列为空,则返回null
put 添加一个元素 如果队列满,则阻塞
take 移除并返回队列头部元素 如果队列为空,则阻塞

remove、element、offer、poll、peek其实是属于Queue接口。

注意:Queue队列是不能直接实例化的。原先在java编程中,Queue的实现都是用LinkedList。如:Queue qe = new LinkedList();

LinkedList即实现了List接口,又实现了Queue接口,但是,在使用的时候,如果我们把它当作List,就获取List的引用,如果我们把它当作Queue,就获取Queue的引用,始终按照面向抽象编程的原则编写代码,可以大大提高代码的质量。

// 这是一个List:
List<String> list = new LinkedList<>();
// 这是一个Queue:
Queue<String> queue = new LinkedList<>();

注意:此实现不是同步的。如果多个线程同时访问一个链接列表,而其中至少一个线程结构上修改了该列表,则它必须保证外部同步。(结构修改指添加或删除一个或多个元素的任何操作;仅设置元素的值不是结构修改)。这一般通过对自然封装该列表的对象进行同步操作来完成。

Deque 如果把条件放松一下,允许两头都进,两头都出,这种队列叫双端队列(Double Ended Queue),学名Deque。

Java集合提供了接口Deque来实现一个双端队列,它的功能是:

  • 将元素添加到队尾或队首:addLast()/offerLast()/addFirst()/offerFirst();
  • 从队首/队尾获取元素并删除:removeFirst()/pollFirst()/removeLast()/pollLast();
  • 从队首/队尾获取元素但不删除:getFirst()/peekFirst()/getLast()/peekLast();
  • 总是调用xxxFirst()/xxxLast()以便与Queue的方法区分开;
  • 避免把null添加到队列。
public class Main {
    public static void main(String[] args) {
        Deque<String> deque = new LinkedList<>();
        deque.offerLast("A"); // A
        deque.offerLast("B"); // A <- B
        deque.offerFirst("C"); // C <- A <- B
        System.out.println(deque.pollFirst()); // C, 剩下A <- B
        System.out.println(deque.pollLast()); // B, 剩下A
        System.out.println(deque.pollFirst()); // A
        System.out.println(deque.pollFirst()); // null
    }
}
Stack

在Java中,我们用Deque可以实现Stack的功能:

  • 把元素压栈:push(E)/addFirst(E);
  • 把栈顶的元素“弹出”:pop()/removeFirst();
  • 取栈顶元素但不弹出:peek()/peekFirst()。

当我们把Deque作为Stack使用时,注意只调用push()/pop()/peek()方法,不要调用addFirst()/removeFirst()/peekFirst()方法,这样代码更加清晰。

ArrayBlockingQueue类

一个由数组支持的有界队列。基于数组的阻塞循环队列,先进先出原则对元素进行排序。

LinkedBlockingQueue类

一个由链接节点支持的可选有界队列。基于链表的队列,先进先出排序元素。

PriorityBlockingQueue类

一个由优先级堆支持的无界优先级队列。PriorityBlockingQueue是对PriorityQueue的再次包装,是基于堆数据结构的,而PriorityQueue是没有容量限制的,与ArrayList一样,所以在优先阻塞队列上put时是不会受阻的。但是由于资源被耗尽,所以试图执行添加操作可能会导致OutOfMemoryError),但是如果队列为空,那么取元素的操作take就会阻塞,所以它的检索操作take是受阻的。另外,往入该队列中的元素要具有比较能力。

DelayQueue

一个由优先级堆支持的、基于时间的调度队列。(基于PriorityQueue来实现的)是一个存放Delayed元素的无界阻塞队列,只有在延迟期满时才能从中提取元素。该队列的头部是延迟期满后保存时间最长的Delayed元素。如果延迟都还没有期满,则队列没有头部,并且poll将返回null。当一个元素的getDelay(TimeUnit.NANOSECONDS)方法返回一个小于或等于零的值时,则出现期满,poll就以移除这个元素了。此队列不允许使用null元素。

SynchronousQueue

一个利用BlockingQueue接口的简单聚集(rendezvous)机制。SynchronousQueue 类是最简单的。它没有内部容量。它就像线程之间的手递手机制。在队列中加入一个元素的生产者会等待另一个线程的消费者。当这个消费者出现时,这个元素就直接在消费者和生产者之间传递,永远不会加入到阻塞队列中。

总结

Java中的List/Set和Map的区别?

List和数组类似,可以动态增长,根据实际存储的数据的长度自动增长List的长度。查找元素效率高,插入删除效率低,因为会引起其他元素位置改变 <实现类有ArrayList,LinkedList,Vector> 。

Set 接口实例存储的是无序的,不重复的数据。List 接口实例存储的是有序的,可以重复的元素。Set检索效率低下,删除和插入效率高,插入和删除不会引起元素位置改变 <实现类有HashSet,TreeSet>。

Map同样对每个元素保存一份,但这是基于"键"(key)的,Map也有内置的排序,因而不关心元素添加的顺序。如果添加元素的顺序对程序设计很重要,应该使用LinkedHashSet或者LinkedHashMap。

如何选用集合类?

1.要求线程安全,使用Vector、Hashtable

2.不要求线程安全,使用ArrayList, LinkedList, HashMap

3.要求key和value键值,则使用HashMap, Hashtable

4.数据量很大,又要线程安全,则使用Vector

如果涉及到堆栈,队列等操作,应该考虑用List,对于需要快速插入,删除元素,应该使用LinkedList,如果需要快速随机访问元素,应该使用ArrayList。

如果程序在单线程环境中,或者访问仅仅在一个线程中进行,考虑非同步的类,其效率较高,如果多个线程可能同时操作一个类,应该使用同步的类。

要特别注意对哈希表的操作,作为key的对象要正确复写equals和hashCode方法。

尽量返回接口而非实际的类型,如返回List而非ArrayList,这样如果以后需要将ArrayList换成LinkedList时,客户端代码不用改变。这就是针对抽象编程。

数据结构与算法的解度处理 (数组,链表,栈树,树,图)

数据量千级以内可以使用 Sparse 数组 (Key为整数),ArrayMap (Key 为对象) 虽然性能不如 HashMap ,但节约内存。 ArrayMap采用的是数组+数组的形式,一个数组存储key的hash值,一个数组存储value,所以如果数据较大时,效率相对较低; HashMap采用的是数组+链表/红黑树的形式,数组存放key的hash值,链表存放值,如果值数量超过8,会转成红黑树.

为什么推荐用SparseArray代替HashMap?

SparseArray三大特点 双数组、删除O(1)、二分查找 为什么省内存? HashMap 为了避免过多的哈希冲突,引入了负载因子,打个比方,负载因子使用默认值 0.75,这意味着容量达到了 75%,就会开始扩容,也就是必然有 25% 的空间是不存储数据而被浪费的。而 SparseArray 可以把数组利用到最后一个空间。 复杂度为什么这么低? SparseArray 做了两个优化: 1.引入 DELETE 标记 既然底层使用了数组,数组的缺点是什么?—— 删除数据时需要搬移元素。SparseArray 对数组的删除不做数据搬移,引入 DELETE 标记,以此达到在删除时做到 O(1) 的时间复杂度。 在调用 size()和put()需要扩容时,才去清理 DELETE 标识。 2.优化追加元素 SparseArray 提供了一个 append() 方法,来优化追加的情况。该方法会判断追加的 key 值,是否大于数组中最大的值,如果是则直接追加在数组末尾,否则执行 put() 方法插入 mKey 数组。

因为sparseArray避免了对key的自动装箱(int转成integer),它的内部是采用2个数组来实现的;一个存储key 一个存储value;相对来说,性能更快,内部采用压缩方式节省内存空间;sparseArray代替HashMap的时候最好存储的数量在千量级以下。key必须是int类型,才可以替代hashmap

SparseArray 遍历 方法1. 可以得到key值:

     SparseArray<UserBean> mUserArray = new SparseArray<>();
         //SparseArrayr容器的遍历方法1
        for (int i = 0; i < mUserArray.size(); i++) {
            int key = mUserArray.keyAt(i);
            UserBean user = mUserArray.get(key);
            Log.e("key = " + key, user.toString());
        }

方法2. 不需要key值:

     SparseArray<UserBean> mUserArray = new SparseArray<>();
         //SparseArrayr容器的遍历方法2
        for (int i = 0; i < mUserArray.size(); i++) {
            UserBean user = mUserArray.valueAt(i);
            Log.e("没有key值", user.toString());
        }

SparseArray中有一些和HashMap中相似的实用方法,比如:

put(int key, E value)
get(int key)
get(int key, E valueIfKeyNotFound)
delete(int key)
removeAt(int index)
keyAt(int index)
valueAt(int index)
等等。

android又给封装了SparseIntArray,SparseBooleanArray,SparseLongArray等等,使用方法和SparseArray都大同小异,只要你会使用Map,那么你就会使用SparseArray。

ArrayMap

ArrayMap是一个<key,value>映射的数据结构,它设计上更多的是考虑内存的优化,内部是使用两个数组进行数据存储,一个数组记录key的hash值,另外一个数组记录Value值,它和SparseArray一样,也会对key使用二分法进行从小到大排序,在添加、删除、查找数据的时候都是先使用二分查找法得到相应的index,然后通过index来进行添加、查找、删除等操作,所以,应用场景和SparseArray的一样,如果在数据量比较大的情况下,那么它的性能将退化至少50%。

添加数据: public V put(K key, V value) 获取数据: public V get(Object key) 删除数据: public V remove(Object key) 特有方法 它和SparseArray一样同样也有两个更方便的获取数据方法:

public K keyAt(int index) public V valueAt(int index)

总结: SparseArray和ArrayMap都差不多,使用哪个呢? 假设数据量都在千级以内的情况下:

1、如果key的类型已经确定为int类型,那么使用SparseArray,因为它避免了自动装箱的过程,如果key为long类型,它还提供了一个LongSparseArray来确保key为long类型时的使用

2、如果key类型为其它的类型,则使用ArrayMap

CopyOnWriteArrayList:

CopyOnWrite容器即写时复制的容器。通俗的理解是当我们往一个容器添加元素的时候,不直接往当前容器添加,而是先将当前容器进行Copy,复制出一个新的容器,然后新的容器里添加元素,添加完元素之后,再将原容器的引用指向新的容器。这样做的好处是我们可以对CopyOnWrite容器进行并发的读,而不需要加锁,因为当前容器不会添加任何元素。所以CopyOnWrite容器也是一种读写分离的思想,读和写不同的容器。 CopyOnWrite并发容器用于读多写少的并发场景。比如白名单,黑名单等场景。 CopyOnWrite两个缺点: 内存占用问题。因为CopyOnWrite的写时复制机制,所以在进行写操作的时候,内存里会同时驻扎两个对象的内存,旧的对象和新写入的对象(注意:在复制的时候只是复制容器里的引用,只是在写的时候会创建新对象添加到新容器里,而旧容器的对象还在使用,所以有两份对象内存)。 数据一致性问题。CopyOnWrite容器只能保证数据的最终一致性,不能保证数据的实时一致性。所以如果你希望写入的的数据,马上能读到,请不要使用CopyOnWrite容器。【当执行add或remove操作没完成时,get获取的仍然是旧数组的元素】

并发队列ConcurrentLinkedQueue和阻塞队列LinkedBlockingQueue使用场景总结

在并发队列上 JDK 提供了两套实现: 一个是以 ConcurrentLinkedQueue 为代表的高性能队列,一个是以 BlockingQueue 接口为代表的阻塞队列。无论哪种都继承自 Queue,并且都是线程安全的,都可以进行并发编程。 适用阻塞队列的好处:多线程操作共同的队列时不需要额外的同步,另外就是队列会自动平衡负载,即那边(生产与消费两边)处理快了就会被阻塞掉,从而减少两边的处理速度差距 当许多线程共享访问一个公共 collection 时,ConcurrentLinkedQueue 是一个恰当的选择。 LinkedBlockingQueue 多用于任务队列,并提供了 BlockingQueue 的等待性方法,BlockingQueue 基本都是基于锁实现 ConcurrentLinkedQueue  多用于消息队列,则是基于 CAS 的无锁技术,不需要在每个操作时使用锁,所以扩展性表现要更加优异。

单生产者,单消费者  用 LinkedBlockingqueue 多生产者,单消费者   用 LinkedBlockingqueue 单生产者 ,多消费者   用 ConcurrentLinkedQueue 多生产者 ,多消费者   用 ConcurrentLinkedQueue leeeyou.gitbooks.io/java-36/con…

ConcurrentLinkedQueue使用:

blog.csdn.net/liyantianmi… 有三个函数需要注意的: peek()获取元素 不移除头结点 poll() 获取元素并且在队列中移除,如果队列为空返回null size: 返回此队列中的元素数量。如果此队列包含的元素数大于 Integer.MAX_VALUE,则返回 Integer.MAX_VALUE。需要小心的是,与大多数 collection 不同,此方法不是 一个固定时间操作。由于这些队列的异步特性,确定当前的元素数需要进行一次花费 O(n) 时间的遍历。 注意1:ConcurrentLinkedQueue的.size() 是要遍历一遍集合的,很慢的,所以尽量要避免用size,如果判断队列是否为空最好用isEmpty()而不是用size来判断. 问题1:使用了这个ConcurrentLinkedQueue 类之后是否意味着我们不需要自己进行任何同步或加锁操作了呢? 如果直接使用它提供的函数,比如:queue.add(obj); 或者 queue.poll(obj);,这样我们自己不需要做任何同步。但如果是非原子操作,比如:

if(!queue.isEmpty()) { queue.poll(obj); } 我们很难保证,在调用了isEmpty()之后,poll()之前,这个queue没有被其他线程修改。所以对于这种情况,我们还是需要自己同步: 详见

ConcurrentHashMap并发的HashMap

ConcurrentHashMap是一个二级哈希表。在一个总的哈希表下面,有若干个子哈希表。 4172f2ff532e80137365e21d26c7babd.jpeg ConcurrentHashMap优势是才用锁分段技术,每一个Segment就好比一个自治区,读写操作高度自治,Segment之间互不影响。 3ac0454aad85fc7b2558a217bcd949ae.jpeg 8054691b578c93d6ab1e4bb53e9dd8ff.jpeg 394a7786587a60d4120abac32fc728da.jpeg ConcurrentHashMap读写过程: Get方法: 1.为输入的Key做Hash运算,得到hash值。 2.通过hash值,定位到对应的Segment对象 3.再次通过hash值,定位到Segment当中数组的具体位置。

Put方法: 1.为输入的Key做Hash运算,得到hash值。 2.通过hash值,定位到对应的Segment对象 3.获取可重入锁 4.再次通过hash值,定位到Segment当中数组的具体位置。 5.插入或覆盖HashEntry对象。 6.释放锁。

统计ConcurrentHashMap的size个数,怎么解决一致性问题? ConcurrentHashMap的Size方法是一个嵌套循环,大体逻辑如下: 1.遍历所有的Segment。 2.把Segment的元素数量累加起来。 3.把Segment的修改次数累加起来。 4.判断所有Segment的总修改次数是否大于上一次的总修改次数。如果大于,说明统计过程中有修改,重新统计,尝试次数+1;如果不是。说明没有修改,统计结束。 5.如果尝试次数超过阈值,则对每一个Segment加锁,再重新统计。 6.再次判断所有Segment的总修改次数是否大于上一次的总修改次数。由于已经加锁,次数一定和上次相等。 7.释放锁,统计结束。

public int size() {
    // Try a few times to get accurate count. On failure due to
   // continuous async changes in table, resort to locking.
   final Segment<K,V>[] segments = this.segments;
    int size;
    boolean overflow; // true if size overflows 32 bits
    long sum;         // sum of modCounts
    long last = 0L;   // previous sum
    int retries = -1; // first iteration isn't retry
    try {
        for (;;) {
            if (retries++ == RETRIES_BEFORE_LOCK) {
                for (int j = 0; j < segments.length; ++j)
                    ensureSegment(j).lock(); // force creation
            }
            sum = 0L;
            size = 0;
            overflow = false;
            for (int j = 0; j < segments.length; ++j) {
                Segment<K,V> seg = segmentAt(segments, j);
                if (seg != null) {
                    sum += seg.modCount;
                    int c = seg.count;
                    if (c < 0 || (size += c) < 0)
                        overflow = true;
                }
            }
            if (sum == last)
                break;
            last = sum;
        }
    } finally {
        if (retries > RETRIES_BEFORE_LOCK) {
            for (int j = 0; j < segments.length; ++j)
                segmentAt(segments, j).unlock();
        }
    }
    return overflow ? Integer.MAX_VALUE : size;
}

为什么这样设计呢?这种思想和乐观锁悲观锁的思想如出一辙。 为了尽量不锁住所有Segment,首先乐观地假设Size过程中不会有修改。当尝试一定次数,才无奈转为悲观锁,锁住所有Segment保证强一致性。

mp.weixin.qq.com/s?__biz=MzI…

HashMap?ConcurrentHashMap?相信看完这篇没人能难住

ArrayList和linkedlist

1.ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。

2.对于随机访问get和set,ArrayList绝对优于LinkedList,因为LinkedList要移动指针。

3.对于新增和删除操作add和remove,LinkedList比较占优势,因为ArrayList要移动数据。这一点要看实际情况的。若只对单条数据插入或删除,ArrayList的速度反而优于LinkedList。但若是批量随机的插入删除数据,LinkedList的速度大大优于ArrayList.因为ArrayList每插入一条数据,要移动插入点及之后的所有数据。

Hashtable和Hashmap

1.历史原因:Hashtable是基于陈旧的Dictionary类的,HashMap是Java1.2引进的Map接口的一个实现。

2.同步性:Hashtable是线程安全的,也就是说是同步的,这个类中的一些方法保证了Hashtable中的对象是线程安全的。而HashMap则是线程异步的,因此HashMap中的对象并不是线程安全的。因为同步的要求会影响执行的效率,所以如果你不需要线程安全的集合那么使用HashMap是一个很好的选择,这样可以避免由于同步带来的不必要的性能开销,从而提高效率。

3.HashMap可以让你将空值作为一个表的条目的key或value,但是Hashtable是不能放入空值的(null)

HashMap和TreeMap

1.HashMap通过hashcode对其内容进行快速查找,而TreeMap中所有的元素都保持着某种固定的顺序,如果你需要得到一个有序的结果你就应该使用TreeMap(HashMap中元素的排列顺序是不固定的)。

2.在Map中插入、删除和定位元素,HashMap是最好的选择。**但如果你要按自然顺序或自定义顺序遍历键,那么TreeMap会更好。**使用HashMap要求添加的键类明确定义了hashCode()和equals()的实现。这个TreeMap没有调优选项,因为该树总处于平衡状态。

HashSet与TreeSet

HashSet是基于hash算法实现的,性能优于TreeSet。通常使用HashSet,在我们需要对其中元素排序的时候才使用TreeSet。

Iterator(迭代器)的用法

不论Collection的实际类型如何,它都支持一个iterator()的方法,该方法返回一个迭代子,使用该迭代子即可逐一访问Collection中每一个元素。

Iterator模式是用于遍历集合类的标准访问方法。它可以把访问逻辑从不同类型的集合类中抽象出来,从而避免向客户端暴露集合的内部结构。

例如,如果没有使用Iterator,遍历一个数组的方法是使用索引:for(inti=0;i<array.size();i++) {..get(i)...}

而访问一个链表(LinkedList)又必须使用while循环:while((e=e.next())!=null){...e.data()...}

以上两种方法客户端都必须事先知道集合的内部结构,访问代码和集合本身是紧耦合,无法将访问逻辑从集合类和客户端代码中分离出来,每一种集合对应一种遍历方法,客户端代码无法复用。

更恐怖的是,如果以后需要把ArrayList更换为LinkedList,则原来的客户端代码必须全部重写。

为解决以上问题,Iterator模式总是用同一种逻辑来遍历集合:

for(Iteratorit=c.iterater(); it.hasNext();) { ...}

每一种集合类返回的Iterator具体类型可能不同,Array可能返回ArrayIterator,Set可能返回SetIterator,Tree可能返回TreeIterator,但是它们都实现了Iterator接口,因此,客户端不关心到底是哪种Iterator,它只需要获得这个Iterator接口即可,这就是面向对象的威力。

要确保遍历过程顺利完成,必须保证遍历过程中不更改集合的内容(Iterator的remove()方法除外),因此,确保遍历可靠的原则是只在一个线程中使用这个集合,或者在多线程中对遍历代码进行同步。

Collection c=new ArrayList();
c.add("abc");
c.add("xyz");
for(Iterator it=c.iterator();it.hasNext();){
         Strings=(String)it.next();
         System.out.println(s);
}

如果你把第一行代码的 ArrayList 换成 LinkedList 或 Vector ,剩下的代码不用改动一行就能编译,而且功能不变,这就是针对抽象编程的原则:对具体类的依赖性最小。

使用Collections

Collections可以对List进行排序。因为排序会直接修改List元素的位置,因此必须传入可变List:

public class Main {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("apple");
        list.add("pear");
        list.add("orange");
        // 排序前:
        System.out.println(list);
        Collections.sort(list);
        // 排序后:
        System.out.println(list);
    }
}

Collections提供了洗牌算法,即传入一个有序的List,可以随机打乱List内部元素的顺序,效果相当于让计算机洗牌:

public class Main {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        for (int i=0; i<10; i++) {
            list.add(i);
        }
        // 洗牌前:
        System.out.println(list);
        Collections.shuffle(list);
        // 洗牌后:
        System.out.println(list);
    }
}

Collections还提供了一组方法把可变集合封装成不可变集合:

封装成不可变List:List unmodifiableList(List<? extends T> list) 封装成不可变Set:Set unmodifiableSet(Set<? extends T> set) 封装成不可变Map:Map<K, V> unmodifiableMap(Map<? extends K, ? extends V> m) 这种封装实际上是通过创建一个代理对象,拦截掉所有修改方法实现的。我们来看看效果:

public class Main {
    public static void main(String[] args) {
        List<String> mutable = new ArrayList<>();
        mutable.add("apple");
        mutable.add("pear");
        // 变为不可变集合:
        List<String> immutable = Collections.unmodifiableList(mutable);
        immutable.add("orange"); // UnsupportedOperationException!
    }
}

f0bf0a198e270d56abb881c2238eee25.png

集合学习链接(有空看看):geek-docs.com/java/java-c…

点击这里复制本文地址 以上内容由权冠洲的博客整理呈现,请务必在转载分享时注明本文地址!如对内容有疑问,请联系我们,谢谢!

支持Ctrl+Enter提交

联系我们| 本站介绍| 留言建议 | 交换友链 | 域名展示 | 支付宝红包
本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除

权冠洲的博客 © All Rights Reserved.  Copyright quanguanzhou.top All Rights Reserved
苏公网安备 32030302000848号   苏ICP备20033101号-1
本网站由 提供CDN/云存储服务

联系我们