Java集合类

发表于

Java的集合主要分为三大块：List、Map、Set

List

常用的List类有：ArrayList、LinkedList

List接口需要实现一下方法：

List接口

ArrayList

  • ArrayList的默认容量为10

  • 每次扩容会变为之前的1.5倍

  • ArrayList中的数据减少时，容量不会减少

  • ArrayList存储元素使用数组：

    transient Object[] elementData;

  • ArrayList中的size指的是集合中元素的个数：

    private int size;

  • ArrayList通过索引访问元素很快，时间复杂度为O(1)：

    public E get(int index)

  • ArrayList在尾部插入元素，时间复杂度为O(1)：

    public boolean add(E e)

  • ArrayList在尾部删除元素，时间复杂度为O(1)：

    public E remove(int index) index为size-1时

  • ArrayList从中间插入元素，需要搬移元素，平均时间复杂度为O(n)：

    public void add(int index, E element)

  • ArrayList从中间删除元素，需要搬移元素，平均时间复杂度为O(n)：

    public E remove(int index)

  • ArrayList可以求并集、交集、单向差集

    • public boolean addAll(Collection<? extends E> c)

  • public boolean retainAll(Collection<?> c)

  • public boolean removeAll(Collection<?> c)

  • 为什么ArrayList中存储元素的数组elementData是被transient的？

    因为ArrayList中的elementData是可以扩容的，但是它的长度可能大于或等于实际元素的个数，如果，在序列化的时候将elementData自动序列化，那么会有多个空元素被序列化到磁盘中，所有源码中使用transient禁止序列化，并且在private void writeObject(java.io.ObjectOutputStream s)中通过size的个数对元素进行序列化

LinkedList

  • LinkedList继承了Queue接口，实现队列的功能
  • LinkedList继承了Deque接口，实现双端队列的功能（队列、栈）
  • LinkedList内部使用双向链表实现List的功能
  • LinkedList没有实现RandomAccess接口，所以访问非队列首尾的元素比较低效
  • LinkedList中用size记录元素个数，并有链表首节点first和链表尾节点last
  • LinkedList在队列首尾添加、删除元素效率高，时间复杂度为O(1)：
    • private void linkFirst(E e)
    • void linkLast(E e)
    • private E unlinkFirst(Node<E> f)
    • private E unlinkLast(Node<E> l)
  • LinkedList在中间添加、删除元素效率低，时间复杂度为O(n)：
    • public void add(int index, E element)
    • public E remove(int index)

Map

常用的Map有：

  • HashMap
  • LinkedHashMap
  • ConcurrentHashMap/HashTable
  • TreeMap

Map接口

HashMap

  1. HashMap的内部结构是数组+链表(jdk1.7)。链表长度大于8时，且扩容达到64长度数组时，链表会转化为红黑树(jdk1.8新增)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    transient Node<K,V>[] table;//数组
    //链表的结构
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
    }
    //红黑树结构
    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
    }

  2. 为什么用数组+链表

    当新插入的元素放入数组中，数组当前位置为空时，直接插入；如何当前位置已经存在元素，则对当前链表进行搜索，找到最后一个链表元素，将新插入的元素放在最后一个链表元素的后面。这样的做法是为了解决Hash冲突的问题。

  3. HashMap的hash()如何设计，为什么？

    将Key的hashCode与hashCode的高16位进行异或得到。

    因为在插入数据的时候是通过2的幂次进行散列操作，如果不与高16位进行异或，那么会有更高的hash冲突。

  4. hash冲突你还知道哪些解决办法？

    比较出名的有四种(1)开放定址法(2)链地址法(3)再哈希法(4)公共溢出区域法

  5. HashMap在什么条件下扩容？

    数组中所有元素大于数组长度*扩容阈值

  6. 为什么数组长度/扩容的容量为2的幂次？

    为了存取高效、减少碰撞、让数据均匀分布在每个链表中，所以元素对于数组的位置计数使用元素key的hash对数组长度进行取模操作，并使用位移操作进行计算。

    1
    2
    hash%length
    hash&(length-1)

    当length为2的幂次（$2^n$）时，length的二进制位1000…00，那么length-1位111…11，这样在&hash的时候可以减小碰撞。

  7. 为什么在解决hash冲突的时候，不直接用红黑树?而选择先用链表，再转红黑树?

    因为红黑树需要进行左旋，右旋，变色这些操作来保持平衡，而单链表不需要。

    当元素小于8个当时候，此时做查询操作，链表结构已经能保证查询性能。当元素大于8个的时候，此时需要红黑树来加快查询速度，但是新增节点的效率变慢了。

    因此，如果一开始就用红黑树结构，元素太少，新增效率又比较慢，无疑这是浪费性能的。

ConcurrentHashMap

  • 是HashMap的线程安全版本，内部结构相同
  • 效率高于HashTable