Java容器

2019-12-16  本文已影响0人  雪飘千里
image.png image.png

List：

1) ArrayList类

底层使用数组实现，查询快，增删慢
　　ArrayList实现了可变大小的数组。它允许所有元素，包括null。ArrayList没有同步。size，isEmpty，get，set方法运行时间为常数。但是add方法开销为分摊的常数，添加n个元素需要O(n)的时间。其他的方法运行时间为线性。每个ArrayList实例都有一个容量（Capacity），即用于存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加，但是增长算法并 没有定义。当需要插入大量元素时，在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。

和LinkedList一样，ArrayList也是非同步的（unsynchronized）。一般情况下使用这两个就可以了，因为非同步，所以效率比较高。
如果涉及到堆栈，队列等操作，应该考虑用List，对于需要快速插入，删除元素，应该使用LinkedList，如果需要快速随机访问元素，应该使用ArrayList。

**数组：采用一段连续的存储单元来存储数据 **

2）LinkedList类

底层使用双向循环链表实现，查询慢，增删快
　　LinkedList实现了List接口，允许null元素。此外LinkedList提供额外的get，remove，insert方法在 LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈（stack），队列（queue）或双向队列（deque）。

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

单链表：每个节点包含值、链接到下一个节点的引用字段


image.png

双链表：双链表中的每个节点包含值，链接到下一个节点的引用字段、链接到上一个节点的引用字段


image.png

LinkedList中是双向链表

    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;
        }
    }

Set：

1）HashSet

底层使用哈希表实现
Hash表：Hash表也称散列表，也有直接译作哈希表，Hash表是一种根据关键字值（key - value）而直接进行访问的数据结构。它基于数组，通过把关键字映射到数组的某个下标来加快查找速度，但是又和数组、链表、树等数据结构不同，在这些数据结构中查找某个关键字，通常要遍历整个数据结构，也就是O(N)的时间级，但是对于哈希表来说，只是O(1)的时间级。

注意，这里有个重要的问题就是如何把关键字转换为数组的下标，这个转换的函数称为哈希函数（也称散列函数），转换的过程称为哈希化

哈希表基于数组，类似于key-value的存储形式，关键字值通过哈希函数映射为数组的下标，如果一个关键字哈希化到已占用的数组单元，这种情况称为冲突。用来解决冲突的有两种方法：开放地址法和链地址法。在开发地址法中，把冲突的数据项放在数组的其它位置；在链地址法中，每个单元都包含一个链表，把所有映射到同一数组下标的数据项都插入到这个链表中（HashMap）。

2）TreeSet：

底层使用二叉树实现
TreeSet是SortedSet接口的唯一实现类，TreeSet可以确保集合元素处于排序状态。TreeSet支持两种排序方式，自然排序 和定制排序，其中自然排序为默认的排序方式。向TreeSet中加入的应该是同一个类的对象。TreeSet判断两个对象不相等的方式是两个对象通过equals方法返回false，或者通过CompareTo方法比较没有返回0

HashSet VS TreeSet

HashSet是基于Hash算法实现的，其性能通常都优于TreeSet。我们通常都应该使用HashSet，在我们需要排序的功能时，我们才使用TreeSet。

队列Queue：

队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
在队列这种数据结构中，最先插入的元素将是最先被删除的元素；反之最后插入的元素将是最后被删除的元素，因此队列又称为“先进先出”（FIFO—first in first out）的线性表。

在并发队列上JDK提供了两套实现，一个是以ConcurrentLinkedQueue为代表的高性能队列（非阻塞队列），一个是以BlockingQueue接口为代表的阻塞队列，无论哪种都继承自Queue。

ConcurrentLinkedQueue：并发队列

是一个适用于高并发场景下的队列，通过CAS的无锁技术的方式，实现了高并发状态下的高性能，通常ConcurrentLikedQueue性能好于BlockingQueue。

它是一个基于链表节点的无界线程安全队列。该队列的元素遵循先进先出的原则。头是最先加入的，尾是最近加入的，该队列不允许null元素。

ConcurrentLinkedQueue重要方法：
add()和offer()都是加入元素的方法(在ConcurrentLinkedQueue中，这两个方法没有任何区别)。
poll()和peek()都是取头元素节点，区别在于前者会删除元素，后者不会。

BlockingQueue：阻塞队列

上面提到的队列都是单向队列，有些场景下我们需要双向队列，比如说我们要求队列中相邻的元素不能相同，这时候新插入元素时，就要和上一次插入的做对比，这时候就可以用到双向队列中的addFrist和getFrist来实现。

Map

1） HashMap

底层使用哈希表实现

2) TreeMap

底层使用红黑树实现

如何决定使用 HashMap 还是 TreeMap？

image.png
3） HashMap 底层实现

扩容机制：当hashMap put时，先查询hashMap 数组长度，当hashmap的size超过阈值（0.75，hasnMap默认初始化时长度为16）时，扩容；扩容是指，先建一个数组，数组长度为原有长度*2，然后再把原先数组中的值，重新添加到新的数组中；

hash算法：先对key取hashcode值，然后为了效率并不是直接取模，而是与 hashMap长度-1 做& 运算（这也就是HashMap的长度为什么要是2的n次方的原因）

4） ConcurrentHashMap VS HashMap
image.png

线程1 执行（Entry<K,V> next = e.next;）后，读取了3 和 next=7之后 线程时间片用完，线程挂起，调用线程2

线程2 完整的执行整个rehash操作，使hashmap的3位置链变成了7->3，1位置链变成了5->null（jdk1.7中hashmap的rehash用的是头插法）

image.png

第一次循环：把刚才读取到的3插入newTable的位置3，进入下一次循环，同时next=7
第二次循环：获取7并且继续插入位置3，同时由于线程2把7.next变成了3（7->3），所以下一次循环还是3，next=3
第三次循环：获取

继续执行线程1 的循环操作，采用头插法，先设置key==7的entry，然后再设置key==3的entry，这时候key==3的next引用是key==7（头插法，后插入的总是在头部），这样就形成了循环链表，那下次只要get 或者put操作的key hash 落到这个链表上，就会陷入死循环，容易导致cpu 100%

image.png

如果扩容前相邻的两个Entry在扩容后还是分配到table的相同位置上，就会出现死循环的BUG

总结：
HashMap是线程不安全的，其主要体现：
1.在jdk1.7中，在多线程环境下，扩容时会造成环形链或数据丢失。
2.在jdk1.8中，在多线程环境下，会发生数据覆盖的情况。

总结
其实可以看出JDK1.8版本的ConcurrentHashMap的数据结构已经接近HashMap，相对而言，ConcurrentHashMap只是增加了同步的操作来控制并发，从JDK1.7版本的ReentrantLock+Segment+HashEntry，到JDK1.8版本中synchronized+CAS+HashEntry+红黑树。

  1. 数据结构：取消了Segment分段锁的数据结构，取而代之的是数组+链表+红黑树的结构。
  2. 保证线程安全机制：JDK1.7采用segment的分段锁机制实现线程安全，其中segment继承自ReentrantLock。JDK1.8采用CAS+Synchronized保证线程安全。
  3. 锁的粒度：原来是对需要进行数据操作的Segment加锁，现调整为对每个数组元素加锁（Node）。**对Segment加锁，segments数（并发数）在初始化后是不能扩容的，所以对Node加锁后，锁的粒度更细，可以支持更大的并发
  4. 链表转化为红黑树：定位结点的hash算法简化会带来弊端，Hash冲突加剧，因此在链表节点数量大于8时，会将链表转化为红黑树进行存储。
  5. 查询时间复杂度：从原来的遍历链表O(n)，变成遍历红黑树O(logN)。
上一篇 下一篇

猜你喜欢

热点阅读