JAVA之集合总结
文章目录
JAVA集合:
一、JAVA集合可以分为两大体系
1. Collection:主要由List、Set、Queue接口组成,List代表有序、重复的集合,Set代表无序、不可重复的集合,Queue代表一种队列集合实现。 java.util.Collection包。
2. Map:则代表具有映射关系的键值对集合。 java.util.Map包。
A. java.util.Collection 下的接口和继承类关系简易结构图,下图中1为接口,2为实现类

B. java.util.Map下的接口和继承类关系简易结构图,下图中1为接口,2为抽象类,3为实现类

JAVA集合框架中主要封装的是典型的数据结构和算法,如动态数组、双向链表、队列、栈、Set、Map等。
二、将集合框架挖掘处理,可以分为以下几个部分:
A. 数据结构
1. List列表
2. Queue队列
3. Deque双端队列
4. Set集合
5. Map映射
B. 比较器
1. Comparator比较器
2. Comparable排序接口
C. 算法
1. Collections常用算法类
2. Arrays静态数组的排序、查找算法
D. 迭代器
1. Iterator通用迭代器
2. ListIterator针对List特化的迭代器
三、列表(List)
List 集合的特点就是存取有序,可以存储重复的元素。
List主要实现类(ArrayList、 LinkedList、 Vector、 Stack)
A. ArrayList
ArrayList底层是一个动态数组结构,允许为null,非线程安全。插入、删除慢,查询快。
1. 初始化:
1. 如果参数等于0,则将数组初始化为一个空数组。
2. 如果参数不等于0,则将数组初始化为一个容量为10的数组。
2. 扩容:
当数组的大小大于初始容量的时候,就会进行扩容,新的容量为旧的容量的1.5倍(oldCapacity + (oldCapacity >> 1))。
1. 新建一个是原数组1.5倍的新数组。
2. 把原数组copy到新数组中。
3. 常用方法:
1. void add(E e): 在尾端添加一个元素。
2. void add(int index, E e):指定索引添加一个元素。
3. int remove(int index):删除指定索引的元素。
4. E get(int index):获取指定索引的元素。
5. int size():大小
B. LinkedList
LinkedList底层是一个双向链表结构,允许为null,非线程安全。 插入、删除快,查询慢。
1. 常用方法:
1.1. boolean add(E e):在链表尾部添加一个元素,返回boolean。
1.2. void addFirst(E e):在链表头部添加一个元素。
1.3. addLast(E e):在链表尾部添加一个元素。
1.4. void add(int index, E element):在指定位置插入一个元素。
1.5. boolean remove(Object o):移除指定的元素。
1.6. E remove(int index):移除指定位置的元素。
1.7. E removeFirst():移除第一个元素。
1.8. E removeLast():移除最后一个元素。
1.9. E get(int index):获取指定位置的元素。
1.10. E getFirst():获取第一个元素。
1.11. E getLast():获取最后一个元素。
C. Vector
Vector早在jdk1.1就引入进来,现在很少使用。
Vector底层是一个动态数组结构,Vector允许同步访问。
Vector中方法都加了synchronized,线程安全,效率低。
Vector初始容量为10。
扩容:
1.1. 获取原始容量。
1.2. 若容量增加系数大于0,则(新增容量 = 原始容量 + 容量增加系数),否则(新增容量 = 原始容量 * 2)。
1.3. 若扩容后,容量仍然小,则新容量改为实际需要最小容量的大小。
1.4. 若扩容后,新数组的长度比虚拟机能够提供给数组的最大存储空间大,则将新数组长度更改为最大正数。
1.5. 按照新的容量创建一个新数组,然后将原数组中的内容copy到新数组中。
D. Stack
Stack(栈),是Vector的一个子类,扩容与Vector一样,本质也是一个动态数组结构,不同的是,它的数据结构是先进先出的。
1. 常用方法:
1. boolean empty():判断stack是否为空。
2. E push(E object):将元素压入栈。
3. synchronized E peek():返回栈顶端的元素。
4. synchronized E pop():弹出栈顶的元素。
5. synchronized int search(Object o):返回最靠近顶端的目标元素到顶端的距离。
四、队列(Queue)
Queue是一个队列集合,队列通常是指“先进先出(FIFO)的容器”。
新元素插入(offer)到队列的尾部,访问元素(poll)操作会返回队列头部的元素。
通常队列中不允许随机访问队列中的元素。
Queue主要实现类(ArrayDeque、 LinkedList、 PriorityQueue):
A. ArrayDeque
ArrayDeque继承自Deque接口,Deque继承自Queue,Queue是队列;Deque是双端队列、可以从前或后插入、取出元素,非线程安全。
ArrayDeque是一个用循环数组实现的双端队列,内部使用数组进行元素存储,不允许存储null值(因为系统根据某个位置是否为null来判断元素的存在)。
ArrayDeque有两个指针,head用于指向数组中头部下标,tail用于指向数组中尾部下标,队列的容量最小为8,而且必须是2的幂。
ArrayDeque当作栈使用时,性能比Stack好;当作队列使用时,性能比LinkedList好。
1. 初始化:
1. 调用时若不指定容量,ArrayDeque默认初始化数组大小为16。
2. 调用时指定容量,如果指定的容量大小,小于最小值8,将容量设置为8;否则通过多次无符号右移进行最小2次幂计算。
3. 当数组容量超过int型最大范围时,直接扩容到最大容量到2^30。
2. 常用方法:
当(elements.length – 1)是2的倍数时,位与运算类似做十进制的 % 运算得到其余数。
2.1: 通过数组尾部下标进行添加,操作的是tail指针:
2.1.1. addLast:无返回值,向数组尾部添加元素,尾部下标从1、2、3、4、……、15、0,依次按照顺序存储,当达到最大值之后,返回到头部,从0开始,结果是一个循环下标。
计算tail指针:tail = (tail + 1) & (elements.length – 1);这个操作是先对尾部参数进行 加1 处理,然后结合数组长度通过位与运算得到尾部值。
当尾部指针(tail)等于头部指针(head)时(tail == head),数组下标越界,进行扩容。
2.1.2. offerLast:调用了addLast方法,两者不同之处,offerLast有返回值,如果添加成功,则返回true,反之,抛出异常。
2.2: 通过数组头部下标进行添加,操作的是head指针:
2.2.1. addFirst:无返回值,向数组头部添加元素。头部下标从15、14、13、12、……、1、0,依次从大到小按照顺序存储,当到达最小值后,返回到头部,从0开始,结果也是一个循环下标。
计算head指针:head = (head – 1) & (elements.length – 1);这个操作是先对头部参数进行 减1 处理,然后结合数组长度通过位与运算得到尾部值。
当头部指针(head)等于尾部指针(tail)时(head == tail),数组下标越界,进行扩容。
2.2.2. offerFirst:调用了addFirst方法,两者不同之处,offerFirst有返回值,如果添加成功,则返回true,反之,抛出异常。
2.3: 通过数组尾部下标进行删除,操作的是tail指针:
2.3.1. pollLast:删除尾部元素。
计算tail指针:tail = (tail – 1) & (elements.length – 1);
pollLast方法是先通过数组尾部计算数组元素下标,判断元素是否存在,如果不存在,直接返回null,如果存在,将其设为null,并返回元素。
2.3.2. removeLast:调用了pollLast方法,不同的是,removeLast方法删除元素失败会抛出异常。
2.4: 通过数组头部下标进行删除,操作的是head指针:
2.4.1. pollFirst:删除头部元素。
pollFirst方法是先获取数组头部元素,判断元素是否存在,如果不存在,直接返回null,如果存在,将其设为null,并返回元素。
计算head指针:head = (head + 1) & (elements.length – 1);
2.4.2. removeFirst:调用了pollFirst方法,不同的是,removeFirst方法删除元素失败会抛出异常。
2.5: 通过数组尾部下标进行查询,操作的是tail指针:
2.5.1. peekLast:通过数组尾部获取数组元素,可能返回null。
2.5.2. getLast:通过数组尾部获取数组元素,如果返回null则抛出异常。
2.6: 通过数组头部下标进行查询,操作的是head指针:
2.6.1. peekFirst:通过数组头部获取数组元素,可能返回null。
2.6.2. getFirst:通过数组头部获取数组元素,如果返回null则抛出异常。
3. 扩容:
1. 记录head指针的位置。
2. 把新数组的大小扩为原始数组的2倍,int newCapacity = n << 1。
3. 复制head头部索引至数组末端的元素到新数组。
4. 复制head左边的元素到新数组。
ArrayDeque 扩容见下图
B. LinkedList
LinkedList是List接口的实现类,也是Deque的实现类,底层是一种双向链表的数据结构,LinkedList同时实现了Stack、Queue、PriorityQueue的所有功能。详细用法见上。
1. ArrayDeque 与 LinkedList 的区别:
1. 数据结构不同,ArrayDeque底层基于循环数组实现,LinkedList底层基于双向链表实现。
2. ArrayDeque不允许插入null,LinkedList允许插入null,两者都是非线程安全的。
3. LinkedList底层基于双向链表实现,内存开销高于ArrayDeque,在小数据量的时候,两者效率差别不大;在大数据量的时候,ArrayDeque性能高于LinkedList。
C. PriorityQueue
PriorityQueue 是一种无界的,非线程安全,并拥有优先级的队列(自然排序)。
PriorityQueue底层采用动态数组存储数据,采用二叉小顶堆数据结构保证优先级序列。
PriorityQueue队列不允许使用null元素,存储的元素要求必须是可比较的对象,如果不是就必须明确指定比较器。
二叉小顶堆:
如果排序规则为从小到大排序,则表示堆的完全二叉树中,每个父结点的值都要小于子结点的值。
二叉大顶堆:
如果排序规则为从大到小排序,则表示堆的完全二叉树中,每个父结点的值都要大于子结点的值。
1. 初始化:
PriorityQueue数组默认大小11。
2. 添加数据(offer):
首先确保数组长度是够的,如果不够,自动扩容。
第一次添加,直接添加到第一个位置即可。
否则将其添加到最后一个位置,但同时向上调整,直至满足二叉小顶堆的性质。
删除元素也需要根据二叉小顶堆的性质调整元素。
3. 扩容:
如果原始长度比较小(< 64),则(newCapacity = oldCapacity +(oldCapacity +2))扩充为原始长度的2倍+2。
如果元素长度(> 64),则(newCapacity = oldCapacity + (oldCapacity >> 1))扩充为原始长度的1.5倍。
使用Arrays.copyOf方法拷贝数组。
4. 常用方法:
1. offer(E e):入列,不能添加null元素。
2. poll(E e):出列。
3. peek():获取。
五、集(Set)
Set集合的特点:元素不重复,存取无序,无下标。
Set集合的实现:基本都是基于Map中的键实现,使用Map中键不能重复、无序的特性;
Set主要实现类(HashSet、 LinkedHashSet、 TreeSet):
A. HashSet
HashSet底层是基于HashMap的key实现的,元素不可重复,存储数据无序,允许为null,非线程安全,特性同HashMap。
HashSet中的元素都存到HashMap键值对的key上面,而value是统一的值(定义一个虚拟的Object对象作为HashMap的value,将此对象定义为static final。 private static final Object PRESENT = new Object());
常用方法:
1. boolean add(E e):如果当前列表中不存在e,则将e加入列表。
2. void clear():从列表中删除所有元素。
3. boolean contains(Object j):判断列表中是否有元素j。
4. boolean remove(Object j):删除列表中的元素j。
5. int size():列表中元素的个数。
6. Iterator<E> iterator():获取当前列表的遍历器。
B. LinkedHashSet
LinkedHashSet底层也是基于LinkedHashMap的key实现的,元素不可重复,存储数据有序,允许为null,非线程安全,特性同LinkedHashMap。
C. TreeSet
TreeSet底层也是基于TreeMap的key实现的,元素不可重复,存储数据有序,特性同TreeMap。
六、映射表(Map)
Map是一个双列集合,其中保存的是键值对,键要求保持唯一性,值可以重复。
Map主要实现类(HashMap、LinkedHashMap、TreeMap、IdentityHashMap、WeakHashMap、Hashtable、Properties):
A. HashMap
HashMap继承自AbstractMap;底层存储(key, value)键值对,使用 数组+链表+红黑树 方式实现,非线程安全。
key值不可重复,HashMap最多只允许一条记录的key为null。HashMap是非线程安全的。
1. 初始化:
指定初始值大小应为2的幂,如果指定的初始值不是2的幂,则HashMap的容量为大于指定初始值的2的幂(通过多次无符号右移实现);如果不指定初始值,则默认16。
2. 扩容:
新容量 = 原始容量 * 2,(HashMap扩容时必须是2的幂)。
B. LinkedHashMap
LinkedHashMap实现与HashMap的不同之处在于,后者维护着一个运行于所有条目的双重链接列表,此链接列表定义了迭代顺序,该迭代顺序可以是插入顺序或者是访问顺序。
LinkedHashMap继承了HashMap,底层使用哈希表与双向链表来保存所有元素,其基本操作与父类HashMap操作相似。
C. TreeMap
1. TreeMap存储(key, value)键值对,底层通过红黑树(R-B tree)实现,红黑树的实现见数据结构实现。
2. TreeMap非线程安全,不允许null, key值不可重复,value允许重复,数据存储有序,默认通过key值的自然顺序进行排序。
3. TreeMap继承了NavigableMap接口,NavigableMap接口继承了SortedMap接口,可支持一系列的导航定位以及导航操作的方法,当然只是提供了接口,需要TreeMap自己去实现。
4. TreeMap实现了Cloneable接口,可被克隆,实现了Serializable接口,可序列化。
D. IdentityHashMap
1. IdentityHashMap继承自AbstractMap,是一种key值可以重复的map。
2. IdentityHashMap不是Map的通用实现,它有意违反了Map的常规协定,key和value都允许为null值,数据是无序的,非线程安全。
3. IdentityHashMap比较key值使用 == 而不是使用 equals,比较的是内存地址(允许相同的key保存进来)。
4. IdentityHashMap类利用哈希表实现Map接口,底层也是数组(没有用到链表),解决冲突的方式是计算下一个有效索引,并且将数据key和value紧挨着存放,即table[i] = key, table[i+1] = value。
如果要线程安全,可以调用 Collection.synchronizedMap(new IdentityHashMap(…)) 方法来实现。
E. WeakHashMap
WeakHashMap继承自AbstractMap,实现了Map接口。和HashMap一样,WeakHashMap也是一个散列表,它存储的内容也是键值对(key, value)映射,而且键和值都可以为null,不过WeakHashMap的键是“弱键”。
在WeakHashMap中,当某个键不再正常使用时,会被从WeakHashMap中被自动移除。
WeakHashMap实现步骤:
1. 新建WeakHashMap,将“键值对”添加到WeakHashMap中。
2. 当某“弱键”不再被其它对象引用,并被GC回收时,在GC回收该“弱键”时,这个“弱键”也同时会被添加到ReferenceQueue(queue)队列中。
3. 当下一次需要操作WeakHashMap时,会先同步table和queue。table中保存了全部的键值对,而queue中保存被GC回收的键值对,同步它们,就是删除table中被GC回收的键值对。
F. Hashtable
Hashtable的底层实现是 数组+链表,键值不能为null,与HashMap不同的是,方法都加了synchronized同步锁,是线程安全的,效率低。
HashMap与Hashtable 的区别在于HashMap允许K和V为空,而HashTable不允许K和V为空,由于HashMap非线程安全,效率高。
扩容:
默认容量为11, 扩容时新容量 = 原始容量 * 2 + 1; int newCapacity = (oldCapacity << 1) + 1;
G. Properties
Properties是HashTable的一个子类,Properties新增了load() 和 store() 方法,可以直接导入或者将映射写入文件,另外,Properties的键和值都是String类型。
七、HashMap 底层实现原理
A. Hash
Hash,一般翻译做“散列”,也有直接音译为“哈希”的。
Hash就是把任意长度的输入(又叫做预映射,pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。
这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来唯一的确定输入值。
简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
1. Hash是一个函数,该函数中的实现就是一种算法,就是通过一系列的算法来得到一个hash值(散列值)。
2. 通过hash算法得到的hash值存放在hash表中,也就是说,hash表就是所有的hash值组成的,有很多种hash函数,也就代表着有很多种算法得到hash值。
3. 散列表(Hash table, 也叫哈希表):是根据关键码值(key, value)而直接进行访问的数据结构。也就是说,它通过把
4. 散列函数:关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
B. HashCode
HashCode就是通过hash函数得来的,通俗的说,就是通过某一种算法得到的,hashcode就是在hash表中有对应的位置。
HashCode的存在主要是为了查找的快捷性,HashCode是用来在散列存储结构中确定对象的存储地址的(用hashcode来代表对象在hash表中的位置)。
1. 对象的HashCode怎么得来的
每个对象都有对应的物理地址(对象存放在内存中的地址),通过对象的物理地址转换成一个整数,然后该整数通过hash函数的算法就得到了hashcode。
2. 常用的Hash函数
2.1 直接寻址法:取关键字或关键字的某个线性函数值为散列地址。即H(key)= key 或 H(key)= a ? key + b,其中a和b为常数(这种散列函数叫做自身函数)。
2.2 数字分析法:数字分析法就是找出数字的规律,尽可能利用这些数据来构造冲突几率较低的散列地址。
2.3 平方取中法:取关键字平方后的中间几位作为散列地址。
2.4 折叠法:将关键字分割成位数相同的几部分,最后一部分位数可以不同,然后取这几部分的叠加和(去除进位)作为散列地址。
2.5 随机数法:选择一随机函数,取关键字的随机值作为散列地址,通常用于关键字长度不同的场合。
2.6 除留余数法:取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。
C. equals方法和hashcode的关系
先通过hashcode来确定对象在hash表中的位置,再用equals方法来比较两个对象是否相等。
1. 如果两个对象equals相等,那么这两个对象的HashCode一定也相同。
2. 如果两个对象的HashCode相同,不代表两个对象就相同,只能说明这两个对象在散列存储结构中,存放于同一个位置。
D. HashMap
HashMap基于Map接口实现,元素以键值对(key, value)的方式存储,并且允许使用null键和null值,因为key不允许重复,因此只能有一个键为null,允许多条记录的值为null。HashMap是无序的,和放入的顺序并不能相同。
HashMap非线程安全,即任一时刻有多个线程同时写HashMap,可能会导致数据的不一致。
如果要满足线程安全,可以用Collections的synchronizedMap方法使HashMap具有线程安全的能力,或者使用ConcurrentHashMap。

E. HashMap存储结构
1. JDK1.7 使用 数组 + 链表 的方式进行存储。
2. JDK1.8 使用 数组 + 链表 + 红黑树 的方式进行存储(链表长度大于8时转换为红黑树,长度小于6时转换为链表)。
HashMap采用Entry数组来存储(key-value)对,每一个键值对组成了一个Entry实体,Entry类实际上是一个单向的链表结构,它具有Next指针,可以链接下一个Entry实体,依次来解决Hash冲突的问题。
因为HashMap是按照key的hash值来计算Entry在HashMap中存储的位置的,如果hash值相同,而key内容不相同,那么就用链表来解决这种hash冲突。
F. HashMap存储流程
1. 使用hash算法计算key值对应的hash值(h)。
2. 计算该(k, v)对应的索引值index,索引值的计算公式为 index = (h % length),length为数组的长度。
3. 储存对应的(k, v)到数组中去,从而形成 a[index] = node<k, v>,如果a[index]已经有了结点,即可能发生碰撞。
index = (h % length) 等于 index = h & (length – 1), HashMap源码中默认使用 index = h & ( length – 1 )。
h是通过hash算法计算得到的一个整型数值(默认使用key对应的hashcode进行计算(hashcode默认为key在内存中的地址));
h可以近似看做一个由key的hashcode生成的随机数,区别在于相同的hashcode生成的h必然相同,而不同的hashcode也可能生成相同的h,这种情况叫做hash碰撞。hash碰撞只能尽量避免,而无法杜绝。
G. 解决hash冲突的三种方式
1. 拉链法(Java默认实现):
将链表和数组想结合,若遇到哈希冲突,则将冲突的值加到链表中即可。
2. 开放地址法:
插入一个元素的时候,先通过哈希函数进行判断,若是发生哈希冲突,就以当前地址为基准,根据再寻址的方法去寻找下一个地址,直到找到一个为空的地址为止。
3. 再散列法:
使用哈希函数去散列一个输入的时候,输出是同一个位置就再次散列,直至不发生冲突为止。
H. HashMap的扩容时机
当hashmap中的(size > loadFactory * capacity)即会发生扩容,size也是数组结点和链表结点的总和。
1. 当前数据存储的数量(即size())大小必须大于等于阈值(负载因子 * 容量(默认 0.75 * 16))。
2. 当前加入的数据是否发生了hash冲突。
I. HashMap中的默认值
1. 默认初始化容量大小 1 << 4, 2^4 = 16。
2. 默认的最大容量大小 1 << 30,2^30。
3. 默认的负载因子(loadFactory) 0.75。
J. HashMap扩容方法 resize()
resize方法中比较重要的是链表和红黑树的rehash操作。
HashMap在扩容的时候,一般是把长度扩为原来的2倍,所以,元素的位置要么是在原位置,要么是在原位置再移动2次幂的位置。
K. 如下图所示,n为数组的长度;
图(a)表示扩容前的key1和key2两种key确定索引位置的示例;
图(b)表示扩容后key1和key2两种key确定索引位置的示例;
其中hash1是key1对应的哈希与高位运算结果。

元素在重新计算hash之后,因为n变为2倍,那么n-1在高位多 1bit(上图中红色部分),因此新的index就会发生以下变化。
因此在扩容hashmap的时候,只需要看看原来的hash值新增的那个bit是1还是0就好了,是0的话索引没有变,是1的话索引变成“原索引 + oldCap”。

L. 为什么在HashMap中数组的长度 length = 2^n(初始默认值为16)?
当计算索引值 index = h % length时,由于计算机的取余操作速度很慢,而计算机的按位取余 & 的操作非常快。
又因为h % length = h & (length – 1)(需要满足 length = 2^n),因此规定了 length = 2^n 加快index的计算速度。
因为2的幂都是 1111 结尾的,在进行位于运算时,能减少哈希碰撞的概率。
M. 为什么HashMap 是线程不安全的?
1. put 的时候导致的多线程数据不一致。
例:有两个线程A 和 线程B。
1)首先A希望插入一个(key, value)到HashMap中。
2)先计算键值对对应的桶的索引坐标。
3)然后获取到该桶里面的链表头结点。
4)此时线程A的时间片用完了。
5)而此时线程B被调度得以执行,和线程A一样执行,只不过线程B成功将记录插到了桶里面。
6)假设线程A与线程B计算出的桶索引一致,那么当线程B成功插入之后,线程A再次被调度运行时依然持有过期的链表头。
7)这样就覆盖了线程B的插入记录,造成数据不一致的行为。
2. get 操作可能因为resize而引起死循环。
例:假设有两个线程同时需要执行resize操作。
1)假设原有桶数量为2,记录为3([3,A],[7,B],[5,C]),需要resize到4。
2)在原来的map里面,3个记录都落到了第二个桶里面(见下图)。
3)假设线程1执行到了transfer方法的 Entry<k, v> next = e.next(见下图)。
4)然后时间片用完了,此时的 e = [3, A], next = [7, B],线程2被调度执行并且顺利完成了resize操作。
5)需要注意的是,此时完成了resize之后的[7, B]的next是[3, A](见下图)。
6)此时线程1重新被调度运行,此时线程1持有的引用已经被线程2 resize之后的结果。
7)线程1首先将[3, A]迁移到新数组上,然后再处理[7, B],[7, B]被链接到了[3, A]后面。
8)处理完[7, B]之后,就需要处理[7, B]的next,而通过线程2的resize之后,[7, B]的next变为了[3, A]。
9)此时,[3, A]和[7, B]形成了环形链表,在get的时候,如果get的key的桶索引和[3, A]、[7, B]一样,就会陷入死循环(源码见下图)。


N. 为什么HashMap的key值允许为空?
从源码分析,HashMap在put的时候会调用hash()方法来计算key的hashcode值,可以从hash算法中看出当 key == null时返回的值为0。
因此key为null时,hash算法返回值为0,不会调用key的hashcode方法。

O. 为什么HashMap是无序的?
因为HashMap的存储结构是 数组+链表+红黑树 的存储结构(JDK1.8中才引入了红黑树结构)。
八、JAVA集合线程安全与非线程安全汇总:

A. ArrayList 和 Vector 区别
Vector和ArrayList之间唯一的区别就是Vector每个方法都自带同步机制。
B. HashMap、HashTable、HashSet 区别
HashMap和HashTable采用的存储机制是一样的,不同的是:
1. HashMap:
非线程安全,采用数组+链表+红黑树的方式存储,key和value允许为null,默认容量16,遍历使用的是Iterator迭代器。
2. HashTable:
线程安全,采用数组+链表的方式存储,key和value不允许为null,默认容量为11,遍历使用的是Enumeration列举。
3. HashSet:
非线程安全,底层通过HashMap实现,不保证数据的有序。
C. TreeSet 和 TreeMap 区别
TreeSet和TreeMap都是完全基于Map来实现的,并且都不支持get(index)来获取指定位置的元素,需要遍历来获取。
1. TreeSet:
非线程安全,底层基于TreeMap实现,支持排序。
2. TreeMap:
非线程安全,典型的基于红黑树的Map实现,因此它要求一定要有key比较的方法,要么传入Comparator比较器实现,要么key对象实现Comparator接口。
与HashMap相比,TreeMap内部的元素都是排序的,当需要查找某些元素以及顺序输出元素的时候占优势。因此,TreeMap是一个内部元素排序版的HashMap。
D. String、StringBuffer、StringBuilder 区别
1. string:
操作少量的数据。
2. StringBuilder:
单线程操作字符串缓冲区下操作大量数据。
3. StringBuffer:
多线程操作字符串缓冲区下操作大量数据。
E. 非线程安全 != 不安全
多线程操作同一个对象是线程不安全的,但如果每一个线程中new一个ArrayList,而这个ArrayList只在这一个线程中使用,那么肯定是没有问题。
九、JAVA集合的比较器:
Comparable 和 Comparator接口都是用来比较大小的,主要用于解决排序问题。
A. Comparable
Comparable接口强行对实现它的类的每个实例进行自然排序,该接口的唯一方法compareTo方法被称为自然比较方法。
1. 方法compareTo
若当前对象比目标对象大,则返回1,那么当前对象会排在目标对象后面。
若当前对象比目标对象小,则返回-1,那么当前对象会排在目标对象前面。
若两个对象相等,则返回0。
package java.lang;
import java.util.*;
public interface Comparable<T> { public int compareTo(T o); }
若一个类实现了Comparable接口,实现Comparable接口的类的对象的List列表(或数组)可以通过Collection.sort(或Array.sort)进行排序。 Collections.sort(list);
B. Comparator
Comparator:是比较器接口,需要重写compare方法。
Comparator 的两个抽象方法:
1. int compare(T o1, T o2):比较用来排序的两个参数。
2. boolean equals(Object obj):指示某个其它对象是否“等于”此Comparator。
package java.util;
import java.util.*;
public interface Comparator<T> { int compare(T o1, T o2); ...... }
如果一个类无法修改或者没有继承Comparable接口,又需要对其进行排序,可以使用Comparator,覆写compare方法。
Collections.sort(list, new Comparator<Person>() {
[@Override](https://my.oschina.net/u/1162528)
public int compare(Person o1, Person o2) {
if(o1 == null || o2 == null){
return 0;
}
/**
o1比o2小,返回 -1
o1等于o2,等于0
o1大于o2,返回 1
*/
return o1.getAge() - o2.getAge();
}
});
Comparable 是排序接口,若一个类实现了Comparable接口,就意味着“该类支持排序”。(内部比较器)
Comparator 是比较器接口,若需要控制某个类的次序,可以建立一个“该类的比较器”来进行排序。(外部比较器)
十、JAVA集合的常用工具类:
A. Collection 类
java.util.Collections工具类为集合框架提供了很多有用的方法,这些方法都是静态的,在编程中可以调用。
1. addAll
向指定的集合c中加入特定的一些元素elements。
2. binarySearch
利用二分法在集合中查找元素,内部是通过Comparable,Comparator接口实现。
3. sort
排序,内部是通过Comparable, Comparator接口实现。
4. shuffle
混排,随机打乱原来的顺序,它打乱在一个List中可能有的任何排列的踪迹。
5. reverse
集合排列反转。
6. synchronized
确保所封装的集合线程安全。
B. Arrays 类
java.util.Arrays工具类也为集合框架提供了很多有用的方法,这些方法都是静态的,在编程中可以直接使用。
1. asList
将一个数组转变成一个List。
注意:这个List是定长的,企图添加或删除数据都会报错。
2. sort
对数组进行排序,适合byte, char, double, float, int, long, short等基本类型,还有Object类型。
3. binarySearch
通过二分查找法对已排序的数组进行查找。
4. copyOf
数组拷贝,底层采用System.arrayCopy(native方法)实现。
5. copyOfRange
数组拷贝,指定一定的范围,底层采用System.arrayCopy(native方法)实现。
6. equals 和 deepEquals
equals:判断两个数组的每一个对应的元素是否相等(equals, 对于两个数组的元素a和a2有anull ? a2null : a.equals(a2))。
deepEquals:主要针对一个数组中的元素也是数组的情况(多维数组比较)。
7. toString 和 deepToString
toString:将数组转换成字符串,中间用逗号隔开。
deepToString:当数组中又包含数组,就不能单纯的利用Arrays.toString()了,使用此方法将数组转换成字符串。
十一、迭代器:
JCF的迭代器(Iterator)为我们提供了遍历容器中元素的方法。
只有容器本身清楚容器里元素的组织方式,因此迭代器只能通过容器本身得到。每个容器都会通过内部类的形式实现自己的迭代器。
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论