java集合容器的特点

一.ArrayList的优缺点&＃xff1a;内存用数组来存储元素&＃xff0c; 且内部存储的元素可重复&＃xff0c;可以存储null元素。且元素的存入取出顺序相同。

优点&＃xff1a;查询快&＃xff0c;知道索引可以快速查找到元素。在所有容器中ArrayList是查询最快的。

缺点&＃xff1a;增删慢。因为数组满了以后需要扩容&＃xff0c;就是先创建一个原来数组的1.5倍的数组&＃xff0c;然后把之前的元素拷贝到一个新的数组中来。这样添加元素的效率就慢慢变低了。数据越多&＃xff0c;删除也变得慢。

容量和大小&＃xff1a;有三种构造方法

1.无参构造方法&＃xff1a;数组的初始容量是10

2.指定数组的初始容量

3.构造方法&＃xff08;传入一个集合&＃xff09;&＃xff1a;可以将另一个集合中的元素的元素插入到ArrayList中&＃xff0c;数组的初始容量就是该集合的大小。

&＃xff08;2&＃xff09;ArrayList里的常用方法&＃xff1a;

1.查询操作&＃xff1a;get(int index) indexof(Object o) Iteraor() size() isEmpty()

2.修改操作&＃xff1a;add(E element) set(int index,E element) remove(int index)

3.批量操作&＃xff1a;clear() stream()

二.Linkedlist 链式链表

特点&＃xff1a;1.有序性&＃xff0c;元素存入的顺序和取出的顺序一致

2.可重复&＃xff0c;可以存入重复的值

3.可以为null&＃xff0c;可以存储为null的值

优点&＃xff1a;增删快&＃xff0c;增加时只需记录前后节点是谁&＃xff0c;删除时改变前后的节点记录

缺点&＃xff1a;查询慢&＃xff0c;必须从头节开始查找

Linkedlist常用方法分类

1.查询操作&＃xff1a;getFirst() getLast() size() isEmpty()

2.修改操作&＃xff1a;add(E e) addFirst(E e)

3.批量操作&＃xff1a;listIterator() clear() stream()

但缺少删除数据的方法&＃xff0c;Linkedlist删除数据一般是找到匹配项后使用迭代器的rmove方法删除

                     ArrayList                                                    Linkedlist

数据结构             数组                                                                       链表

查询速度             快                                                                            慢

增删速度             慢                                                                            快

内存空间             小&＃xff0c;连续                                                                 大&＃xff0c;不连续

应用场景             查询较多                                                                 增删较多

三&＃xff0c;HashMap

HashMap是以Key-value来存储数据保存在数组中&＃xff0c;默认的初始容量为16。

1.元素是无序的&＃xff0c;但是根据Key计算出的。

2.key可以为null并且哈希值为零。

3.key不可以相同&＃xff0c;重复的key&＃xff0c;对应的新的值将会覆盖旧值。

哈希冲突&＃xff1a;是不同的key产生了相同的哈希值&＃xff0c;发送冲突的原因是哈希值的取值范围&＃xff0c;更大的哈希值意味着相同的概率越小&＃xff0c;但也需要更大的存储空间。

“树化”是当链表的长度大于8且数组的容量大于等于64时&＃xff0c;将链表转换为红黑树&＃xff0c;当红黑树中的节点小于6个时&＃xff0c;红黑树将转换为链表&＃xff0c;这个过程叫做“链化”&＃xff0c;在插入元素时&＃xff0c;直接在尾部插入&＃xff0c;但红黑树还要计算节点的位置&＃xff0c;因此相互转化是很好的互补。

扩容&＃xff1a;当前元素个数超越临界值时&＃xff0c;HashMap就需要扩容&＃xff0c;扩容后的容量是之前的两倍

                                       临界值&＃61;容量*负载因子

频繁扩容很容易影响HashMap的性能&＃xff0c;所以设置合适的初始容量和负载因子很重要。

HashMap常用的方法&＃xff1a;

1.查询操作&＃xff1a;size()      isEmpty()     *get(O  e )       Containskey(O e)

2.修改操作&＃xff1a;*put(K,V)              remove(O e)

3.批量操作&＃xff1a;keyset()                clear()

四&＃xff0c;LinkedHashMap  &＃xff08;链式哈希映射&＃xff09;

它扩展自哈希映射&＃xff0c;有序的

特点&＃xff1a;元素的排序顺序

1.元素的添加顺序&＃xff1a;元素添加的顺序和元素取出的顺序一致

2.元素的访问顺序&＃xff1a;被访问过的元素将会被排到链表的尾部

LinkedHashMap常用的方法分类

1.查询操作&＃xff1a;*size()      *isEmpty()          *get(O e)       *ContainsKey(O e)

2.修改操作:   *put(K,v)      *remove(O e)

3.批量删除&＃xff1a;*keyset()      *clear()

五&＃xff0c;TreeMap  &＃xff08;二叉树映射&＃xff09;

 以二叉树的形式来存储元素&＃xff0c;二叉树是红黑树的类型&＃xff0c;红黑树拥有自平衡的特点&＃xff0c;根据key的值进行排序

特点&＃xff1a;

1.对key的排序       2.无序      3.key不可以为null      4.key唯一

优点&＃xff1a;对key排序                缺点&＃xff1a;无序

TreeMap的常用方法&＃xff1a;

1.查询操作&＃xff1a;*size()  *isEmpty()   *get(Object)   *containskey(Object)

2.修改操作&＃xff1a;*put(K,V)           *remove(Object)

3.批量删除&＃xff1a;*keyset()  *clear()   *descendingMap()

六&＃xff0c;Hashset

内部使用HashMap来储存元素&＃xff0c;所以是无序的&＃xff0c;创建Hashset就是创建了一个HashMap。在存储元素的时候将key当做value使用&＃xff0c;value再用一个统一的值进行填充即可。这个值便在HashMap内部PRESENT是Object类型。

元素取出的顺序&＃xff0c;数组从下标0开始

特点&＃xff1a;1.无序。    2.值唯一。 3.值可以为null。

优点&＃xff1a;增删改查快。               缺点&＃xff1a;无序。

HashSet常用方法&＃xff1a;

1.查询操作&＃xff1a;*size()  *isEmpty()     *contains()

2.修改操作&＃xff1a;*add()   *remove(Object o)    

3.批量删除&＃xff1a;*iterater()    *clear().     

HashMap                                   HashSet

key是键&＃xff0c;value是值。             用原来Key的位置来存储元素&＃xff0c;value用统一的值进行填充

七.LinkedHashSet(链式哈希集合)

它扩展至HashSet&＃xff0c;但它的内部使用的是LinkedHashMap&＃xff0c;由于LinkedHashMap是有序的&＃xff0c;所以

LinkedHashMap也是有序的。使用key值来存储元素&＃xff0c;使用值的位置为唯一的值。

LinkedHashSet常用方法分类

1.查询操作&＃xff1a;*size()    *isEmpty()

2.修改操作&＃xff1a;*add()      *remove()

3. 批量删除&＃xff1a;*iterater()      *clear()

                              LinkedHashMap                     LinkedHashSet

存储方式           key是键&＃xff0c;value是值                 把key当做存储value的空间&＃xff0c;value用统一的值填充

排序顺序         添加顺序&＃xff0c;访问顺序                   添加顺序

八.TreeSet

 内部使用的是TreeMap&＃xff0c;对元素进行自然排序&＃xff0c;自然排序是通过元素的comparaTo方法完成的&＃xff0c;自定义排序则需要实现comparaTo接口。

特点&＃xff1a;1.对值排序    2.无序    3.值不可以为null   4.值唯一

优点&＃xff1a;对值排序           特点&＃xff1a;无序

TreeSet的常用方法&＃xff1a;

1.查询操作&＃xff1a;  *size()      *isEmpty()     *contans(Object O)

2.修改操作&＃xff1a;*add()     *remove(Object O)

3.删除操作&＃xff1a;*iterator()      *clear()

                      HashSet                                              LinkedHashSet                                        TreeSet

特点&＃xff1a;         添加查询快                            添加&＃xff0c;删除&＃xff0c;修改&＃xff0c;有序                                    排序

适用问题&＃xff1a;   添加查询性能最佳。            当需要存入取出的顺序一致时。             对元素进行排序

快速失败机制&＃xff08;fail-fast&＃xff09;

        它能够防止多个线程并发修改同一个容器的内容&＃xff0c;如果发生了并发修改的情况那么就会触发"快速失败"的机制&＃xff0c;也就是抛出并发修改异常。

1.一种容器的保护机制

2.防止多线程同时修改一个容器

3.容器若被修改将抛出异常

       在容器中定义一个modcount属性&＃xff1a;用来记录容器修改的次数&＃xff0c;初始值为零&＃xff0c;只要容器有被操作就会&＃43;&＃43;&＃xff0c;在每次获取迭代器的时候&＃xff0c;迭代器的时候&＃xff0c;迭代器会获取modcount的值&＃xff0c;如果两值不相等&＃xff0c;就说明有其他的线程修改了容器&＃xff0c;并抛出修改异常。

解决方法&＃xff1a;使用线程安全的容器类便可以起到线程安全。

CopyOnNriteArrayList类   ConCurrentHashMap类   CopyOnWriterArrayset类

CopyCurrentHashMap类的特点及优点缺点

1.同步&＃xff1a;给数组中的每一个头节点加锁&＃xff0c;这样一来并发度从原来的1增长到16&＃xff0c;理论上数组有多长&＃xff0c;并发度就有多少&＃xff0c;并发度上去了&＃xff0c;效率也就上去了。

2.统计元素的个数&＃xff1a;在并发度大的情况下不能在使用一个属性来统计元数对个数&＃xff0c;原因是多个线程同时来读取属性的值&＃xff0c;然后再对其&＃43;&＃43;&＃xff0c;再同时赋给属性&＃xff0c;这样一来就产生了线程安全问题&＃xff0c;明明有很多线程对其&＃43;&＃43;&＃xff0c;结果却是加一。

      为了解决这个线程安全问题&＃xff0c;我们给它加锁&＃xff0c;这却使得刚刚提升起来的效率又降下来了&＃xff0c;获取锁&＃xff0c;释放锁耗时资源&＃xff0c;于是设计者使用比锁轻量的CAS&＃xff0c;使用CAS更新属性时&＃xff0c;同一时刻也只有一个线程能更新成功&＃xff0c;其余线程更新失败&＃xff0c;更新失败的线程再无限循环更新&＃xff0c;只到更新成功。

但是却没高到那里去&＃xff0c;于是设计者又提出&＃xff0c;不妨新增一个数组&＃xff0c;让失败的线程先把值累加到数组中去&＃xff0c;在此之前各线程需要知道自己里面加的位置&＃xff0c;位置的计算方式和HashMap是一样的&＃xff0c;取一个随机数&＃xff0c;当做是哈希值&&＃xff08;数组长度减一&＃xff09;&＃xff0c;这个操作等同于数组操作取余&＃xff0c;得到的余数就是要累加的位置&＃xff08;下标&＃xff09;累加失败的线程再循环累加&＃xff0c;直到累加成功&＃xff0c;最终元素个数由单个属性和数组中累加获得。

3.多线程协同扩容&＃xff1a;从后往前&＃xff0c;每个线程负责一段数据的迁移工作&＃xff0c;一段有多长&＃xff1f;

关注一下源码。

4.Key和value是不能为空的。

5.区别&＃xff1a;                     HashMap                              ConCrrentHashMap 

线程是否安全             不安全                                             安全

扩容                           单线程扩容                                 多线程扩容

统计个数                      size                                baseCont&＃43;ConterCell[  ]

key和value能否为空      能                                               不能

6.常用方法&＃xff1a;

(1)查询操作&＃xff1a; size()        isEmpty()         get(O e)      Containskey(O e)

(2)修改操作&＃xff1a;put(K,V)     remove(O e) 

(3)批量操作&＃xff1a;keyset()      clear()

特点&＃xff1a;1.无序  2.key唯一  3.key与value不可为null  4.线程安全

优点&＃xff1a;增删改查快

缺点&＃xff1a;无序

为什么ConcurrentHashMap只给头结点加锁就可以保证线程安全呢&＃xff1f;

答&＃xff1a;Concurrent只针对位置加锁&＃xff0c;它不针对具体元素加锁&＃xff0c;头结点之所以成为被锁的对象&＃xff0c;是因为头结点正好在数组的位置上&＃xff0c;它下面的节点都是链在它身后的&＃xff0c;另外&＃xff0c;头结点是不固定的&＃xff0c;所以只针对位置加锁&＃xff0c;而增删改查都是通过头结点来进行的。

      所以只要入口每次只进一个线程&＃xff0c;就可以保证数据的安全&＃xff0c;因此ConcurrentHashMap只给头节点加速就可以了。

总结

Q:为什么只需要给头节点加锁&＃xff1f;

A:加锁只针对位置&＃xff0c;不针对具体元素。位置上正好放的是头结点&＃xff0c;且增删改查都是以头结点作为入口。所以&＃xff0c;只需要给头节点加锁即可。