线程安全的List
A:使用 Vector;B:使用 Collections.synChronized() 返回线程安全的 List;C:使用 CopyOnWriteArrayList
List的API示例
boolean contains(Object o) // 是否包含 o
boolean isEmpty(); // 是否为空
int size(); //集合元素
Iterator<E> iterator(); // 返回迭代器
Object[] toArray(); // 转为 Object数组
<T> T[] toArray(T[] a); // 转为具体类型数组
boolean add(E e); // 加入尾部
boolean remove(Object o); // 移除 o
boolean containsAll(Collection<?> c); //是否报考 集合 c
boolean addAll(Collection<? extends E> c);// 合并 c
boolean retainAll(Collection<?> c);//保留只存在集合 c 的元素
void clear(); // 清除集合元素
void sort(Comparator<? super E> c) //根据 Comparator 排序
E get(int index); // 根据下标获取 元素
E set(int index, E element); // 设置第 index 的元素
E remove(int index); // 移除 第 index 的元素
<E> List<E> of(E e1.....) // jdk 9
List<E> copyOf(Collection<? extends E> coll) // 复制
2.Vector(向量)
ArrayList 和 Vector、LinkedList 的区别
· Vector 相当于是 ArrayList 线程安全的翻版
· Vector 继承实现List 特点: 底层数据结构是数组,查询快,线程安全
Vector 的API示例
boolean synChronized contains(Object o);
boolean synChronized isEmpty();
boolean synChronized containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c);
public synChronized boolean add(E e)
public synChronized E get(int index);
public synChronized E set(int index, E element);
public synChronized E firstElement()
public synChronized void removeElementAt(int index)
public synChronized E lastElement()
public synChronized void setElementAt(E obj, int index)
public synChronized E remove(int index)
public void clear()
Iterator<E> iterator();
3.Stack(栈)
Stack 是 Vector提供的一个子类,用于模拟"栈"这种数据结构(LIFO后进先出)
线程安全,允许 null 值
Stack 的API示例
public E push(E item) //推入栈顶
public synChronized E pop() // 弹出栈顶元素,不存在则报错
public synChronized E peek() // 获取栈顶元素,不移除
public boolean empty() // 栈是否为空
public synChronized int search(Object o) // 搜索元素
4.Map
Map 用于保存具有映射关系的数据,Map里保存着两种映射的数据:key和value,它们都可以使任何引用类型的数据,但key不能重复。所以通过指定的key就可以取出对应的value
请注意!!!Map 没有继承 Collection 接口
TreeMap(1.8JDK)
继承 AbstractMap,TreeMap 是基于红黑树实现,可保证在log(n)时间复杂度内完成 containsKey,get,put 和 remove 操作,效率很高。(红黑树的原理这里不展开讲,后面会专门写一篇)
另一方面,由于 TreeMap 基于红黑树实现,因此 TreeMap 的键是有序的
HashMap
HashMap 继承AbstractMap类实现了Map,是一个散列表,它存储的内容是键值对(key-value)映射。HashMap 实现了 Map 接口,根据键的 HashCode 值存储数据,具有很快的访问速度,最多允许一条
记录的键为 null,不支持线程同步。HashMap 是无序的,即不会记录插入的顺序
HashMap如何处理hash冲突,hash冲突的几种解决方法
· 链地址法-如果存在 hash 碰撞,则创建一链表存储相同的元素
· 开放定址法容易导致 hash 碰撞,查询慢
· 线性探查在散列的时候,如果当前计算出的位置已经被存储,那么就顺序的向后查找,知道找到空位置或则是所有位置均不为空失败
· 二次探查使用一个辅助散列函数,使得后续的探查位置在前一个探查位置上加上一个偏移量,该偏移量以二次方的形式依赖于探查号i。二次探查的散列函数形式为:h(k,i)=(h”(k,i)+c1*i + c2 * i^2) mod m
· 双重散列使用两个辅助散列函数h1和h2,初始的散列位置是h1(k),后续的散列位置在此基础上增加一个偏移量h2(k)*i mod m
· 开放定址法
· 链地址法
HashMap 底层实现是数组+链表+红黑树。空参的HashMap初始容量是16,默认加载因子为0.75。取值0.75是因为 0.5 容易浪费空间,取值 1 则需要填满每一个桶,实际情况很难达到,会产生大量的哈希碰撞。因此取中间值
HashMap 的容量一般是 2 的幂次方,可直接使用“位与”计算 hash 值,相对取模计算 hash 快
Hashtable
继承于Dictionary,现在基本已被淘汰
HashTable的操作几乎和HashMap一致,主要的区别在于HashTable为了实现多线程安全,在几乎所有的方法上都加上了synChronized锁,而加锁的结果就是HashTable操作的效率十分低下
HashMap允许有一个键为null,允许多个值为null;但HashTable不允许键或值为null
Hash映射:HashMap的hash算法通过非常规设计,将底层table长度设计为2的幂,使用位与运算代替取模运算,减少运算消耗;而HashTable的hash算法首先使得hash值小于整型数最大值,再通过取模进行散射运算
LinkedHashMap
LinkedHashMap的元素存取过程基本与HashMap基本类似,只是在细节实现上稍有不同。当然,这是由LinkedHashMap本身的特性所决定的,因为它额外维护了一个双向链表用于保持迭代顺序。此外,LinkedHashMap可以很好的支持LRU算法。HashMap和双向链表合二为一即是LinkedHashMap
WeakHashMap
WeakHashMap 也是一个散列表,它存储的内容也是键值对(key-value)映射,而且键和值都可以是 null
WeakHashMap的键是“弱键”。在 WeakHashMap 中,当某个 key 不再被强引用使用时,会被从WeakHashMap中被 JVM 自动移除,然后它对应的键值对也会被从WeakHashMap中移除。?JAVA引用类型和ThreadLocal
ConcurrentHashMap(1.8JDK)
ConcurrentHashMap 是 HashMap 的多线程安全版本。它使用了细粒度锁 和 cas 提高了在多线程环境的安全性和高并发
底层数据结构是 数组 + 链表/红黑树(后面专门写一篇介绍)
ConcurrentSkipListMap 了解一波
ConcurrentSkipListMap 则是基于跳跃链表的实现的 map,使用了 cas
技术实现线程安全性,高并发
ConcurrentSkipListMap 相比 ConcurrentHashMap 的优点
· ConcurrentSkipListMap 的key是有序的。
· ConcurrentSkipListMap 支持更高的并发。ConcurrentSkipListMap的存取时间是log(N),和线程数几乎无关。也就是说在数据量一定的情况下,并发的线程越多,ConcurrentSkipListMap 越能体现出它的优势
NavigableMap 和 ConcurrentNavigableMap 操作 key 值的范围区间
TreeMap 实现了 NavigableMap 。ConcurrentNavigableMap 高并发线程安全版的 TreeMap
NavigableMap 提供了针对给定搜索目标返回最接近匹配项的导航方法。直接看API
K lowerKey(K key) // 找到第一个比指定的key小的值
K floorKey(K key) // 找到第一个比指定的key小于或等于的key
K ceilingKey(K key) // 找到第一个大于或等于指定key的值
K higherKey(K key) // 找到第一个大于指定key的值
Map.Entry<K,V> firstEntry() // 获取最小值
Map.Entry<K,V> lastEntry() // 获取最大值
Map.Entry<K,V> pollFirstEntry() // 删除最小的元素
Map.Entry<K,V> pollLastEntry() // 删除最大的元素
NavigableMap<K,V> descendingMap() //返回一个倒序的Map
// 返回值小于 toKey 的 NavigableMap
NavigableMap<K,V> headMap(K toKey, boolean inclusive)
// 返回值大于 fromKey 的 NavigableMap
NavigableMap<K,V> tailMap(K fromKey, boolean inclusive)
// 返回值小于 toKey 大于 的 fromKey NavigableMap
NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)
5.Set(集合)
Set特点:元素无放入顺序,元素不可重复,如果加入重复元素,会保留最先加入的对象。存取速度快
Set 的几种实现子类和各自特点
TreeSet:底层数据结构采用二叉树来实现,元素唯一且已经排好序;唯一性同样需要重写 hashCode 和 equals()方法,二叉树结构保证了元素的有序
· 根据构造方法不同,分为自然排序(无参构造)和比较器排序(有参构造),自然排序要求元素必须实现Compareable接口,并重写里面的compareTo()方法
HashSet:是哈希表实现的,HashSet中的数据是无序的,可以放入 null,但只能放入一个null,两者中的值都不能重复,就如
数据库中唯一约束
· HashSet 是基于 HashMap 算法实现的,其性能通常都优于TreeSet
· 为快速查找而设计的Set,我们通常都会用到HashSet,若需要排序的功能时,才使用TreeSet
LinkedHashSet:底层数据结构采用链表和哈希表共同实现,链表保证了元素的顺序与存储顺序一致,哈希表保证了元素的唯一性,效率高。但线程不安全
ConcurrentSkipListSet
基于 ConcurrentSkipListMap 实现
CopyOnWriteArraySet
基于 CopyOnWriteArrayList 实现
BitSet
BitSet是位操作的对象,值只有 0 或 1 即false和true,内部维护了一个long数组,初始只有一个long,所以BitSet最小的size是64,当随着存储的元素越来越多,BitSet内部会动态扩充,最终内部是由N个long来存储
如统计40亿个数据中没有出现的数据,将40亿个不同数据进行排序等。
现在有1千万个随机数,随机数的范围在1到1亿之间。现在要求写出一种算法,将1到1亿之间没有在随机数中的数求出来
void an d(BitSet set) // 两个BitSet 做与操作,结果并存入当前 BitSet
void an dNot(BitSet set) // 两个BitSet 与非操作
void flip(int index) // 反转某一个指定 index
boolean intersects(BitSet bitSet) // 是否有交集
int cardinality() //返回 true/1 的个数
void clear() // 重置
void clear(int startIndex, int endIndex) // startIndex~endIndex 重置
int nextSetBit(int startIndex) //检索在startIndex之后出现为1的第一位的索引
int nextClearBit(int startIndex) //检索在startIndex之后出现为0的第一位的索引
6.Queue(队列)
Queue的概念 队列是一种特殊的线性表,只允许元素从队列一端入队,而另一端出队(获取元素),就像我们平时排队结算一样(懂文明讲礼貌不插队)。Queue 的数据结构和 List 一样,可以基于数组,链表实现,队列通常都是一端进(offer),另一端出(poll),有序性
PriorityQueue
PriorityQueue是按优先级排序的队列,也就是说 vip 可以插队。优先队列要求使用
Java Comparable 和 Comparator 接口给对象排序,并且在排序时会按照优先级处理其中的元素
PriorityBlockingQueue 是线程安全的PriorityQueue
BlockingQueue
BlockingQueue很好的解决了多线程中,如何高效安全“传输”数据的问题。通过这些高效并且线程安全的队列类,为我们快速搭建高质量的多线程程序带来极大的便利。常用于线程的任务队列
DelayQueue
DelayQueue是一个没有边界BlockingQueue实现,加入元素必须实现Delayed接口。当生产者线程调用put之类的方法加入元素时,会触发 Delayed 接口中的compareTo方法进行排序
消费者线程查看队列头部的元素,注意是查看不是取出。然后调用元素的getDelay方法,如果此方法返回的值小0或者等于0,则消费者线程会从队列中取出此元素,并进行处理。如果getDelay方法返回的值大于0,则消费者线程阻塞到第一元素过期
Queue 的 API
boolean add(E e); //加入队列尾部
boolean offer(E e); // 加入队列尾部,并返回结果
E remove(); //移除头部元素
E poll(); // 获取头部元素,并移除
E element(); // 获取头部元素,不存在则报错
E peek(); // 获取头部元素,不移除
7.Deque(双向队列)
Deque接口代表一个"双端队列",双端队列可以同时从两端来添加、删除元素,因此Deque的实现类既可以当成队列使用、也可以当成栈使用
Deque 的子类 LinkedList,ArrayDeque,LinkedBlockingDeque
Deque的 API
void addFirst(E e); //加入头部
void addLast(E e); //加入尾部
boolean offerFirst(E e); //加入头部,并返回结果
boolean offerLast(E e); //加入尾部,并返回结果
E removeFirst(); // 移除第一个元素
E removeLast(); // 移除最后一个元素
E getFirst(); //获取第一个元素,不存在则报错
E getLast(); //获取最后一个元素,不存在则报错
E pollFirst(); //获取第一个元素,并移除
E pollLast(); //获取最后一个元素,并移除
E peekFirst(); //获取第一个元素
E peekLast(); // 获取最后一个元素
void push(E e); //加入头部
E pop(); //弹出头部元素