集合概述

集合和数组的区别

  • 数组的长度是固定的；集合是可变长的；
  • 数组中可以存储基本数据类型，也可以存储区引用数据类型；集合只能存储引用数据类型
  • 数组存储的元素必须是同一个数据类型；集合存储的对象可以是不同数据类型

集合框架底层数据结构

Collection

List

  • ArrayList：Object数组
  • Vector：Object数组
  • LinkedList：双向循环链表

Set

  • HashSet（无序，唯一）：基于HashMap实现，底层采用HashMap来保存元素
  • LinkedHashSet：LinkedHashSet继承于HashSet，并且其内部是通过LinkedHashMap来实现的。
  • TreeSet（有序，唯一）：红黑树

Map

  • HashMap：JDK1.8之前HashMap由数组+链表组成，数组是HashMap的主体，链表是为了解决哈希冲突而存在的（拉链法），JDK1.8以后当链表长度大于阈值8时，将链表转化为红黑树，以减少搜索时间；
  • LinkedHashMap：继承自HashMap，所以它的底层仍然是基于拉链式散列结构（即由数组+链表或红黑树）组成，不过在此基础上增加了一条双向链表，使得上面的结果可以保持键值对的插入顺序，同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。

哪些集合类是线程安全的？

  • vector：效率低，不建议使用；
  • stack：继承自vector
  • Hashtable：
  • ConcurrentHashMap
  • Enumeration：枚举

Java集合的快速失效机制“fail-fast”

“fail-fast”是Java集合的一种错误检测机制，当多个线程对集合进行结构上的改变操作时，就有可能产生fail-fast机制。

原因：迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个modCount变量，集合在被遍历期间如果内容发生变化，就会改变modCount的值。
每当迭代器使用hasNext()/next()遍历下一个元素之前，都会检测modCount变量是否为预期的值，如果是就返回遍历，否则抛出异常，终止遍历。

解决办法：
1、在遍历过程中，所有涉及到改变modCount值的地方都加上synchronized；
2、使用CopyOnWriteArrayList来代替ArrayList

Collection

如何边遍历边移除Collection中的元素

正确写法：

Iterator<Integer> it = list.iterator();
while(it.hasNext()){
   *// do something*
   it.remove();
}

错误写法：

for(Integer i : list){
   list.remove(i)
}

原因：当使用foreach语句时，会自动生成一个iterator来遍历该list，但同时该list正在被Iterator.remove()修改，Java一般不允许一个线程在遍历Collection时另一个线程修改它。

如何实现数组与List之间的转换

  • 数组转List：使用Arrays.asList(array)进行转换；
  • List转数组：使用List自带的toArray方法。

ArrayLsit和Vector的区别是什么

  • 线程安全：Vector使用了Synchronized来实现线程同步，而ArrayList是非线程安全的；
  • 性能：ArrayList在性能方面优于Vector；
  • 扩容：ArrayList初始大小为10，每次进行1.5倍扩容，Vector进行2倍扩容。

ArrayList和LinkedList的区别

  1. ArrayList是实现了基于动态数组的数据结构，LinkedList是基于链表结构。
  2. 对于随机访问的get和set方法，ArrayList要优于LinkedList，因为LinkedList要移动指针。
  3. 对于新增和删除操作add和remove，LinkedList比较占优势，因为ArrayList要移动数据。

CopyOnWriteArrayList

CopyOnWriteArrayList是一个写时复制的容器，用读写分离的思想用来保证list的一致性，其实现是当我们往一个容器添加元素的时候，不直接往当前容器添加，而是先将当前容器进行copy，复制出一个新的容器，然后在新的容器里添加元素，添加完元素之后，再将原容器的引用指向新的容器；这样做的好处是我们可以对CopyOnWriteArrayList进行并发的读，而不需要加锁，而在其增删改的操作中都使用了独占锁ReetrantLock来保证某个时间只有一个线程能对list数组进行修改。

缺点：

  • 内存占用：在进行写操作的时候，内存里会同时驻扎两个对象的内存。
  • 数据一致性问题：不能保证数据的实时一致性，只能保证数据的最终一致性。

List和Set的区别

List和Set都是继承自Collection接口

List特点：有序（元素存入集合的顺序和取出的顺序一致），元素可以重复，可以插入多个null元素；支持for循环，可以通过下标来遍历，查找元素效率高，插入删除元素效率低。

Set特点：无序，不可以存储重复元素，只允许存入一个null元素；只能通过迭代来获取数据，删除和插入效率高，检索元素效率低。

Set接口

HashSet实现原理

HashSet是基于HashMap实现的，HashSet的值存放于HashMap的key上，HashMap的value统一为PRESEENT，相关HashSet的操作，基本上都是直接调用底层HashMap的相关方法来实现的。

HashSet如何检查重复？HashSet如何保证数组不可重复？

HashSet在添加元素时，通过比较hash值以及结合equals方法来比较，HashSet添加进去的值就是作为HashMap的key，PRESENT作为value是一个始终相等的虚值。

private static final Object PRESENT = new Object();
private transient HashMap<E,Object> map;

public HashSet() {
    map = new HashMap<>();
}

public boolean add(E e) {
    // 调用HashMap的put方法,PRESENT是一个至始至终都相同的虚值
	return map.put(e, PRESENT)==null;
}

Queue

在Queue中poll()和remove()有什么区别？

  • 相同点：都是返回第一个元素，并在队列中删除返回的对象
  • 不同点：如果队列中没有元素，调用poll()返回null，调用remove()则抛出异常

Map

HashMap的实现原理

HashMap是基于哈希表的Map接口的非同步实现，允许使用null值和null键，此类不保证映射的顺序，HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。

HashMap基于Hash算法实现的：

  1. 当我们往HashMap中put元素时，利用key的HashCode重新hash计算出当前对象的元素在数组中的下标;
  2. 在存储时，如果出现hash值相同的key，此时有两种情况：如果key相同，则覆盖原始值，如果key不同，则将当前的key-value放入链表中;
  3. 获取时，直接找到hash值对应的下标，再进一步判断key是否相同，从而找到对应值;
  4. JDK1.8以后，当链表中的节点数据超过8个以后，该链表会转为红黑树来提高查询效率，从原来的O(n)到O(logn)。

HashMap的扩容操作是怎么实现的？

1、在JDK1.8中，resize()方法是在HashMap中的键值对大于阈值时或者初始化时，就调用resize方法进行扩容；
2、每次扩容时，都是扩为原来的2倍；
3、扩展后的Node对象的位置要么在原位置，要么移动到原始位置+增加的数组大小的位置上。

HashMap是如何有效解决Hash冲突的？

1、使用链地址法(拉链法)来连接拥有相同hash值的数据；
2、使用2次扰动函数（hash函数）来降低哈希冲突的概率，使得数据分布更平均；
3、引入红黑树进一步降低遍历的时间复杂度，使得遍历更快；

HashMap的长度为什么是2的幂次方

为了能让HashMap存取高效，尽量减少碰撞，也就是尽量把数据分配均匀，另外在取余操作中如果除数是2的幂次方，则等价于与其除数减一的与（&）操作（也就是说hash%length==hash&(length-1)的前提是length是2的n次方），采用二进制位运算能够提高运算效率。

HashMap和HashTable有什么区别

  1. 线程安全：HashMap非线程安全，HashTable线程安全，不过不建议使用，一般用ConcurrentHashMap；
  2. 效率：HashMap效率高于HashTable
  3. 对null key 和null value的支持：HashMap允许null作为键，但是只能有一个，可以有多个键所对应的值为null；HashTable中键值对都不允许为null
  4. 初始容量大小和每次扩容量大小：创建时如果不指定容量初始值，HashTable默认的初始值大小为11，之后每次扩容容量变为原来的2n+1，HashMap的初始容量为16，之后每次扩容为原来的2倍。

HashMap在JDK1.8做了什么优化

  • JDK1.8增加了红黑树来进行优化，当链表长度超过8时，链表就转为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能；
  • 在JDK1.7中，插入链表节点使用头插法，JDK1.8中变为了尾插法，这是因为头插法在并发下调用transfer()方法，可能会导致链表死循环，以及数据的丢失。
  • hash()方法，将hash值高位（前16位）参与到取模的运算中，使得计算结果的不确定性增强，降低发生哈希碰撞的概率。

ConcurrentHashMap在JDK1.8做了哪些优化？

ConcurrentHashMap在Java 8 里抛弃了Segment的概念，直接用Node数组+链表+红黑树的数据结构来实现，Node是ConcurrentHashMap存储结构的基本单元，继承于HashMap中的Entry，用于存储数据，并发控制使用Synchronized和CAS来操作。

HashMap,LinkedHashMap,TreeMap的区别？

区别：

  • LinkedHashMap是继承于HashMap，是基于HashMap和双向链表来实现的。
  • HashMap无序；LinkedHashMap有序，可分为插入顺序和访问顺序两种。如果是访问顺序，那put和get操作已存在的Entry时，都会把Entry移动到双向链表的表尾(其实是先删除再插入)。
  • LinkedHashMap存取数据，还是跟HashMap一样使用的Entry[]的方式，双向链表只是为了保证顺序。
  • LinkedHashMap是线程不安全的。

LinkedHashMap应用场景：

当我们希望有顺序地去存储key-value时，就需要使用LinkedHashMap。

TreeMap的用法（主要是排序）

TreeMap中默认的排序是升序，如果要改变其排序可以自己写一个Comparator，重写其compare()方法。

public class Compare {
    public static void main(String[] args) {
        TreeMap<String, Integer> map = new TreeMap<String, Integer>(new xbComparator());
        map.put("192.168.1.11", 1);
        map.put("193.168.2.11", 1);
        map.put("192.128.1.11", 1);
        map.put("192.168.1.12", 1);
        map.put("192.168.1.31", 1);

        Set<String> keys = map.keySet();
        Iterator<String> iterator = keys.iterator();
        while (iterator.hasNext()) {
            String next = iterator.next();
            System.out.println(" " + next + ":" + map.get(next));
        }
    }
}
class xbComparator implements Comparator {

    @Override
    public int compare(Object o1, Object o2) {
        String s1 = (String) o1;
        String s2 = (String) o2;
        return s2.compareTo(s1);
    }
}

辅助工具类

comparable

Comparable是排序接口，若一个类实现了Comparable接口，就意味着“该类支持排序”，也就是说实现了Comparable接口的类的对象的列表或数组可以通过Collections.sort()或Arrays.sort()进行排序。

Comparable接口仅仅只包含一个函数，它的定义如下：

package java.lang;
import java.util.*;

public interface Comparable<T> {
    public int compareTo(T o);
}

假设我们通过x.compareTo(y)来比较x和y的大小，若返回负数，意味着x比y小，返回0，说明相等，返回正数，说明x比y大。

现在我们假设一个Person类，代码如下：

public class Person
{
    String name;
    int age;
    public Person(String name, int age){
        super();
        this.name = name;
        this.age = age;
    }
    public String getName(){
        return name;
    }
    public int getAge(){
        return age;
    }
}

现在有两个Person类的对象，我们如何来比较二者的大小呢？我们可以通过让Person实现Comparable接口：

public class Person implements Comparable<Person>
{
    String name;
    int age;
    public Person(String name, int age) {
        super();
        this.name = name;
        this.age = age;
    }
    public String getName() {
        return name;
    }
    public int getAge() {
        return age;
    }
    @Override
    public int compareTo(Person p) {
        return this.age-p.getAge();
    }
    public static void main(String[] args) {
        Person[] people=new Person[]{
            new Person("xujian", 20),new Person("xiewei", 10)
        };
        System.out.println("排序前");
        for (Person person : people) {
            System.out.print(person.getName()+":"+person.getAge());
        }
        Arrays.sort(people);
        System.out.println("\n排序后");
        for (Person person : people) {
            System.out.print(person.getName()+":" + person.getAge());
        }
    }
}

Comparator

Comparator是比较器接口，我们若需要控制某个类的次序，而该类本身不支持排序（即没有实现Comparable接口），那么，我们可以建立一个该类的比较器来进行排序，这个比较器只需要实现Comparator接口即可。也就是说，我们可以通过实现Comparator类来新建一个比较器，然后通过该比较器对类进行排序。

Comparator接口仅仅包含两个函数，它的定义如下：

package java.util;

public interface Comparator<T> {

    int compare(T o1, T o2);

    boolean equals(Object obj);
}

说明：

  • 如果一个类要实现Comparator接口，它一定要实现Compare(T o1,T o2)函数，但可以不实现equals(Object obj)函数。

  • int compare(T o1, T o2) 是“比较o1和o2的大小”。返回“负数”，意味着“o1比o2小”；返回“零”，意味着“o1等于o2”；返回“正数”，意味着“o1大于o2”。

现在假如上面的Person类没有实现Comparable接口，该如何比较大小呢？我们可以新建一个类，让其实现Comparator接口，从而构造一个“比较器”。

public class PersonCompartor implements Comparator<Person>{
    @Override
    public int compare(Person o1, Person o2) {
        return o1.getAge()-o2.getAge();
    }
}

现在我们就可以利用这个比较器来对其进行排序：

public class Person{
    String name;
    int age;
    public Person(String name, int age) {
        super();
        this.name = name;
        this.age = age;
    }
    public String getName() {
        return name;
    }
    public int getAge() {
        return age;
    }
    public static void main(String[] args) {
        Person[] people=new Person[]{new Person("xujian", 20),new Person("xiewei", 10)};
        System.out.println("排序前");
        for (Person person : people) {
            System.out.print(person.getName()+":"+person.getAge());
        }
        Arrays.sort(people,new PersonCompartor());
        System.out.println("\n排序后");
        for (Person person : people) {
            System.out.print(person.getName()+":"+person.getAge());
        }
    }
}

Comparable和Comparator区别比较

  • Comparable是排序接口，若一个类实现了Comparable接口，就意味着“该类支持排序”。

  • 而Comparator是比较器接口，我们若需要控制某个类的次序，可以建立一个“该类的比较器”来进行排序。

  • Comparable相当于“内部比较器”，而Comparator相当于“外部比较器”。

  • 两种方法各有优劣， 用Comparable 简单， 只要实现Comparable 接口的对象直接就成为一个可以比较的对象，但是需要修改源代码。 用Comparator 的好处是不需要修改源代码， 而是另外实现一个比较器， 当某个自定义的对象需要作比较的时候，把比较器和对象一起传递过去就可以比大小了， 并且在Comparator 里面用户可以自己实现复杂的可以通用的逻辑，使其可以匹配一些比较简单的对象，那样就可以节省很多重复劳动了。

语言相关 Java进阶 Java集合
Java集合

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！

Java异常 Previous
Java基础 Next