中级03 - Collection体系简介

List

Set

hashCode约定

Map

Collection 的体系

Collection 体系提供的常⽤⽅法：

retainAll() 求交集

removeAll() 求差集

有序可重复，最常用的是 ArrayList，本质上就是一个数组

add() 方法内部实现了数组的动态扩容：创建一个更大的空间，然后把原先的所有元素拷贝进去。

无序且不可重复的元素集合。

只是简单通过 objectcontains() 判断添加新元素时是否重复，从而实现去重的 Set 是很低效的，这就引出了对象的 hashcode。

Java世界⾥第⼆重要的约定：hashCode

哈希就是⼀个单向、一对多的映射，具有相同 hashCode 的东西存放在同一个 hash 桶中，

例⼦：从姓名到姓到哈希运算

从任意对象到⼀个整数（int）的 hashCode

HashSet 是无序的，是最常用的 Set 实现。

可以利用 set 为 list 过滤去重：

LinkedHashSet 是有序的，其维护了一个双向（doubly-linked）链表，顺序就是插入元素时的顺序。

map 是 一个将 keys 映射到 values 的对象，键不能重复，每个键只能映射一个值，值可以重复。

Create/Update: put()/putAll()

Read:

Delete: remove()/clear()

keySet() 返回键的集合，因为键不可重复，所以可以返回一个 set；

values() 返回值的集合，因为值可以重复，所以返回的是 collection。

注意： keySet() 和 map 背后的 keys 是同一组数据，所以二者的修改会相互影响。

entrySet() 返回键值对的集合（ Set<MapEntry<K, V>> ），遍历时很有用：

HashMap 是最常用、最高效的 Map 实现。

HashMap 的扩容，思路同样是创建更大的空间，然后把之前的数据 copy 进来。

HashMap 是多线程不安全的，可使用 ConcurrentHashMap。

HashMap在Java 7+后的改变（链表 --> 红⿊树）：

因为 hashCode 是可能重复的（即发生碰撞），极端情况下如果一组数据的 hashCode 全部相同，那么会全放在同一个 hash 桶中成为了一个 List 链表，此时就丧失了 hash 桶的好处，性能会急剧恶化，所以 Java 7 开始会采用红黑树来代替链表。

HashMap 和 HashSet 本质上是同一个东西：

HashMap 的 key 集合（set）就是 HashSet，而 HashSet 内部其实就是个 HashMap，毕竟 HashSet 拥有的功能 HashMap 都有。

TreeSet 可以排序（默认是自然顺序）。

HashSet、LinkedHashSet 与 TreeSet 对比：

TreeMap 同理。

它们使⽤ Comparable 约定，认为排序相等的元素相等。

Google 开源的 Guava 提供了 JDK 没有的额外方法，不要重复发明轮⼦，尽量使⽤经过实战检验的类库。

这本是多年前一个stackoverflow上的一个讨论，回答中涉及到了多种计数方法。对于一个key-value结构的map，我们在编程时会经常涉及到key是对象，而value是一个integer或long来负责计数，从而统计多个key的频率。

面对这样一个基本需求，可能有很多种实现。比如最基本的使用jdk的map直接实现——value是一个integer或者long。其基本代码型如下：

1: final Map<String, Integer> freq = new HashMap<String, Integer>();

2: int count = freqcontainsKey(word) freqget(word) : 0;

3: freqput(word, count + 1);

逻辑简单，判断是否存在，是则get取值，否则为0，再put进去一个加1后的值。总共要contain判断，get，put做三次方法调用。

当然进一步我们可以把contain判断去掉，代码如下：

1: final Map<String, Integer> freq = new HashMap<String, Integer>();

2: Integer count = freqget(word);

3: if (count == null) {

4: freqput(word, 1);

5: } else {

6: freqput(word, count + 1);

7: }

一般情况，我们做到这个地步，多数人对其逻辑已经满足，简单性能也能接受，试着想一下，难道不是这样吗？get加put，解决了。

当然这样的实现还不够高效，于是我们开始去尝试实现或寻找更高效的方法，看看开源的集合类库是否有需要的：

有个Trove，可以让我们参考一下：

1: final TObjectIntHashMap<String> freq = new TObjectIntHashMap<String>();

2: freqadjustOrPutValue(word, 1, 1);

这样做，非常优雅啊，性能如何呢？不知道，需要看源码了解细节。那再看看大名鼎鼎的guava如何呢？

1: AtomicLongMap<String> map = AtomicLongMapcreate();

2: mapgetAndIncrement(word);

实现依然优雅，但是，但是看这名字，再看源码，好吧，线程安全的，支持并发，这不好搞了，我们场景需要吗？不需要的话直觉告诉我们这肯定是“慢”的。再找：

1: Multiset<String> bag = HashMultisetcreate();

2: bagadd(word);

这个看上去合适了，bag的实现明显好很多，而且从语义理解上，这样的接口更容易让人理解。

那么这些方法，性能如何呢？做了个简单的比较，将26个英文字母做key，均匀循环若干次比较各个方法的效率（单纯时间效率），而且时间不统计构建开销。外加了一个线程安全版的concurrentMap实现，而其实google的guava里的AtomicLongMap也是包装了juc的concurrentMap而已。里面有最终极的MutableInt方法，找找看吧，性能最好的就是它了。

Guava 的 FAQ 部分有专门解答：

Why did Google build all this, when it could have tried to improve the Apache Commons Collections instead

The Apache Commons Collections very clearly did not meet our needs It does not use generics, which is a problem for us as we hate to get compilation warnings from our code It has also been in a "holding pattern" for a long time We could see that it would require a pretty major investment from us to fix it up until we were happy to use it, and in the meantime, our own library was already growing organically

An important difference between the Apache library and ours is that our collections very faithfully adhere to the contracts specified by the JDK interfaces they implement If you review the Apache documentation, you'll find countless examples of violations They deserve credit for pointing these out so clearly, but still, deviating from standard collection behavior is risky! You must be careful what you do with such a collection; bugs are always just waiting to happen

Our collections are fully generified and never violate their contracts (with isolated exceptions, where JDK implementations have set a strong precedent for acceptable violations) This means you can pass one of our collections to any method that expects a Collection and feel pretty confident that things will work exactly as they should

简单地说：

Apache Commons Collections 3x 不支持泛型，Guava 支持

Guava 实现了 JDK 的标准接口，而 Apache Commons Collections 3x 有很多违反标准的地方

Apache Commons Collections 4x 的发行注记如下：

Major changes since 321

Use of generics and other language features introduced in Java 5 (varargs, Iterable)

Removed deprecated classes / methods and features which are now supported by the JDK

Replaced Buffer interface with javautilQueue

Added concept of split maps with respective interfaces Put / Get (see also package splitmap)

Added new Trie interface together with an implementation of a Patricia Trie

从 4x 开始，Apache Commons Collections 开始使用 JDK 5 的特性（包括泛型），此外也去除、添加了很多内容

各有千秋, 我主要使用 Apache Commons ,辅助使用  Google guava

当同时满足以下条件时，使用ziplist编码：

SpringBoot—实现n秒内出现x个异常报警

思路：

借助Redis的zSet集合，score存储的是异常时的时间戳，获取一定时间范围内的set集合。判断set个数是否满足条件，若满足条件则触发报警；

注意点：

相关API：

Redis实现延迟队列方法介绍

基于Redis实现DelayQueue延迟队列设计方案

相关API：

SpringBoot2x—使用Redis的bitmap实现布隆过滤器（Guava中BF算法）

布隆过滤器： 是专门用来检测集合中是否存在特定元素的数据结构。

存在误差率： 即将不在集合的元素误判在集合中。

所以布隆过滤器适合查询准确度要求没这么苛刻，但是对时间、空间效率比较高的场景。

实现方式：Redis实现布隆过滤器——借鉴Guava的BF算法：

SpringBoot2x中使用Redis的bitmap结构（工具类）

注意：bitmap使用存在风险，若仅仅计算hash值，会导致bitmap占用空间过大。一般需要对hash值进行取余处理。

根据Redis是否存在key，判断锁是否被获取；

锁应该是一个对象，记录持有锁的线程信息、当前重入次数。所以应该使用Redis的Hash结构来存储锁对象。

31 网络波动造成释放锁失败怎么解决？

需要为锁加上超时时间；

32 任务未执行完毕时，锁由于超时时间被释放？

线程一旦加锁成功，可以启动一个后台线程，每隔多少秒检查一次，如果线程还持有锁，可以不断延长锁的生存时间。

主从切换时，从服务器上没有加锁信息，导致多个客户端同时加锁。

list结构底层是ziplist/quicklist（可看着一个双端队列）。常用命令：

使用list作为对象的缓存池。通过rpush放入对象，通过lpop取出对象。

若是阻塞取，可以使用blpop命令实现。

Redis和Lua脚本(实现令牌桶限流)

数据结构选择hash。

hash里面维护：最后放入令牌时间、当前桶内令牌量、桶内最大数量、令牌放置速度（元数据）。

被动式维护：

命令：incr原子累加；

对一段固定时间窗口内的请求进行计数，如果请求数超过了阈值，则舍弃该请求；如果没有达到设定的阈值，则接受该请求，且计数加1。当窗口时间结束，重置计数器为0。

优点：实现简单，容易理解；

缺点：流量曲线可能不够平滑，有“突刺现象”。

1 一段时间内（不超过时间窗口）系统服务不可用。 比如窗口大小1s，限流为100，恰好某个窗口第1ms来了100个请求，然后2ms-999ms请求都会被拒绝。这段时间用户会感觉系统服务不可用（即不够平滑）。

2 窗口切换时可能会出现两倍于阈值流量的请求。 比如窗口大小1s，限流大小100，然后在某个窗口的第999ms有100个请求，窗口前期没有请求。所以这100个请求都会通过。然后下一个窗口的第1ms又来100个请求，然后全部通过。其实也是1ms内通过的200个请求。

命令：Redis的incr命令

是对固定窗口计数器的优化，解决的是切换窗口两倍阈值流量的场景。

具体解决方案是：将限流窗口分为多个小的限流窗口，各个限流窗口分别计数。当前时间大于窗口最大时间时，将头部的小窗口数据舍弃，尾部新增小窗口来处理新请求。

优点：本质上是对固定窗口的优化

以上就是关于中级03 - Collection体系简介全部的内容，包括:中级03 - Collection体系简介、如何高效的实现一个计数器map、Google guava和Apache commons哪个好等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！