【Java】集合

【Java】集合

Java中的集合包括:实现了Collection接口的类、实现了Map接口的类。

Java.util.Collection是一个集合接口,提供了对集合对象进行基本操作的通用接口方法,Collection接口的意义是为各种具体的集合提供最大化的统一操作方式。

 1. Collection的继承实现关系:

Collection 集合主要集合类:

实现List接口的集合类:

List 接口允许内容重复

1. ArrayList 

1. 实现了List接口,内部实现是通过数组结构实现存储,其本质是一个顺序存储的线性表
2. 默认初始化容量为10,当超过数组大小就创建一个新的数组,扩容为1.5倍+1扩容。10-->16
2. 随机访问效率高(通过角标直接访问)(在内存中连续存储)
3. 插入和删除都会影响其他元素的位置,下标改变(循环输出或迭代时注意),效率低


有三个构造函数:
Arraylist()构造一个初始化容量为10的空列表
Arraylist(int  initialCapacity)构造一个指定容量列表的空列表
Arraylist(Collection<? extends E> c)构造一个包含指定collection元素的列表,按迭代器返回它们的顺序

常用方法:
list.forEach(System.out::print);
list.hashCode();
list.iterator();
list.toArray();
list.clear();

2. LinkedList :集合链表

1. 实现了List接口,内存结构是双向链表存储
2. 没有扩容机制,随意在链表头或尾部插入和删除
3. 链式存储结构的插入和删除效率高,不影响其他元素的位置
4. 随机访问效率低,需要从头依次访问

 3. Vector 

1. 在内存中顺序存储,默认初始化容量为10,扩容为1倍扩容
2. 比ArrayList多了同步机制,效率较低,线程安全
3. 如果Vector定义为Object类型,则可以存放任意类型,该集合已弃用

4. Stack: 继承Vector 使用概念低

1. 底层是通过数组实现的
2. 继承了AbstractList、实现了Enumeration、List、ListIterator等接口
3. 线程安全的。使用场景比如说倒序输出、XML语法检查

实现Set接口的集合类:

Set 不允许内容重复

因为set中不允许相同对象出现,所以添加对象需要比较两次,hashcode、equals,一次比较hashcode是否存在,一次比较equals,也就是对象是否存在。因为,hashcode的计算方法并不能保证唯一性,可能通过权重、或其他方法计算,并不能保证唯一性,所以存储时需要equals

1.HashSet : 继承AbstractSet,并实现Set接口

HashSet的底层使用通过HashMap,所以基本原理跟 HashMap 类似,使用 Map 保存数据

2. TreeSet :

TreeSet是一个有序的集合,它的作用是提供有序的Set集合。它继承了AbstractSet抽象类,实现了NavigableSet<E>,Cloneable,Serializable接口。TreeSet是基于TreeMap实现的,

TreeSet的元素支持2种排序方式:自然排序或者根据提供的Comparator进行排序

使用TreeSet 需要自定义类实现Comparable接口,并重写接口中的compareTo方法
compareTo()返回值写死为0、1、-1,表示只存储一个元素、按顺序存储、逆序存储

实现Queue接口的集合类:

在新增的Concurrent包中,BlockingQueue(阻塞队列) 很好的解决了多线程中,如何高效安全“传输”数据的问题。通过这些高效并且线程安全的队列类,为我们快速搭建高质量的多线程程序带来极大的便利。
BlockingQueue不仅实现了一个完整队列所具有的基本功能,同时在多线程环境下,他还自动管理了多线间的自动等待于唤醒功能,从而使得程序员可以忽略这些细节,关注更高级的功能.

1.  ArrayBlockingQueue

1. 基于数组的阻塞队列实现,内部维护了一个定长数组,以便缓存队列中的数据对象,
2. 除了一个定长数组外,ArrayBlockingQueue内部还保存着两个整形变量,分别标识着队列的头部和尾部在数组中的位置。 
3. 创建时,可以控制对象的内部锁是否采用公平锁,默认采用非公平锁
4. 放入数据和消费者获取数据,都是共用同一个锁对象

2. LinkedBlockingQueue

1. 基于链表的阻塞队列,其内部也维持着一个数据缓冲队列(该队列由一个链表构成)
2. 如果没有在初始化时,指定大小,默认为无限大。
3. 生产者端和消费者端分别采用了 独立的锁 来控制数据同步:分离锁

原理:
当生产者往队列中放入一个数据时,队列会从生产者手中获取数据,并缓存在队列内部,而生产者立即返回;只有当队列缓冲区达到最大值缓存容量时(LinkedBlockingQueue可以通过构造函数指定该值),才会阻塞生产者队列,直到消费者从队列中消费掉一份数据,生产者线程会被唤醒,反之对于消费者这端的处理也基于同样的原理。而LinkedBlockingQueue之所以能够高效的处理并发数据,还因为其对于生产者端和消费者端分别采用了独立的锁来控制数据同步,这也意味着在高并发的情况下生产者和消费者可以并行地操作队列中的数据,以此来提高整个队列的并发性能。 
作为开发者,我们需要注意的是,如果构造一个LinkedBlockingQueue对象,而没有指定其容量大小,LinkedBlockingQueue会默认一个类似无限大小的容量(Integer.MAX_VALUE),这样的话,如果生产者的速度一旦大于消费者的速度,也许还没有等到队列满阻塞产生,系统内存就有可能已被消耗殆尽了

两者的区别:

ArrayBlockingQueue 和 LinkedBlockingQueue (以 生产者 和 消费者为例分析)

锁:前者队列头和队列尾 维护同一个锁,后者使用了分离锁。
操作:前者在添加和删除操作时,不产生或销毁任何的对象实例,后者会生成一个额外的 Node 对象。高并发大批量数据处理中,影响gc,内存容易爆满。

3. PriorityBlockingQueue:

1. 基于优先级的阻塞队列(优先级的判断通过构造函数传入的Compator对象来决定)
2. 不会阻塞数据生产者,只会阻塞数据的消费者(生产者的速度不能快于消费者)
3. 在实现PriorityBlockingQueue时,内部控制线程同步的锁采用的是公平锁

4. SynchronousQueue

1. 一种无缓冲的等待队列,类似于无中介的直接交易,有点像原始社会中的生产者和消费者,
2. 声明有两种不同的方式,它们之间有着不太一样的行为。公平模式和非公平模式的区别: 
   公平模式:采用公平锁,并配合一个FIFO队列来阻塞多余的生产者和消费者,实现公平策略;
   非公平模式(SynchronousQueue默认):非公平锁,LIFO队列来管理多余的生产者和消费者

非公平模式的问题:如果生产者和消费者的处理速度有差距,则很容易出现饥渴的情况,即可能有某些生产者或者是消费者的数据永远都得不到处理。 

原理:
生产者拿着产品去集市销售给产品的最终消费者,而消费者必须亲自去集市找到所要商品的直接生产者,如果一方没有找到合适的目标,那么对不起,大家都在集市等待。相对于有缓冲的BlockingQueue来说,少了一个中间经销商的环节(缓冲区),如果有经销商,生产者直接把产品批发给经销商,而无需在意经销商最终会将这些产品卖给那些消费者,由于经销商可以库存一部分商品,因此相对于直接交易模式,总体来说采用中间经销商的模式会吞吐量高一些(可以批量买卖);但另一方面,又因为经销商的引入,使得产品从生产者到消费者中间增加了额外的交易环节,单个产品的及时响应性能可能会降低。 

6. ConcurrentLinkedQueue:

1. 基于链接节点的无界并发deque(deque是双端队列),并发插入
2. 删除和访问可以跨多个线程安全执行,不允许null元素

9. enumeration 枚举,相当于迭代器:

这种传统接口已被迭代器取代,还是使用在诸如Vector和Properties这些传统类所定义的方法中

 2. Map的继承实现关系:

1. HashMap 

1. 默认初始化容量为16,扩容为2倍.(初始化大小是 16,扩容因子默认0.75)
2. 未进行同步考虑,是线程不安全的。
3. key、value都可以为null,判断key=null;的键是否存在,应该用containsKey方法,并不能用get方法。因为get返回null,即可表示 null键存在 也可表示 此键不存在
4. 采用快速失败机制(fast-fail): 依靠 modCount expectedModCount (实现)

使用头插法,以为设计人员认为新插入的内容被使用的概率高。
HashMap 如何需要重新计算哈希值?
(h = key.hashCode()) ^ (h>>>) & (m-1)
1. h = key.hashCode()  # 得到 key 的哈希值
2. h >>> 16            # 右击将高位特征保留下来 0000.....1101
3. x = h ^ (h >>> 16)  # 将 高位 和 低位 特征保留下来
4. x & (2^n-1)         # 槽位-1 得到更多的1(特征值) 


>>  :算术右移运算符,也称带符号右移。用最高位填充移位后左侧的空位
>>> :逻辑右移运算符,也称无符号右移。只对位进行操作,用0填充左侧的空位
参考:https://www.cnblogs.com/zxporz/p/11204233.html

2. HashTable 

1. 默认初始化容量为11,扩容为2倍
2. 比Hashmap多了同步机制,是线程安全的,任何操作都对整张哈希表加锁,多线程中效率低
3. key、value都不可为null,存储的key为对象的hashcode, 已弃用

HashMap 和 HashTable的区别:

1) 继承不同
HashMap:     AbstractMap implements Map
HashTable :  Dictionary implements Map
2) 同步问题
HashMap   方法在缺省的情况下是不同步的,需要自己添加同步
   Map map = Collections.synchronizedMap(new HashMap<>());
HashTable 方法是同步(sychronizedHashMap)的
3) null 的问题:
HashMap中,null可以作为键,这样的键只有一个,可以有多个value=null
HashTable中,key、value都不允许出现null值
4) 遍历方式不同:
HashTable、HashMap都使用了Iterator,
HashTable 还支持了Enumeration的方式,
5) 哈希值不同:
HashTable直接使用对象的hashcode,HashMap重新计算hash值
{
HashMap (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16) //重新计算哈希值
(n - 1) & hash  //计算数组槽位
}
6) 初始化和扩容:
HashTable和HashMap内部实现都是数组初始化大小和扩容方式。
HashTable的Hash数组默认为11,扩容为old*2+1;---》23
HashMap的hash数组默认值为16,而且一定是2的指数扩容,扩容因子为0.75。16---32

3. concurrentHashMap

1. 提供一组和HashMap功能相同但线程安全的方法
2. 将Hash表分为16桶(segment),每次只对需要的桶加锁
3. 在JDK1.8之后,可以做到读取不加锁,内部结构可以在写操作时将锁粒度尽量的小,锁区变小
4. ConcurrentHashMap并不再是分段锁,而是更细粒度的锁,只是在修改map时对链表头加锁
   通过(红黑树根)实现

Iterator:迭代器

常用Iterator中的方法:hasNext()、next()、
remove()方法调用的是remove(int index);而不是remove(Object o); 

ArrayList中的迭代器使用:
public static void main(String[] args){
        List<String> list=new ArrayList<>();
        list.add("abc");
        list.add("edf");
        list.add("ghi");
        for(Iterator<String> it=list.iterator();it.hasNext();){
            System.out.println(it.next());
        }
}
迭代器的实现原理:
    在ArrayList内部定义了一个内部类Itr,该类实现了Iterator接口。
  在Itr中,有三个变量分别是
  cursor:表示下一个元素的索引位置   (hasNext判断  cursor是不是等于size)
  lastRet:表示上一个元素的索引位置    (用来返回当前元素)
  expectModCount:预期被修改的次数

对于线程不安全的集合,使用Iterator快速失败机制:
在集合中存在一个modCount记录集合的修改次数,在Iterator中也存在一个expectModCount用来记录集合的修改次数,当在Iterator的遍历中,有线程修改了集合,modCount会+1,此时两者不相等,抛出java.util.ConcurrentModificationException异常,如果是在Iterator中修改了集合结构,会同时修改modCount、expectModCount,不会抛出异常
 /**
     * An optimized version of AbstractList.Itr
     */
    private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;
 
        public boolean hasNext() {
            return cursor != size;
        }
        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }
 
        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();
 
            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
 
        @Override
        @SuppressWarnings("unchecked")
        public void forEachRemaining(Consumer<? super E> consumer) {
            Objects.requireNonNull(consumer);
            final int size = ArrayList.this.size;
            int i = cursor;
            if (i >= size) {
                return;
            }
            final Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length) {
                throw new ConcurrentModificationException();
            }
            while (i != size && modCount == expectedModCount) {
                consumer.accept((E) elementData[i++]);
            }
            // update once at end of iteration to reduce heap write traffic
            cursor = i;
            lastRet = i - 1;
            checkForComodification();
        }
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }
Iterator只支持在遍历的时候,删除元素,如果要在遍历时,添加元素,该怎么办呢?

这时就引出了ListIterator,可以用于在遍历的过程中,修改元素,正反遍历,返回当前位置。(添加元素通过当前元素比较)

重点:HashMap为什么线程不安全:

HashMap在并发时可能出现的问题主要是两方面:

1.首先如果多个线程同时使用put方法添加元素,而且假设正好存在两个put的key发生了碰撞(hash值一样),那么根据HashMap的实现,这两个key会添加到数组的同一个位置,这样最终就会发生其中一个线程的put的数据被覆盖。

2. 如果多个线程同时检测到元素个数超过数组大小*loadFactor,这样就会发生多个线程同时对Node数组进行扩容,都在重新计算元素位置以及复制数据,但是最终只有一个线程扩容后的数组会赋给table,也就是说其他线程的都会丢失,并且各自线程put的数据也丢失。

关于HashMap线程不安全这一点,《Java并发编程的艺术》一书中是这样说的:

HashMap在并发执行put操作时会引起死循环,导致CPU利用率接近100%。因为多线程会导致HashMap的Node链表形成环形数据结构,一旦形成环形数据结构,Node的next节点永远不为空,就会在获取Node时产生死循环。(rehash可能导致环形数据结构)

三个方法避免:使用HashTable、使用synchronized修饰方法、使用concurrentHashMap。

集合结构图:

continue….

0 0 vote
Article Rating
Subscribe
提醒
guest
0 评论
Inline Feedbacks
View all comments