Java의 컬렉션에 요소가 있는지 빠르게 확인하는 방법

1. 블룸 필터란?

블룸 필터는 1970년에 Bloom이라는 사람이 제안했습니다.

실제로는 바이너리 벡터(또는 비트 배열)와 일련의 랜덤 매핑 함수(해시 함수)로 구성된 데이터 구조라고 생각하면 됩니다.

일반적인 알고리즘에 비해 공간 효율성과 쿼리 시간이 훨씬 좋다는 장점이 있고, 오인식률이 일정하고 삭제가 어렵다는 단점이 있습니다.

2. 구현 원리

먼저 사진을 찍자

Bloom 필터 알고리즘의 주요 아이디어는 n개의 해시 함수를 사용하여 해시한 다음 서로 다른 해시 값을 얻어 매핑되는 것입니다. 해시에 따라 배열의 다른 인덱스 위치(이 배열의 길이는 매우 길 수 있음)에 해당하는 인덱스 비트의 값을 1로 설정합니다.

요소가 집합에 나타나는지 확인하려면 k개의 서로 다른 해시 함수를 사용하여 해시 값을 계산하고 해시 값의 해당 인덱스 위치의 값이 1인지 확인하는 것입니다. 하나가 1이 아닌 경우 요소가 컬렉션에 존재하지 않습니다.

하지만 요소가 집합에 있지만 요소가 없다고 판단하는 것도 가능합니다. 이 요소의 모든 인덱스 위치 위의 1은 다른 요소에 의해 설정되므로 오판의 가능성이 어느 정도 발생합니다. 위의 내용은 세트에 있을 수 있습니다.) 근본 원인은 특정 해시 충돌이 발생한다는 것입니다.

참고: 거짓양성률이 낮을수록 해당 성능도 낮아집니다.

3. 기능

블룸 필터는 요소가 집합에 있는지 여부를 결정하는 데 사용할 수 있습니다. 다른 데이터 구조와 비교할 때 블룸 필터는 공간 및 시간 제약이 큽니다.

위의 단어인 '아마도'에 주목하세요. 여기에는 서스펜스가 있는데, 이에 대해서는 아래에서 자세히 분석하겠습니다.

해당 데이터가 존재하는지 확인

캐시 침투 방지(데이터베이스를 요청하기 위해 캐시를 직접 우회하지 않도록 요청한 데이터가 유효한지 확인) 등, 메일함의 스팸 필터링, 블랙리스트 기능 등

4. 구체적인 구현

Bloom 필터의 알고리즘 아이디어를 읽은 후 구체적인 구현에 대해 설명하겠습니다.

먼저 예를 들어 Wangcai와 Xiaoqiang이라는 두 개의 문자열이 각각 3번씩 해시된 다음 해당 배열의 인덱스 위치 값(배열 길이가 16이라고 가정)이 설정되었다고 가정합니다. 해시 결과가 1이면 먼저 번영이라는 문구를 살펴보겠습니다.

세 번 해싱한 후 값은 2, 4, 6입니다. 그러면 인덱스 값을 얻을 수 있습니다. ​​​2, 4, 6이므로 배열의 인덱스(2, 4, 6) 값은 1로 설정되고 나머지는 0으로 처리됩니다. 이제 Wangcai를 찾아야 한다고 가정해 보겠습니다. 동일한 3개의 해시 후에는 인덱스 2, 4, 6에 해당하는 위치의 값을 찾을 수 있습니다. 둘 다 1이면 부가 존재할 수 있다고 판단할 수 있습니다.

그 다음 Xiaoqiang을 Bloom 필터에 삽입합니다. 실제 과정은 위와 같습니다. 얻은 첨자가 1, 3, 5라고 가정합니다. Wangcai 및 Xiaoqiang과 결합된 실제 배열인 Bloom 필터는 다음과 같습니다.

이제 데이터는 9527입니다. 현재 요구 사항은 9527이 존재하는지 확인하는 것입니다. 첨자는 3개입니다. 5, 6, 7입니다. 첨자 7이 붙은 위치의 값이 0인 것으로 나타나므로 9527은 존재하지 않아야 한다고 확실히 판단할 수 있다.

그리고 또 다른 국산 007이 나왔습니다. 3번의 해시 후에 얻은 첨자는 2, 3, 5였습니다. 첨자 2, 3, 5에 해당하는 값은 모두 1인 것으로 확인되어 대략적으로 판단할 수 있습니다. 그 국내 007 그것이 존재할 수도 있습니다. 그런데 사실 지금 시연을 해보니 국내 007은 전혀 존재하지 않습니다. 지수 위치 2, 3, 5의 값이 1인 이유는 다른 데이터 설정 때문입니다.

그러고보니 블룸 필터의 역할을 이해하셨는지 모르겠네요.

5. 코드 구현

Java 프로그래머로서 우리는 많은 프레임워크와 도구를 사용하며 기본적으로 Google을 사용하여 도구를 캡슐화합니다. 물론 탐색할 수 있는 다른 방법도 있습니다.

먼저 종속성 추가

<!--布隆过滤依赖-->
<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>25.1-jre</version>
</dependency>

코드 구현

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import java.nio.charset.Charset;
public class BloomFilterDemo {
        public static void main(String[] args) {
        /**
         * 创建一个插入对象为一亿，误报率为0.01%的布隆过滤器
         * 不存在一定不存在
         * 存在不一定存在
         * ----------------
         *  Funnel 对象：预估的元素个数，误判率
         *  mightContain ：方法判断元素是否存在
         */
        BloomFilter<CharSequence> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.forName("utf-8")), 100000000, 0.0001);
        bloomFilter.put("死");
        bloomFilter.put("磕");
        bloomFilter.put("Redis");
        System.out.println(bloomFilter.mightContain("Redis"));
        System.out.println(bloomFilter.mightContain("Java"));
    }
}

구체적인 설명은 댓글에 적어두었습니다. 이제 모든 사람이 Bloom 필터와 사용 방법을 이해해야 한다고 생각합니다.

6. 실제 전투

이 시나리오를 시뮬레이션해 보겠습니다. 블룸 필터를 통해 캐시 침투를 해결합니다.

우선 캐시 침투가 무엇인지 아시나요?

캐시 침투란 캐시나 데이터베이스에 없는 데이터에 사용자가 접근한다는 뜻입니다. 캐시에 존재하지 않기 때문에 동시성이 높으면 데이터베이스에 접근하게 됩니다. 데이터베이스를 물리치는 것은 쉽습니다

그렇다면 블룸 필터는 이 문제를 어떻게 해결할까요? 그 사람

的原理是这样子的：将数据库中所有的查询条件，放入布隆过滤器中，当一个查询请求过来时，先经过布隆过滤器进行查，如果判断请求查询值存在，则继续查；如果判断请求查询不存在，直接丢弃。

其代码如下：

String get(String key) {
    String value = redis.get(key);     
    if (value  == null) {
        if(!bloomfilter.mightContain(key)){
            return null; 
        }else{
            value = db.get(key); 
            redis.set(key, value); 
        }    
    }
    return value；
}

위 내용은 Java의 컬렉션에 요소가 있는지 빠르게 확인하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!