集合类

Java
Java
Publish Date:   2021-05-29

Java 常用集合

1. List

1.1 List基本实现

  • ArrayList: List 主要实现类，底层使用Object[]存储，适合频繁查询工作，线程不安全
  • Vector: 古老实现类，线程安全，
  • LinkedList: 底层使用双向链表结构,JDK1.7取消了循环
    • getFirst（） 和element（） 完全一样，都返回第一个元素。如果为空，抛NoSuchElementException.
    • peek（） 方法与上诉类似，只时列表为空返回null
    • removeFirst（） 和 remove（） 类似，移除并返回列表的头，只是列表为空抛出NoSuchElementException。
    • poll（） 同样移除并返回列表头，只是列表为空返回Null
  • Stack: 栈结构,pop（）、push（）、 peek（）方法，其中peek（）返回栈顶元素，而不将其移除。

1.2 ArrayList扩容与源码分析

（JDK8）ArrayList 有三种方式来初始化，构造方法源码如下：

   /**
     * 默认初始容量大小
     */
    private static final int DEFAULT_CAPACITY = 10;


    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     *默认构造函数，使用初始容量10构造一个空列表(无参数构造)
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     * 带初始容量参数的构造函数。（用户自己指定容量）
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {//初始容量大于0
            //创建initialCapacity大小的数组
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {//初始容量等于0
            //创建空数组
            this.elementData = EMPTY_ELEMENTDATA;
        } else {//初始容量小于0，抛出异常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }


   /**
    *构造包含指定collection元素的列表，这些元素利用该集合的迭代器按顺序返回
    *如果指定的集合为null，throws NullPointerException。
    */
     public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }
  • 无参初始化容量为10
  • int newCapacity = oldCapacity + (oldCapacity >> 1),所以 ArrayList 每次扩容之后容量都会变为原来的 1.5 倍左右（oldCapacity 为偶数就是 1.5 倍，否则是 1.5 倍左右）！ 奇偶不同，比如 ：10+10/2 = 15, 33+33/2=49。如果是奇数的话会丢掉小数.

1.3 LinkedList 源码

定义了一个内部的Node 节点，基于双向链表实现，使用 Node 存储链表节点信息。
相关操作：

  • getFirst() 和element() 完全一样，都返回第一个元素。如果为空，抛NoSuchElementException.

  • peek() 方法与上诉类似，只时列表为空返回null

  • removeFirst() 和 remove() 类似，移除并返回列表的头，只是列表为空抛出NoSuchElementException。

  • poll() 同样移除并返回列表头，只是列表为空返回Null

    private static class Node<E> {
      E item;
      Node<E> next;
      Node<E> prev;

      Node(Node<E> prev, E element, Node<E> next) {
          this.item = element;
          this.next = next;
          this.prev = prev;
      }
  }

  • add（）方法有add（E e） 方法：将元素添加到链表尾部，add（int index,E e）：在指定位置添加元素

  • addAll（Collection c ）：将集合插入到链表尾部,addAll（int index, Collection c）： 将集合从指定位置开始插入

  • get(int index)： 根据指定索引返回数据,**int indexOf(Object o)**： 从头遍历找 **int lastIndexOf(Object o)**： 从尾遍历找, **remove(int index)**：删除指定位置的元素

1.4 ArrayList与LinkedList区别

1. 是否保证线程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；
2. 底层数据结构： Arraylist 底层使用的是 Object 数组；LinkedList 底层使用的是 双向链表 数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环。注意双向链表和双向循环链表的区别，下面有介绍到！）
3. 插入和删除是否受元素位置的影响：
ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。 比如：执行add（E e）方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O（1）。但是如果要在指定位置 i 插入和删除元素的话（add（int index, E element））时间复杂度就为 O（n-i）。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的（n-i）个元素都要执行向后位/向前移一位的操作。
LinkedList 采用链表存储，所以，如果是在头尾插入或者删除元素不受元素位置的影响（add（E e）、addFirst（E e）、addLast（E e）、removeFirst（） 、 removeLast（）），近似 O（1），如果是要在指定位置 i 插入和删除元素的话（add（int index, E element），remove（Object o）） 时间复杂度近似为 O（n） ，因为需要先移动到指定位置再插入。
4. 是否支持快速随机访问： LinkedList 不支持高效的随机元素访问，而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象（对应于get（int index）方法）。
5. 内存空间占用： ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。

2. Map

  • HashMap： JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间
  • LinkedHashMap： LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。详细可以查看：《LinkedHashMap 源码详细分析（JDK1.8）》
  • Hashtable： 数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的
  • ConcurrentHashMap: 线程安全的Map.
  • TreeMap: 基于红黑树的实现（自平衡的排序二叉树）。“键”或“键值对”的次序是由Comparable或Comparator决定的。TreeMap是唯一带有subMap()方法的Map，可以返回一个子树。
  • WeakHashMap： 弱键映射，允许设释放射所指对象。被垃圾收集器回收。
  • ConcurrentHashMap: 线程安全的Map.
  • IdentityHashMap：使用==代替equals()对“键”进行比较的散列映射。
  • sortedMap: 排序的Map，现阶段TreeMap是其唯一实现。
  • EnumMap:要求键必须来自一个Enum。

2.1 HashMap

  • 底层实现
    JDK1.8 之前 HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列。

HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 （n - 1） & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

1.8 的hash方法
    static final int hash(Object key) {
      int h;
      // key.hashCode()：返回散列值也就是hashcode
      // ^ ：按位异或
      // >>>:无符号右移，忽略符号位，空位都以0补齐
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
    // 序列号
    private static final long serialVersionUID = 362498820763181265L;
    // 默认的初始容量是16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    // 最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30;
    // 默认的填充因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 当桶(bucket)上的结点数大于这个值时会转成红黑树
    static final int TREEIFY_THRESHOLD = 8;
    // 当桶(bucket)上的结点数小于这个值时树转链表
    static final int UNTREEIFY_THRESHOLD = 6;
    // 桶中结构转化为红黑树对应的table的最小大小
    static final int MIN_TREEIFY_CAPACITY = 64;
    // 存储元素的数组，总是2的幂次倍
    transient Node<k,v>[] table;
    // 存放具体元素的集
    transient Set<map.entry<k,v>> entrySet;
    // 存放元素的个数，注意这个不等于数组的长度。
    transient int size;
    // 每次扩容和更改map结构的计数器
    transient int modCount;
    // 临界值 当实际大小(容量*填充因子)超过临界值时，会进行扩容
    int threshold;
    // 加载因子
    final float loadFactor;
}
  • loadFactor 加载因子

loadFactor 加载因子是控制数组存放数据的疏密程度，loadFactor 越趋近于 1，那么 数组中存放的数据(entry)也就越多，也就越密，也就是会让链表的长度增加，loadFactor 越小，也就是趋近于 0，数组中存放的数据(entry)也就越少，也就越稀疏。

loadFactor 太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor 的默认值为 0.75f 是官方给出的一个比较好的临界值。

给定的默认容量为 16，负载因子为 0.75。Map 在使用过程中不断的往里面存放数据，当数量达到了 16 * 0.75 = 12 就需要将当前 16 的容量进行扩容，而扩容这个过程涉及到 rehash、复制数据等操作，所以非常消耗性能。

  • threshold

threshold = capacity * loadFactor，当 Size>=threshold的时候，那么就要考虑对数组的扩增了，也就是说，这个的意思就是 衡量数组是否需要扩增的一个标准。

  • 扩容
  1. 计算扩容新的table长度size 与threshold 的长度
  2. 遍历旧table，如果节点，无哈希冲突的情况，e.hash&(newCap-1)直接定位到新的位置。
  3. 出现哈希冲突的情况，由于每次扩容的大小默认为2的n次方，因此重散列的位置只会为当前位置或者当前位置+旧数组大小两个位置。
  4. 如果节点存在哈希冲突，则根据位运算计算最新的位置是否为0，为0表示无需移动节点。为1表示移动到oldCap+j的位置。
  5. 针对出现红黑树的哈希冲突，同理。此处针对红黑树冲突的需要判断重散列的节点是否需要重新建立红黑树。
  6. 如果初始化容量大小部位2的幂次方，那么在初始化的时候，会计算threshold为大于初始化数的最近2的幂次方数，在实际使用的时候声明为table的大小。※
  • 红黑树

红黑树： 红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须满足下面性质：

  • 性质1：每个节点要么是黑色，要么是红色。
  • 性质2：根节点是黑色。
  • 性质3：每个叶子节点（NIL）是黑色。
  • 性质4：每个红色结点的两个子结点一定都是黑色。
  • 性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。
    三种操作：左旋、右旋和变色。

左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。如图3。
右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。如图4。
变色：结点的颜色由红变黑或由黑变红。 https://www.jianshu.com/p/e136ec79235c

  • put操作
  1. 首先判断table是否需要扩容，若需要进行扩容操作
  2. 计算当前元素hash经过散列后是否有元素存在，若不存在元素直接添加。
  3. 若存在元素，分下面两个判断
    替换：若旧元素的hash值与新添加元素一致，且新添加Node 的key调用equals方法一致，则直接替换旧节点。
    拉链法：
    普通链表：循环判断链表节点是否为key相同替换情况，若均不是需要替换情况，则定位到链表尾部添加新节点。
    红黑树：树形遍历判断是否存在，不存在添加。
  • hashmap红黑树查找

为什么使用红黑树： 当HashMap中有大量的元素都存放到同一个桶中时，这个桶下有一条长长的链表，这个时候HashMap就相当于一个单链表，假如单链表有n个元素，遍历的时间复杂度就是O(n)，完全失去了它的优势。 针对这种情况，JDK1.8中引入了红黑树来优化这个问题，为什么不引入二叉查找树呢？因为二叉查找树的一般操作的执行时间为O(lgn)，但是二叉查找树若退化成了一棵具有n个结点的线性链后，则这些操作最坏情况运行时间为O(n)。与单链表一样。 所以此时我们需要红黑树它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。
红黑树建立是基于Hash的大小来建立的。这里的hashcode 为hashMap换算过的hash。hash小的为左子树， hash 大的为右子树

针对hash重复的情况：

使用equal的方法进行匹配，相同返回。
若存在左节点或右节点缺失，则直接进入未缺失的节点查找。（left==null ==> findByRight)，均不存在返回null。
左右子节点均存在，判断是否为相同的class，及class是否继承comparable接口，
若为相同的class且都继承则直接通过comparable判断左右节点。
若不同的class、无继承comparable接口或者经过comparable接口比较的结果相等。
递归调用左节点查找，若未找到，递归调用右节点查找。

 final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
    TreeNode<K,V> p = this;
    do {
        int ph, dir; K pk;
        TreeNode<K,V> pl = p.left, pr = p.right, q;
        if ((ph = p.hash) > h)
            p = pl;
        else if (ph < h)
            p = pr;
        // hash 相同 使用equal比较
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        // 左右子树缺失，直接进入存在子树的部分
        else if (pl == null)
            p = pr;
        else if (pr == null)
            p = pl;
        // 基于class的比较，若都继承comparable接口，则使用compareTo比较
        // 若class 均不继承comparable 接口，或者compare接口比较后相同，进入左右子树递归查询。
        else if ((kc != null ||
                  (kc = comparableClassFor(k)) != null) &&
                 (dir = compareComparables(kc, k, pk)) != 0)
            p = (dir < 0) ? pl : pr;
        else if ((q = pr.find(h, k, kc)) != null)
            return q;
        else
            p = pl;
    } while (p != null);
    return null;
}

针对建立红黑树或者添加树节点的情况

  • 若使用equal及class 的compare 均无法确定添加节点的方向

  • 使用对象的类名进行判断，若类名依然相同，则使用System根据对象地址换算的hashcode编码判断添加方向。
    static int tieBreakOrder(Object a, Object b) {

      int d;
  if (a == null || b == null ||
      (d = a.getClass().getName().
       compareTo(b.getClass().getName())) == 0)
      d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
           -1 : 1);
  return d;

    }

  • HashMap遍历方法

    • 使用迭代器（Iterator）EntrySet 的方式进行遍历；
    • 使用迭代器（Iterator）KeySet 的方式进行遍历；
    • 使用 For Each EntrySet 的方式进行遍历；
    • 使用 For Each KeySet 的方式进行遍历；
    • 使用 Lambda 表达式的方式进行遍历；
    • 使用 Streams API 单线程的方式进行遍历；
    • 使用 Streams API 多线程的方式进行遍历。

如果从性能方面考虑，我们应该尽量使用 lambda 或者是 entrySet 来遍历 Map 集合。

EntrySet 之所以比 KeySet 的性能高是因为，KeySet 在循环时使用了 map.get（key），而 map.get（key） 相当于又遍历了一遍 Map 集合去查询 key 所对应的值。为什么要用“又”这个词？那是因为在使用迭代器或者 for 循环时，其实已经遍历了一遍 Map 集合了，因此再使用 map.get（key） 查询时，相当于遍历了两遍。
而 EntrySet 只遍历了一遍 Map 集合，之后通过代码“Entry<Integer, String> entry = iterator.next（）”把对象的 key 和 value 值都放入到了 Entry 对象中，因此再获取 key 和 value 值时就无需再遍历 Map 集合，只需要从 Entry 对象中取值就可以了。
所以，EntrySet 的性能比 KeySet 的性能高出了一倍，因为 KeySet 相当于循环了两遍 Map 集合，而 EntrySet 只循环了一遍。

https://juejin.cn/post/6844904144331866119

2.2 concurrentHashMap

  • 数据结构:synchronized+CAS+Node+红黑树,Node的val和next都用volatile修饰,保证可见性
  • 查找,替换,赋值操作都使用CAS
  • 锁:锁链表的head节点,不影响其他元素的读写,锁粒度更细,效率更高,扩容时,阻塞所有的读写
    操作、并发扩容
  • 读操作无锁:
    Node的val和next使用volatile修饰,读写线程对该变量互相可见
    数组用volatile修饰,保证扩容时被读线程感知
Java
评论
 Previous
Java并发(一) Java并发(一)
1. 进程与线程1.1进程 进程（Process）是计算机中的程序关于某数据集合上的一次运行活动，是系统进行资源分配和调度的基本单位，是操作系统结构的基础。进程是程序的基本执行实体；在当代面向线程设计的计算机结构中，进程是线程的容器。程序是
2021-06-03 Java
Java
Next 
排序算法 排序算法
相关资料：https://www.jianshu.com/p/47170b1ced23 冒泡排序算法描述 比较相邻的元素，如果前一个比后一个大，交换两个元素 从最开始的一对到最后一对，这样最后的元素就是数组里最大的数 重复以上步骤，除
2021-05-28 算法
算法
  TOC