中国建设协会网站,分销系统开发公司,wordpress商城怎么样,深圳网站策划作者 | 王磊来源 | Java中文社群#xff08;ID#xff1a;javacn666#xff09;转载请联系授权#xff08;微信ID#xff1a;GG_Stone#xff09;URL 去重在我们日常工作中和面试中很常遇到#xff0c;比如这些#xff1a;可以看出#xff0c;包括阿里#xff0c;网易… 作者 | 王磊来源 | Java中文社群IDjavacn666转载请联系授权微信IDGG_StoneURL 去重在我们日常工作中和面试中很常遇到比如这些可以看出包括阿里网易云、优酷、作业帮等知名互联网公司都出现过类似的面试题而且和 URL 去重比较类似的如 IP 黑/白名单判断等也经常出现在我们的工作中所以我们本文就来“盘一盘”URL 去重的问题。URL 去重思路在不考虑业务场景和数据量的情况下我们可以使用以下方案来实现 URL 的重复判断使用 Java 的 Set 集合根据添加时的结果来判断 URL 是否重复添加成功表示 URL 不重复使用 Redis 中的 Set 集合根据添加时的结果来判断 URL 是否重复将 URL 都存储在数据库中再通过 SQL 语句判断是否有重复的 URL把数据库中的 URL 一列设置为唯一索引根据添加时的结果来判断 URL 是否重复使用 Guava 的布隆过滤器来实现 URL 判重使用 Redis 的布隆过滤器来实现 URL 判重。以上方案的具体实现如下。URL 去重实现方案1.使用 Java 的 Set 集合判重Set 集合天生具备不可重复性使用它只能存储值不相同的元素如果值相同添加就会失败因此我们可以通过添加 Set 集合时的结果来判定 URL 是否重复实现代码如下public class URLRepeat {// 待去重 URLpublic static final String[] URLS {www.apigo.cn,www.baidu.com,www.apigo.cn};public static void main(String[] args) {SetString set new HashSet();for (int i 0; i URLS.length; i) {String url URLS[i];boolean result set.add(url);if (!result) {// 重复的 URLSystem.out.println(URL 已存在了 url);}}}
}
程序的执行结果为URL 已存在了www.apigo.cn从上述结果可以看出使用 Set 集合可以实现 URL 的判重功能。2.Redis Set 集合去重使用 Redis 的 Set 集合的实现思路和 Java 中的 Set 集合思想思路是一致的都是利用 Set 的不可重复性实现的我们先使用 Redis 的客户端 redis-cli 来实现一下 URL 判重的示例从上述结果可以看出当添加成功时表示 URL 没有重复但添加失败时结果为 0表示此 URL 已经存在了。我们再用代码的方式来实现一下 Redis 的 Set 去重实现代码如下// 待去重 URL
public static final String[] URLS {www.apigo.cn,www.baidu.com,www.apigo.cn
};Autowired
RedisTemplate redisTemplate;RequestMapping(/url)
public void urlRepeat() {for (int i 0; i URLS.length; i) {String url URLS[i];Long result redisTemplate.opsForSet().add(urlrepeat, url);if (result 0) {// 重复的 URLSystem.out.println(URL 已存在了 url);}}
}
以上程序的执行结果为URL 已存在了www.apigo.cn以上代码中我们借助了 Spring Data 中的 RedisTemplate 实现的在 Spring Boot 项目中要使用 RedisTemplate 对象我们需要先引入 spring-boot-starter-data-redis 框架配置信息如下!-- 添加操作 RedisTemplate 引用 --
dependencygroupIdorg.springframework.boot/groupIdartifactIdspring-boot-starter-data-redis/artifactId
/dependency
然后需要再项目中配置 Redis 的连接信息在 application.properties 中配置如下内容spring.redis.host127.0.0.1
spring.redis.port6379
#spring.redis.password123456 # Redis 服务器密码有密码的话需要配置此项
经过以上两个步骤之后我们就可以在 Spring Boot 的项目中正常的使用 RedisTemplate 对象来操作 Redis 了。3.数据库去重我们也可以借助数据库实现 URL 的重复判断首先我们先来设计一张 URL 的存储表如下图所示此表对应的 SQL 如下/**/
/* Table: urlinfo */
/**/
create table urlinfo
(id int not null auto_increment,url varchar(1000),ctime date,del boolean,primary key (id)
);/**/
/* Index: Index_url */
/**/
create index Index_url on urlinfo
(url
);其中 id 为自增的主键而 url 字段设置为索引设置索引可以加快查询的速度。我们先在数据库中添加两条测试数据如下图所示我们使用 SQL 语句查询如下图所示如果结果大于 0 则表明已经有重复的 URL 了否则表示没有重复的 URL。4.唯一索引去重我们也可以使用数据库的唯一索引来防止 URL 重复它的实现思路和前面 Set 集合的思想思路非常像。首先我们先为字段 URL 设置了唯一索引然后再添加 URL 数据如果能添加成功则表明 URL 不重复反之则表示重复。创建唯一索引的 SQL 实现如下create unique index Index_url on urlinfo
(url
);
5.Guava 布隆过滤器去重布隆过滤器Bloom Filter是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法缺点是有一定的误识别率和删除困难。布隆过滤器的核心实现是一个超大的位数组和几个哈希函数假设位数组的长度为 m哈希函数的个数为 k。以上图为例具体的操作流程假设集合里面有 3 个元素 {x, y, z}哈希函数的个数为 3。首先将位数组进行初始化将里面每个位都设置位 0。对于集合里面的每一个元素将元素依次通过 3 个哈希函数进行映射每次映射都会产生一个哈希值这个值对应位数组上面的一个点然后将位数组对应的位置标记为 1查询 W 元素是否存在集合中的时候同样的方法将 W 通过哈希映射到位数组上的 3 个点。如果 3 个点的其中有一个点不为 1则可以判断该元素一定不存在集合中。反之如果 3 个点都为 1则该元素可能存在集合中。注意此处不能判断该元素是否一定存在集合中可能存在一定的误判率。可以从图中可以看到假设某个元素通过映射对应下标为 4、5、6 这 3 个点。虽然这 3 个点都为 1但是很明显这 3 个点是不同元素经过哈希得到的位置因此这种情况说明元素虽然不在集合中也可能对应的都是 1这是误判率存在的原因。我们可以借助 Google 提供的 Guava 框架来操作布隆过滤器实现我们先在 pom.xml 中添加 Guava 的引用配置如下!-- 添加 Guava 框架 --
!-- https://mvnrepository.com/artifact/com.google.guava/guava --
dependencygroupIdcom.google.guava/groupIdartifactIdguava/artifactIdversion28.2-jre/version
/dependency
URL 判重的实现代码public class URLRepeat {// 待去重 URLpublic static final String[] URLS {www.apigo.cn,www.baidu.com,www.apigo.cn};public static void main(String[] args) {// 创建一个布隆过滤器BloomFilterString filter BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()),10, // 期望处理的元素数量0.01); // 期望的误报概率for (int i 0; i URLS.length; i) {String url URLS[i];if (filter.mightContain(url)) {// 用重复的 URLSystem.out.println(URL 已存在了 url);} else {// 将 URL 存储在布隆过滤器中filter.put(url);}}}
}
以上程序的执行结果为URL 已存在了www.apigo.cn6.Redis 布隆过滤器去重除了 Guava 的布隆过滤器我们还可以使用 Redis 的布隆过滤器来实现 URL 判重。在使用之前我们先要确保 Redis 服务器版本大于 4.0此版本以上才支持布隆过滤器并且开启了 Redis 布隆过滤器功能才能正常使用。以 Docker 为例我们来演示一下 Redis 布隆过滤器安装和开启首先下载 Redis 的布隆过器然后再在重启 Redis 服务时开启布隆过滤器如下图所示布隆过滤器使用布隆过滤器正常开启之后我们先用 Redis 的客户端 redis-cli 来实现一下布隆过滤器 URL 判重了实现命令如下在 Redis 中布隆过滤器的操作命令不多主要包含以下几个bf.add 添加元素bf.exists 判断某个元素是否存在bf.madd 添加多个元素bf.mexists 判断多个元素是否存在bf.reserve 设置布隆过滤器的准确率。接下来我们使用代码来演示一下 Redis 布隆过滤器的使用import redis.clients.jedis.Jedis;
import utils.JedisUtils;import java.util.Arrays;public class BloomExample {// 布隆过滤器 keyprivate static final String _KEY URLREPEAT_KEY;// 待去重 URLpublic static final String[] URLS {www.apigo.cn,www.baidu.com,www.apigo.cn};public static void main(String[] args) {Jedis jedis JedisUtils.getJedis();for (int i 0; i URLS.length; i) {String url URLS[i];boolean exists bfExists(jedis, _KEY, url);if (exists) {// 重复的 URLSystem.out.println(URL 已存在了 url);} else {bfAdd(jedis, _KEY, url);}}}/*** 添加元素* param jedis Redis 客户端* param key key* param value value* return boolean*/public static boolean bfAdd(Jedis jedis, String key, String value) {String luaStr return redis.call(bf.add, KEYS[1], KEYS[2]);Object result jedis.eval(luaStr, Arrays.asList(key, value),Arrays.asList());if (result.equals(1L)) {return true;}return false;}/*** 查询元素是否存在* param jedis Redis 客户端* param key key* param value value* return boolean*/public static boolean bfExists(Jedis jedis, String key, String value) {String luaStr return redis.call(bf.exists, KEYS[1], KEYS[2]);Object result jedis.eval(luaStr, Arrays.asList(key, value),Arrays.asList());if (result.equals(1L)) {return true;}return false;}
}
以上程序的执行结果为URL 已存在了www.apigo.cn总结本文介绍了 6 种 URL 去重的方案其中 Redis Set、Redis 布隆过滤器、数据库和唯一索引这 4 种解决方案适用于分布式系统如果是海量的分布式系统建议使用 Redis 布隆过滤器来实现 URL 去重如果是单机海量数据推荐使用 Guava 的布隆器来实现 URL 去重。
往期推荐
多图证明Java到底是值传递还是引用传递阿里为什么推荐使用LongAdder而不是volatile磊哥工作十几年了竟没有用过do-while文末送书关注下方二维码收获更多干货
