关于java:URL-去重的-6-种方案附详细实现代码

7次阅读

共计 5693 个字符，预计需要花费 15 分钟才能阅读完成。

URL 去重在咱们日常工作中和面试中很常遇到，比方这些：

能够看出，包含阿里，网易云、优酷、作业帮等出名互联网公司都呈现过相似的面试题，而且和 URL 去重比拟相似的，如 IP 黑 / 白名单判断等也经常出现在咱们的工作中，所以咱们本文就来“盘一盘”URL 去重的问题。

在不思考业务场景和数据量的状况下，咱们能够应用以下计划来实现 URL 的反复判断：

应用 Java 的 Set 汇合，依据增加时的后果来判断 URL 是否反复（增加胜利示意 URL 不反复）；
应用 Redis 中的 Set 汇合，依据增加时的后果来判断 URL 是否反复；
将 URL 都存储在数据库中，再通过 SQL 语句判断是否有反复的 URL；
把数据库中的 URL 一列设置为惟一索引，依据增加时的后果来判断 URL 是否反复；
应用 Guava 的布隆过滤器来实现 URL 判重；
应用 Redis 的布隆过滤器来实现 URL 判重。

以上计划的具体实现如下。

Set 汇合天生具备不可重复性，应用它只能存储值不雷同的元素，如果值雷同增加就会失败，因而咱们能够通过增加 Set 汇合时的后果来断定 URL 是否反复，实现代码如下：

public class URLRepeat {
    // 待去重 URL
    public static final String[] URLS = {
            "www.apigo.cn",
            "www.baidu.com",
            "www.apigo.cn"
    };
    public static void main(String[] args) {Set<String> set = new HashSet();
        for (int i = 0; i < URLS.length; i++) {String url = URLS[i];
            boolean result = set.add(url);
            if (!result) {
                // 反复的 URL
                System.out.println("URL 已存在了：" + url);
            }
        }
    }
}

程序的执行后果为：

URL 已存在了：www.apigo.cn

从上述后果能够看出，应用 Set 汇合能够实现 URL 的判重性能。

应用 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) {
            // 反复的 URL
            System.out.println("URL 已存在了：" + url);
        }
    }
}

以上程序的执行后果为：

URL 已存在了：www.apigo.cn

以上代码中咱们借助了 Spring Data 中的 RedisTemplate 实现的，在 Spring Boot 我的项目中要应用 RedisTemplate 对象咱们须要先引入 spring-boot-starter-data-redis 框架，配置信息如下：

<!-- 增加操作 RedisTemplate 援用 -->
<dependency>
    <groupId>org.springframework.boot</groupId>
    <artifactId>spring-boot-starter-data-redis</artifactId>
</dependency>

而后须要再我的项目中配置 Redis 的连贯信息，在 application.properties 中配置如下内容：

spring.redis.host=127.0.0.1
spring.redis.port=6379
#spring.redis.password=123456 # Redis 服务器明码，有明码的话须要配置此项

通过以上两个步骤之后，咱们就能够在 Spring Boot 的我的项目中失常的应用 RedisTemplate 对象来操作 Redis 了。

咱们也能够借助数据库实现 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。

咱们也能够应用数据库的惟一索引来避免 URL 反复，它的实现思路和后面 Set 汇合的思维思路十分像。

首先咱们先为字段 URL 设置了惟一索引，而后再增加 URL 数据，如果能增加胜利则表明 URL 不反复，反之则示意反复。

创立惟一索引的 SQL 实现如下：

create unique index Index_url on urlinfo
(url);

布隆过滤器（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 -->
<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>28.2-jre</version>
</dependency>

URL 判重的实现代码：

public class URLRepeat {
    // 待去重 URL
    public static final String[] URLS = {
            "www.apigo.cn",
            "www.baidu.com",
            "www.apigo.cn"
    };

    public static void main(String[] args) {
        // 创立一个布隆过滤器
        BloomFilter<String> 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)) {
                // 用反复的 URL
                System.out.println("URL 已存在了：" + url);
            } else {
                // 将 URL 存储在布隆过滤器中
                filter.put(url);
            }
        }
    }
}

以上程序的执行后果为：

URL 已存在了：www.apigo.cn

除了 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 {
    // 布隆过滤器 key
    private static final String _KEY = "URLREPEAT_KEY";
    
    // 待去重 URL
    public 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) {
                // 反复的 URL
                System.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 中文社群」发送“面试”，支付我整顿的最新面试复习资料。

正文完

java

发表至： java

2020-09-10

0

关于java:太妙了Spring-boot-整合-Mybatis-Druid还能配置监控

关于java:java-编程技术异步通信

全网最全这份深入讲解jdk和jvm原理的笔记刷新了我对JVM的认知

关于java:免费分享Java高并发与多线程的优秀图书

关于react-hooks:Function组件Hooks-vs-Class组件

关于java:URL-去重的-6-种方案附详细实现代码

URL 去重思路

URL 去重实现计划

1. 应用 Java 的 Set 汇合判重

2.Redis Set 汇合去重

3. 数据库去重

4. 惟一索引去重

5.Guava 布隆过滤器去重

6.Redis 布隆过滤器去重

总结

站内搜索