블룸 필터는 비트 배열(BitSet)을 사용하여 집합을 표현하고 특정 수의 해시 함수를 통해 요소를 맵의 위치에 결합하는 매우 공간 효율적인 무작위 데이터 구조입니다. 요소가 이 세트에 속하는지 여부를 확인하는 데 사용되는 비트 배열입니다.
한 요소에 대해 여러 개의 해시 함수를 통해 여러 개의 해시 값이 생성되고, 여러 개의 해시 값 중 해당 비트가 비트 배열에 있으면 해당 비트가 1로 설정됩니다. 모두 1이면 해당 요소가 집합에 있을 수 있는 것으로 간주됩니다. 해시 값의 해당 비트 중 하나 이상이 0인 경우 해당 요소는 집합에 없어야 합니다. 이 방법은 더 작은 공간에서 효율적인 검색을 달성할 수 있지만, 거짓양성률이 발생할 수 있습니다.
일반적인 Bloom 필터에는 세 가지 매개 변수가 포함됩니다. 비트 배열의 크기(즉, 저장된 요소 수), 채우기 요소(즉, 거짓 긍정 비율); 즉, 비트 배열의 크기에 대한 요소 수의 비율입니다.
위 그림과 같이 Bloom 필터의 기본 동작 과정은 비트 배열 및 해시 함수 초기화, 요소 삽입, 해당 요소가 집합에 있는지 확인 등을 포함합니다. 그 중 각 요소는 여러 해시 함수에 의해 비트 배열의 여러 위치에 매핑됩니다. 요소가 집합에 있는지 확인할 때 해당 요소가 있을 수 있다고 간주하기 전에 해당 비트가 모두 1로 설정되어 있는지 확인해야 합니다. 컬렉션에 포함되어 있습니다.
스팸 필터링: Bloom 필터에서 모든 블랙리스트 이메일의 해당 해시 값을 1로 설정합니다. 각각의 새 이메일에 대해 해당 해시 값을 Bloom 필터의 해당 위치가 모두 1인지 확인합니다. .그렇다면 이메일은 스팸으로 간주되고 그렇지 않으면 일반 이메일일 수 있습니다.
URL 중복제거: 크롤링된 URL에 해당하는 해시 값을 Bloom 필터의 해당 위치에 1로 설정합니다. 각각의 새 URL에서 Bloom 필터의 해당 위치에 있는 해시 값이 모두 1인지 확인하세요. 그렇다면 URL이 크롤링된 것으로 간주됩니다. 그렇지 않으면 크롤링이 필요합니다.
캐시 분석: 해당 해시를 설정합니다. Bloom 필터에서 캐시에 있는 모든 데이터의 값을 1로 해싱하고, 각 쿼리의 키 값을 Bloom 필터의 해당 해시 값 위치가 모두 1인지 확인합니다. 그렇다면 키 값으로 간주합니다. 그렇지 않으면 데이터베이스에서 쿼리하여 캐시에 추가해야 합니다.
비트 배열 크기가 커짐에 따라 Bloom 필터의 오탐률은 감소하지만 메모리 오버헤드와 계산 시간도 증가한다는 점에 유의해야 합니다. Bloom 필터에 대한 이해를 돕기 위해 다음은 Java 코드를 사용하여 간단한 Bloom 필터를 구현합니다.
import java.util.BitSet; import java.util.Random; public class BloomFilter { private BitSet bitSet; // 位集，用于存储哈希值 private int bitSetSize; // 位集大小 private int numHashFunctions; // 哈希函数数量 private Random random; // 随机数生成器 // 构造函数，根据期望元素数量和错误率计算位集大小和哈希函数数量 public BloomFilter(int expectedNumItems, double falsePositiveRate) { this.bitSetSize = optimalBitSetSize(expectedNumItems, falsePositiveRate); this.numHashFunctions = optimalNumHashFunctions(expectedNumItems, bitSetSize); this.bitSet = new BitSet(bitSetSize); this.random = new Random(); } // 根据期望元素数量和错误率计算最佳位集大小 private int optimalBitSetSize(int expectedNumItems, double falsePositiveRate) { int bitSetSize = (int) Math.ceil(expectedNumItems * (-Math.log(falsePositiveRate) / Math.pow(Math.log(2), 2))); return bitSetSize; } // 根据期望元素数量和位集大小计算最佳哈希函数数量 private int optimalNumHashFunctions(int expectedNumItems, int bitSetSize) { int numHashFunctions = (int) Math.ceil((bitSetSize / expectedNumItems) * Math.log(2)); return numHashFunctions; } // 添加元素到布隆过滤器中 public void add(String item) { // 计算哈希值 int[] hashes = createHashes(item.getBytes(), numHashFunctions); // 将哈希值对应的位设置为 true for (int hash : hashes) { bitSet.set(Math.abs(hash % bitSetSize), true); } } // 检查元素是否存在于布隆过滤器中 public boolean contains(String item) { // 计算哈希值 int[] hashes = createHashes(item.getBytes(), numHashFunctions); // 检查哈希值对应的位是否都为 true for (int hash : hashes) { if (!bitSet.get(Math.abs(hash % bitSetSize))) { return false; } } return true; } // 计算给定数据的哈希值 private int[] createHashes(byte[] data, int numHashes) { int[] hashes = new int[numHashes]; int hash2 = Math.abs(random.nextInt()); int hash3 = Math.abs(random.nextInt()); for (int i = 0; i < numHashes; i++) { // 使用两个随机哈希函数计算哈希值 hashes[i] = Math.abs((hash2 * i) + (hash3 * i) + i) % data.length; } return hashes; } }
위 내용은 Java에서 Bloom 필터를 적용하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
