当前位置： 首页 > article >正文

海量数据面试题

article 2024/10/28 18:24:26

请添加图片描述

⭐️前言⭐️

本篇文章主要针对在面试时可能涉及到的海量数据的面试题，该类型面试题常常考虑通过位图、布隆过滤器或者哈希的方式来解决。

🍉欢迎点赞 👍 收藏 ⭐留言评论

🍉博主将持续更新学习记录收获，友友们有任何问题可以在评论区留言

🍉博客中涉及源码及博主日常练习代码均已上传GitHub

请添加图片描述

📍内容导读📍

  • 🍅 海量数据面试题
    • 1. 哈希切割
    • 2. 位图应用
      • 2.1 只出现一次的整数
        • 解法一：哈希切割+哈希表
        • 解法二：两个位图
        • 解法三：2-bit位图（两个模拟实现）
      • 2.2 两个文件交集
        • 解法一：哈希切割
        • 解法二：位图
      • 2.3 交集、并集和差集
      • 2.4 不超过2次的所有整数
    • 3. 布隆过滤器
      • 精确算法和近似算法
    • 4. 爬虫URL去重
      • 1. 设计思路
      • 2. 数据结构
      • 3. 核心方法
      • 4. 时间和空间复杂度分析
      • 5. 优点和局限性

🍅 海量数据面试题

1. 哈希切割

给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？ 与上题条件相同，如何找到top K的IP？

1、找到出现次数最多的IP地址

思路：

  • 哈希切割大文件：根据IP地址进行哈希分区，将大文件切分为多个小文件，每个小文件的大小可以控制在内存可处理的范围内。
  • 统计每个小文件中的IP频率：使用哈希表统计每个小文件中的IP出现次数。
  • 合并结果：对所有小文件的结果进行汇总，找出出现次数最多的IP。

实现步骤：
1、第一遍扫描文件，进行哈希切割

  • 计算每个IP的哈希值，将其划分到不同的小文件中。

2、第二遍遍历小文件，统计IP频率

  • 使用哈希表统计IP出现的次数。

3、合并结果，找出出现次数最多的IP

  • 遍历所有小文件的统计结果，找出出现次数最多的IP。

代码示例：

import java.io.*;
import java.util.HashMap;
import java.util.Map;

public class MostFrequentIP {

    private static final int NUM_PARTITIONS = 100; // 假设划分为100个小文件

    // 哈希切割大文件
    public static void partitionLogFile(String inputFile) throws IOException {
        BufferedReader reader = new BufferedReader(new FileReader(inputFile));
        BufferedWriter[] writers = new BufferedWriter[NUM_PARTITIONS];

        // 初始化写入流
        for (int i = 0; i < NUM_PARTITIONS; i++) {
            writers[i] = new BufferedWriter(new FileWriter("partition_" + i + ".txt"));
        }

        // 按行读取日志文件
        String line;
        while ((line = reader.readLine()) != null) {
            String ip = extractIP(line);
            int partitionIndex = Math.abs(ip.hashCode()) % NUM_PARTITIONS;
            writers[partitionIndex].write(ip + "\n");
        }

        // 关闭所有写入流
        for (BufferedWriter writer : writers) {
            writer.close();
        }
        reader.close();
    }

    // 从日志行中提取IP地址（假设每行都是IP地址）
    private static String extractIP(String line) {
        return line.trim();
    }

    // 统计每个小文件中的IP频率
    public static Map<String, Integer> countIPs(String partitionFile) throws IOException {
        Map<String, Integer> ipCountMap = new HashMap<>();
        BufferedReader reader = new BufferedReader(new FileReader(partitionFile));

        String ip;
        while ((ip = reader.readLine()) != null) {
            ipCountMap.put(ip, ipCountMap.getOrDefault(ip, 0) + 1);
        }
        reader.close();
        return ipCountMap;
    }

    // 找出出现次数最多的IP
    public static String findMostFrequentIP() throws IOException {
        String mostFrequentIP = null;
        int maxCount = 0;

        // 遍历所有小文件的统计结果
        for (int i = 0; i < NUM_PARTITIONS; i++) {
            Map<String, Integer> ipCountMap = countIPs("partition_" + i + ".txt");

            for (Map.Entry<String, Integer> entry : ipCountMap.entrySet()) {
                if (entry.getValue() > maxCount) {
                    maxCount = entry.getValue();
                    mostFrequentIP = entry.getKey();
                }
            }
        }
        return mostFrequentIP;
    }

    public static void main(String[] args) throws IOException {
        String inputFile = "large_log_file.txt"; // 假设大文件名为large_log_file.txt

        // 1. 分区
        partitionLogFile(inputFile);

        // 2. 找出出现次数最多的IP
        String mostFrequentIP = findMostFrequentIP();
        System.out.println("出现次数最多的IP是：" + mostFrequentIP);
    }
}

2、找到Top K个出现次数最多的IP

思路：
1.哈希切割大文件：与找到最多的IP相同。
2.统计每个小文件的IP频率：使用哈希表统计每个小文件中的IP频率。
3.合并结果：使用最小堆（Min Heap）来维护前K个频率最高的IP。

实现步骤：
1.第一遍扫描文件，进行哈希切割：与上面一致。
2.第二遍遍历小文件，统计IP频率并维护Top K

  • 使用哈希表统计小文件中的IP频率。
  • 使用最小堆来维护全局Top K。

3.返回Top K结果。

代码实现：

import java.io.*;
import java.util.*;

public class TopKFrequentIPs {

    private static final int NUM_PARTITIONS = 100; // 假设划分为100个小文件
    private static final int K = 10; // 假设找前10个IP

    // 哈希切割大文件
    public static void partitionLogFile(String inputFile) throws IOException {
        BufferedReader reader = new BufferedReader(new FileReader(inputFile));
        BufferedWriter[] writers = new BufferedWriter[NUM_PARTITIONS];

        for (int i = 0; i < NUM_PARTITIONS; i++) {
            writers[i] = new BufferedWriter(new FileWriter("partition_" + i + ".txt"));
        }

        String line;
        while ((line = reader.readLine()) != null) {
            String ip = extractIP(line);
            int partitionIndex = Math.abs(ip.hashCode()) % NUM_PARTITIONS;
            writers[partitionIndex].write(ip + "\n");
        }

        for (BufferedWriter writer : writers) {
            writer.close();
        }
        reader.close();
    }

    // 从日志行中提取IP地址
    private static String extractIP(String line) {
        return line.trim();
    }

    // 统计每个小文件中的IP频率并维护Top K
    public static PriorityQueue<Map.Entry<String, Integer>> findTopK() throws IOException {
        PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(K, Comparator.comparingInt(Map.Entry::getValue));

        for (int i = 0; i < NUM_PARTITIONS; i++) {
            Map<String, Integer> ipCountMap = countIPs("partition_" + i + ".txt");

            // 维护最小堆中的Top K
            for (Map.Entry<String, Integer> entry : ipCountMap.entrySet()) {
                if (minHeap.size() < K) {
                    minHeap.offer(entry);
                } else if (entry.getValue() > minHeap.peek().getValue()) {
                    minHeap.poll();
                    minHeap.offer(entry);
                }
            }
        }
        return minHeap;
    }

    // 统计每个小文件中的IP频率
    public static Map<String, Integer> countIPs(String partitionFile) throws IOException {
        Map<String, Integer> ipCountMap = new HashMap<>();
        BufferedReader reader = new BufferedReader(new FileReader(partitionFile));

        String ip;
        while ((ip = reader.readLine()) != null) {
            ipCountMap.put(ip, ipCountMap.getOrDefault(ip, 0) + 1);
        }
        reader.close();
        return ipCountMap;
    }

    public static void main(String[] args) throws IOException {
        String inputFile = "large_log_file.txt"; // 假设大文件名为large_log_file.txt

        // 1. 分区
        partitionLogFile(inputFile);

        // 2. 找到Top K个出现次数最多的IP
        PriorityQueue<Map.Entry<String, Integer>> topK = findTopK();
        List<Map.Entry<String, Integer>> result = new ArrayList<>(topK);
        result.sort((a, b) -> b.getValue() - a.getValue()); // 从大到小排序

        System.out.println("Top K个出现次数最多的IP：");
        for (Map.Entry<String, Integer> entry : result) {
            System.out.println(entry.getKey() + " : " + entry.getValue());
        }
    }
}

2. 位图应用

2.1 只出现一次的整数

题目：给定100亿个整数，设计算法找到只出现一次的整数？

由于数据量非常大，我们需要考虑内存限制，以及如何在分布式或分段的情况下进行计算。

解法一：哈希切割+哈希表

思路概述：
解决这样的大规模问题可以采用哈希切割（Hash Partitioning）和位图（BitMap）相结合的方式。具体步骤如下：

1、哈希切割数据：将100亿个整数划分为多个小文件，每个文件只包含部分整数。
2、统计每个小文件中的整数频率：在小文件中，使用哈希表记录每个整数出现的次数。
3、合并结果：汇总所有小文件的结果，找出只出现一次的整数。

实现步骤：
1、第一遍扫描文件，进行哈希切割

  • 根据整数值的哈希值，将其划分到多个小文件中。

2、第二遍遍历小文件，统计每个整数的频率

  • 对每个小文件使用哈希表统计出现次数。

3、合并结果

  • 汇总所有小文件的统计结果，找到只出现一次的整数。

代码示例：

import java.io.*;
import java.util.HashMap;
import java.util.Map;

public class FindUniqueNumber {

    private static final int NUM_PARTITIONS = 1000; // 假设划分为1000个小文件

    // 哈希切割大文件
    public static void partitionLargeFile(String inputFile) throws IOException {
        BufferedReader reader = new BufferedReader(new FileReader(inputFile));
        BufferedWriter[] writers = new BufferedWriter[NUM_PARTITIONS];

        // 初始化写入流
        for (int i = 0; i < NUM_PARTITIONS; i++) {
            writers[i] = new BufferedWriter(new FileWriter("partition_" + i + ".txt"));
        }

        // 按行读取大文件
        String line;
        while ((line = reader.readLine()) != null) {
            int num = Integer.parseInt(line.trim());
            int partitionIndex = Math.abs(num) % NUM_PARTITIONS;
            writers[partitionIndex].write(num + "\n");
        }

        // 关闭所有写入流
        for (BufferedWriter writer : writers) {
            writer.close();
        }
        reader.close();
    }

    // 统计每个小文件中的整数频率
    public static Map<Integer, Integer> countFrequency(String partitionFile) throws IOException {
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        BufferedReader reader = new BufferedReader(new FileReader(partitionFile));

        String line;
        while ((line = reader.readLine()) != null) {
            int num = Integer.parseInt(line.trim());
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }
        reader.close();
        return frequencyMap;
    }

    // 找出只出现一次的整数
    public static Integer findUniqueNumber() throws IOException {
        for (int i = 0; i < NUM_PARTITIONS; i++) {
            Map<Integer, Integer> frequencyMap = countFrequency("partition_" + i + ".txt");

            // 遍历哈希表，找到只出现一次的整数
            for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
                if (entry.getValue() == 1) {
                    return entry.getKey(); // 返回找到的第一个只出现一次的整数
                }
            }
        }
        return null; // 没有找到只出现一次的整数
    }

    public static void main(String[] args) throws IOException {
        String inputFile = "large_numbers_file.txt"; // 假设大文件名为large_numbers_file.txt

        // 1. 哈希切割大文件
        partitionLargeFile(inputFile);

        // 2. 找到只出现一次的整数
        Integer uniqueNumber = findUniqueNumber();
        if (uniqueNumber != null) {
            System.out.println("只出现一次的整数是：" + uniqueNumber);
        } else {
            System.out.println("没有找到只出现一次的整数。");
        }
    }
}
解法二：两个位图

如果整数的范围是已知且不大（如0到2^31-1），可以使用位图来记录每个整数的频率。这里我们用两个位图分别记录出现1次和出现2次及以上的整数。

实现步骤
1、初始化两个位图bitMap1和bitMap2。
2、第一遍扫描：对于每个整数num：

  • 如果bitMap1中对应的位为0，则将其置为1。
  • 如果bitMap1中对应的位已经为1，则将bitMap2对应的位置为1。

3、第二遍扫描：找出只在bitMap1中为1且在bitMap2中为0的整数。

代码示例：

import java.io.*;
import java.util.BitSet;

public class FindUniqueUsingBitMap {

    private static final int MAX_RANGE = Integer.MAX_VALUE; // 假设整数范围为0到2^31-1

    // 用两个位图记录频率
    private BitSet bitMap1 = new BitSet(MAX_RANGE);
    private BitSet bitMap2 = new BitSet(MAX_RANGE);

    // 第一遍扫描数据
    public void scanFile(String inputFile) throws IOException {
        BufferedReader reader = new BufferedReader(new FileReader(inputFile));
        String line;
        while ((line = reader.readLine()) != null) {
            int num = Integer.parseInt(line.trim());

            if (!bitMap1.get(num)) {
                bitMap1.set(num); // 第一次出现，将bitMap1对应位设为1
            } else {
                bitMap2.set(num); // 第二次出现，将bitMap2对应位设为1
            }
        }
        reader.close();
    }

    // 找出只出现一次的整数
    public int findUnique() {
        for (int i = 0; i < MAX_RANGE; i++) {
            // 只在bitMap1中为1，且bitMap2中为0
            if (bitMap1.get(i) && !bitMap2.get(i)) {
                return i;
            }
        }
        return -1; // 没有找到只出现一次的整数
    }

    public static void main(String[] args) throws IOException {
        String inputFile = "large_numbers_file.txt"; // 假设大文件名为large_numbers_file.txt
        FindUniqueUsingBitMap findUnique = new FindUniqueUsingBitMap();

        // 1. 扫描大文件
        findUnique.scanFile(inputFile);

        // 2. 找出只出现一次的整数
        int uniqueNumber = findUnique.findUnique();
        if (uniqueNumber != -1) {
            System.out.println("只出现一次的整数是：" + uniqueNumber);
        } else {
            System.out.println("没有找到只出现一次的整数。");
        }
    }
}
解法三：2-bit位图（两个模拟实现）

解决方案：2-bit 位图
在一个2-bit位图中，每个整数对应两个位来表示其状态：

  • 00：表示该整数从未出现。
  • 01：表示该整数出现一次。
  • 10：表示该整数出现两次。
  • 11：表示该整数出现三次及以上。

实现思路
1、初始化2-bit位图。
2、扫描输入数据：

  • 如果当前整数的状态为00，将其状态设置为01。
  • 如果当前整数的状态为01，将其状态设置为10。
  • 如果当前整数的状态为10，保持不变。

3、再次扫描2-bit位图，找到状态为01的整数，即只出现一次的整数。

Java中没有直接2-bit位图的实现，可以借助两个1-bit位图 BitSet模拟实现2-bit位图的四个状态，同时也可以如下所示自己实现2-bit位图。

2-bit位图模拟实现：

import java.util.Arrays;

public class TwoBitMap {
    private byte[] elem; // 2-bit位图的字节数组
    public int usedSize; // 用于记录非零位的个数

    public TwoBitMap() {
        // 默认给一个大小
        elem = new byte[1];
    }

    /**
     * 初始化n个整数的2-bit位图
     * @param n 整数范围
     */
    public TwoBitMap(int n) {
        elem = new byte[n / 4 + 1]; // 每个字节可存储4个整数的状态
    }

    /**
     * 获取整数num的状态
     * @param num 整数
     * @return 状态值（00、01、10或11）
     */
    public int get(int num) {
        if (num < 0) {
            throw new IndexOutOfBoundsException();
        }
        int byteIndex = num / 4;         // 计算字节索引
        int bitOffset = (num % 4) * 2;   // 计算在字节内的偏移量

        // 提取对应的2-bit状态
        return (elem[byteIndex] >> bitOffset) & 0b11;
    }

    /**
     * 设置整数num的状态
     * @param num 整数
     * @param state 新的状态值（00、01、10或11）
     */
    public void set(int num, int state) {
        if (num < 0 || state < 0 || state > 3) { // 状态值应为0到3
            throw new IndexOutOfBoundsException();
        }
        int byteIndex = num / 4;
        int bitOffset = (num % 4) * 2;

        // 扩容
        if (byteIndex > elem.length - 1) {
            elem = Arrays.copyOf(elem, byteIndex + 1);
        }

        // 清除当前2-bit状态
        elem[byteIndex] &= ~(0b11 << bitOffset);
        // 设置新的2-bit状态
        elem[byteIndex] |= (state << bitOffset);
        usedSize++;
    }

    /**
     * 更新整数num的状态
     * 00 -> 01, 01 -> 10, 10 -> 11, 11保持不变
     * @param num 整数
     */
    public void update(int num) {
        int currentState = get(num);

        // 根据当前状态进行更新
        if (currentState == 0) {
            set(num, 1); // 00 -> 01
        } else if (currentState == 1) {
            set(num, 2); // 01 -> 10
        } else if (currentState == 2) {
            set(num, 3); // 10 -> 11
        }
        // 如果是11，则不变
    }

    /**
     * 统计2-bit位图中非零位的个数
     * @return 非零位的个数
     */
    public int getUsedSize() {
        return this.usedSize;
    }

    public static void main(String[] args) {
        int[] array = {1, 2, 3, 10, 4, 18, 13, 2, 10, 18, 3}; // 测试用例
        TwoBitMap twoBitMap = new TwoBitMap(18);

        // 更新2-bit位图状态
        for (int i = 0; i < array.length; i++) {
            twoBitMap.update(array[i]);
        }

        // 找出只出现一次的整数
        System.out.println("只出现一次的整数：");
        for (int i = 0; i <= 18; i++) {
            if (twoBitMap.get(i) == 1) { // 01表示只出现一次
                System.out.println(i);
            }
        }

        // 找出只出现两次的整数
        System.out.println("只出现两次的整数：");
        for (int i = 0; i <= 18; i++) {
            if (twoBitMap.get(i) == 2) { // 10表示只出现两次
                System.out.println(i);
            }
        }

        // 找出出现三次及以上的整数
        System.out.println("出现三次及以上的整数：");
        for (int i = 0; i <= 18; i++) {
            if (twoBitMap.get(i) == 3) { // 11表示出现三次及以上
                System.out.println(i);
            }
        }
    }
}

2.2 两个文件交集

题目：
给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？

解法一：哈希切割

思路概述
我们可以将两个大文件进行哈希切割，将整数划分成多个较小的分区，每个分区的数据量可以控制在内存可处理的范围内。然后在每个分区内使用位图或哈希表计算交集。

实现步骤

  1. 哈希切割
  • 首先对两个文件进行哈希切割，将大文件划分成多个较小的分区，每个分区可以独立处理。
  • 通过哈希函数，将相同的整数映射到相同的对应分区文件中，这样可以确保相同的整数出现在相同的分区。
  1. 统计交集
  • 针对每个分区文件，使用位图（BitMap）或哈希表来存储和查找交集。
  1. 合并结果
  • 对每个分区的结果进行汇总，得到全局的交集。

具体代码实现（Java）

代码说明

  1. 使用哈希切割分区文件。
  2. 在分区文件中寻找交集。
  3. 合并各个分区的交集。
import java.io.*;
import java.util.BitSet;
import java.util.HashSet;
import java.util.Set;

public class FindIntersection {

    private static final int NUM_PARTITIONS = 100; // 假设划分为100个小文件
    private static final int MAX_RANGE = Integer.MAX_VALUE; // 假设整数范围为0到2^31-1

    // 哈希切割大文件
    public static void partitionFile(String inputFile, String outputPrefix) throws IOException {
        BufferedReader reader = new BufferedReader(new FileReader(inputFile));
        BufferedWriter[] writers = new BufferedWriter[NUM_PARTITIONS];

        // 初始化写入流
        for (int i = 0; i < NUM_PARTITIONS; i++) {
            writers[i] = new BufferedWriter(new FileWriter(outputPrefix + "_" + i + ".txt"));
        }

        // 按行读取大文件并进行哈希切割
        String line;
        while ((line = reader.readLine()) != null) {
            int num = Integer.parseInt(line.trim());
            int partitionIndex = Math.abs(num) % NUM_PARTITIONS;
            writers[partitionIndex].write(num + "\n");
        }

        // 关闭所有写入流
        for (BufferedWriter writer : writers) {
            writer.close();
        }
        reader.close();
    }

    // 找出分区文件的交集
    public static Set<Integer> findIntersectionInPartition(String file1, String file2) throws IOException {
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> intersection = new HashSet<>();

        // 读取第一个分区文件，将整数存入集合
        BufferedReader reader1 = new BufferedReader(new FileReader(file1));
        String line;
        while ((line = reader1.readLine()) != null) {
            int num = Integer.parseInt(line.trim());
            set1.add(num);
        }
        reader1.close();

        // 读取第二个分区文件，查找交集
        BufferedReader reader2 = new BufferedReader(new FileReader(file2));
        while ((line = reader2.readLine()) != null) {
            int num = Integer.parseInt(line.trim());
            if (set1.contains(num)) {
                intersection.add(num);
            }
        }
        reader2.close();

        return intersection;
    }

    // 合并所有分区的交集
    public static Set<Integer> findTotalIntersection(String filePrefix1, String filePrefix2) throws IOException {
        Set<Integer> totalIntersection = new HashSet<>();

        // 遍历所有分区
        for (int i = 0; i < NUM_PARTITIONS; i++) {
            String partitionFile1 = filePrefix1 + "_" + i + ".txt";
            String partitionFile2 = filePrefix2 + "_" + i + ".txt";

            // 找出当前分区的交集
            Set<Integer> partitionIntersection = findIntersectionInPartition(partitionFile1, partitionFile2);
            totalIntersection.addAll(partitionIntersection);
        }

        return totalIntersection;
    }

    public static void main(String[] args) throws IOException {
        String inputFile1 = "large_file_1.txt"; // 假设大文件1的路径
        String inputFile2 = "large_file_2.txt"; // 假设大文件2的路径

        // 1. 对两个大文件进行哈希切割
        partitionFile(inputFile1, "partition_file_1");
        partitionFile(inputFile2, "partition_file_2");

        // 2. 找出两个文件的交集
        Set<Integer> totalIntersection = findTotalIntersection("partition_file_1", "partition_file_2");

        // 3. 输出交集
        System.out.println("交集中的整数：");
        for (int num : totalIntersection) {
            System.out.println(num);
        }
    }
}

代码解释

  1. 哈希切割（partitionFile方法）：

    • 将大文件划分为多个较小的分区文件。
    • 根据整数的哈希值，将其分配到不同的分区文件中，确保相同的整数会被分配到相同的分区。

  2. 查找分区交集（findIntersectionInPartition方法）：

    • 对每个分区文件，使用HashSet存储第一个文件的整数。
    • 再次遍历第二个文件的相应分区，找到两个分区文件的交集。

  3. 合并所有分区的交集（findTotalIntersection方法）：

    • 遍历所有分区的交集，合并结果得到全局交集。
解法二：位图

思路：
1、遍历第一个文件，将第一个文件的每个数据读取出来，存放到bitSet当中
2、遍历第二个文件，每次读第一个数据，就看bitSet中，之前是否存在
3、如果存在，就是交集

2.3 交集、并集和差集

参考2.2中的解法2，其实我们可以发现，如果把两个文件中的数据都读取出来，存放到位图中，那两个位图去做按位与操作，就可以获取到交集

按位与操作，只有都是1才是1，那么这个时候对应位上是1，说明两个文件中都有该数据

在这里插入图片描述
相同的思路，如果我们对两个位图进行其他操作，可以得到其他集合；
比如两个位图按位或操作，就可以得到并集；两个集合按位异或操作，就可以得到差集

按位或，即两个位图的同一位置上，有一个1则整体都是1，那最后按位或后的位图，一个位置上有1，则说明对应数据在两个文件中至少有一个数据存在，该位图即为并集；

按位异或，即两个位图进行无进位加法操作，0的还是0，都是1的也变0，只有其中一个是1的还保留1，那最后得到的这个位图中的每一个1，都代表两个中只有其中一个有，即为差集

在这里插入图片描述

2.4 不超过2次的所有整数

题目：
位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数

解法1：哈希切割
同2.1哈希切割，把数据用哈希，分成多个小文件，然后分组统计最后汇总

解法2：使用两个位图
用两个位图的同一个位置，去维护四个状态，模拟一个2-bit位图；

  • 00：表示该整数从未出现。
  • 01：表示该整数出现一次。
  • 10：表示该整数出现两次。
  • 11：表示该整数出现三次及以上。

先第一遍遍历，把数据的出现次数状态，存到两个位图中。
然后二次遍历，排除11状态的，其他的全部计数

解法二代码示例：

import java.io.*;
import java.util.BitSet;

public class FindIntegersWithMax2Occurrences {

    private static final int MAX_RANGE = Integer.MAX_VALUE; // 假设整数范围是0到2^31-1
    private BitSet bitSet1; // 第一个BitSet
    private BitSet bitSet2; // 第二个BitSet

    public FindIntegersWithMax2Occurrences(int maxRange) {
        // 初始化两个BitSet
        bitSet1 = new BitSet(maxRange);
        bitSet2 = new BitSet(maxRange);
    }

    /**
     * 更新整数的2-bit位图状态
     * @param num 整数
     */
    private void updateBitSets(int num) {
        boolean bit1 = bitSet1.get(num);
        boolean bit2 = bitSet2.get(num);

        if (!bit1 && !bit2) {
            // 当前状态是00，更新为01
            bitSet1.set(num);
        } else if (bit1 && !bit2) {
            // 当前状态是01，更新为10
            bitSet1.clear(num);
            bitSet2.set(num);
        } else if (!bit1 && bit2) {
            // 当前状态是10，更新为11
            bitSet1.set(num);
        }
        // 如果是11，则保持不变
    }

    /**
     * 第一次遍历文件，更新2-bit位图的状态
     * @param inputFile 输入文件
     */
    public void firstPass(String inputFile) throws IOException {
        BufferedReader reader = new BufferedReader(new FileReader(inputFile));
        String line;
        while ((line = reader.readLine()) != null) {
            int num = Integer.parseInt(line.trim());
            updateBitSets(num);
        }
        reader.close();
    }

    /**
     * 第二次遍历文件，找出出现次数不超过2次的整数
     * @param inputFile 输入文件
     */
    public void secondPass(String inputFile) throws IOException {
        BufferedReader reader = new BufferedReader(new FileReader(inputFile));
        String line;

        System.out.println("出现次数不超过2次的整数：");
        while ((line = reader.readLine()) != null) {
            int num = Integer.parseInt(line.trim());
            boolean bit1 = bitSet1.get(num);
            boolean bit2 = bitSet2.get(num);

            // 如果状态是00、01或10，输出该整数
            if (!(bit1 && bit2)) {
                System.out.println(num);
            }
        }
        reader.close();
    }

    public static void main(String[] args) throws IOException {
        String inputFile = "large_numbers_file.txt"; // 假设大文件名为large_numbers_file.txt

        FindIntegersWithMax2Occurrences finder = new FindIntegersWithMax2Occurrences(MAX_RANGE);

        // 1. 第一次遍历文件，更新2-bit位图状态
        finder.firstPass(inputFile);

        // 2. 第二次遍历文件，找出出现次数不超过2次的整数
        finder.secondPass(inputFile);
    }
}

3. 布隆过滤器

精确算法和近似算法

题目：
给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法

精确算法：
使用哈希切割，分别把两个文件，用相同的哈希方式，切割成同样份数的小文件，再用一一对应的小文件取交集，最后把所有交集汇总起来即可。

近似算法：
1、把第一个文件当中的query映射到布隆过滤器中
2、读取第二个文件，每个query都去布隆过滤器中查找
3、因为可能存在误判，所以这个数据有可能没有，但是被误判为了有。

4. 爬虫URL去重

题目：
多线程并发爬虫时，对url做去重，让你设计整个数据结构和核心方法，思考查询时间复杂度、空间复杂度等因素

可以使用 布隆过滤器（Bloom Filter） 结合 HashSet 来设计多线程并发爬虫中的 URL 去重方案。这种方案在保证较快的查询速度的同时，也能有效控制内存消耗。

1. 设计思路

  • 布隆过滤器：用来判断某个 URL 是否可能已经存在，可以节省空间，但有一定的误判率。
  • HashSet：在布隆过滤器判断为可能存在时进行二次确认，以确保去重的准确性。

2. 数据结构

  • 布隆过滤器（BloomFilter）：一个基于哈希的位数组，能够高效地判断元素是否存在，空间复杂度低。
    • add(url): 将 URL 添加到布隆过滤器中。
    • mightContain(url): 检查 URL 是否可能存在。
  • HashSet：存储经过布隆过滤器验证的 URL，用于消除误判。
    • contains(url): 检查 URL 是否已存在。
    • add(url): 将 URL 添加到集合中。

3. 核心方法

以下是Java中实现的核心代码：

import java.util.BitSet;
import java.util.HashSet;
import java.util.concurrent.locks.ReentrantLock;

public class UrlDeduplication {
    // 布隆过滤器位数组
    private final BitSet bloomFilter;
    // 位数组的大小
    private final int size;
    // HashSet用于消除误判
    private final HashSet<String> urlSet;
    // ReentrantLock实现线程安全
    private final ReentrantLock lock;

    // 哈希函数数量
    private static final int HASH_COUNT = 3;

    // 初始化布隆过滤器和HashSet
    public UrlDeduplication(int size) {
        this.size = size;
        this.bloomFilter = new BitSet(size);
        this.urlSet = new HashSet<>();
        this.lock = new ReentrantLock();
    }

    // 计算哈希值
    private int[] hash(String url) {
        int[] hashValues = new int[HASH_COUNT];
        for (int i = 0; i < HASH_COUNT; i++) {
            hashValues[i] = Math.abs(url.hashCode() + i) % size;
        }
        return hashValues;
    }

    // 添加URL到布隆过滤器和HashSet
    public void addUrl(String url) {
        int[] hashValues = hash(url);
        lock.lock(); // 加锁保证线程安全
        try {
            // 更新布隆过滤器
            for (int hash : hashValues) {
                bloomFilter.set(hash);
            }
            // 更新HashSet
            urlSet.add(url);
        } finally {
            lock.unlock(); // 解锁
        }
    }

    // 判断URL是否存在
    public boolean containsUrl(String url) {
        int[] hashValues = hash(url);
        lock.lock(); // 加锁保证线程安全
        try {
            // 检查布隆过滤器
            for (int hash : hashValues) {
                if (!bloomFilter.get(hash)) {
                    return false; // 肯定不存在
                }
            }
            // 可能存在，再次确认
            return urlSet.contains(url);
        } finally {
            lock.unlock(); // 解锁
        }
    }
}

4. 时间和空间复杂度分析

  • 时间复杂度
    • addUrl(url)：
      • 布隆过滤器：O(k)，其中 k 为哈希函数的数量。
      • HashSet：O(1)。
      • 总体：O(k) + O(1) ≈ O(1)。
    • containsUrl(url)：
      • 布隆过滤器：O(k)。
      • HashSet：O(1)。
      • 总体：O(k) + O(1) ≈ O(1)。
  • 空间复杂度
    • 布隆过滤器：O(n)，其中 n 为位数组的大小。
    • HashSet：O(m)，其中 m 为实际存储的 URL 数量。
    • 总体：O(n + m)。

5. 优点和局限性

  • 优点
    • 具有较高的空间效率，能够有效去重。
    • 支持多线程并发访问。
  • 局限性
    • 布隆过滤器可能产生误判，需要使用 HashSet 进行二次确认。
    • 随着数据量增加，HashSet 的内存占用会变大。

这种方案在多线程并发环境中较为高效，可以在爬虫系统中实现较好的性能与去重效果。

⭐️最后的话⭐️
总结不易，希望uu们不要吝啬你们的👍哟(＾Ｕ＾)ノ~ＹＯ！！如有问题，欢迎评论区批评指正😁

请添加图片描述


http://www.kler.cn/a/369045.html

相关文章：

  • dmsql日志分析工具部署与使用DM8/DM7
  • 504 Gateway Time-outopenresty
  • 量子计算突破：下一个科技革命的风口浪尖在哪里？
  • 活着就好20241028
  • hcia复习篇
  • 嵌入式Linux的AXI平台（platform）驱动教程
  • springmvc-springsecurity-redhat keycloak SAML2 xml实现
  • 【C++】继承与模板
  • WASM 使用说明23事(RUST实现)
  • 【TIMM库】是一个专门为PyTorch用户设计的图像模型库 python库
  • 15分钟学 Go 第 23 天：并发基础：Goroutines
  • 【CSS3】css开篇基础（4）
  • JavaScript 函数与事件处理
  • 灵动AI：艺术与科技的融合
  • 网络搜索引擎Shodan（4）
  • 最优化方法-无约束优化算法（最速下降法）matlab实现
  • opencv学习笔记(3)：图像和视频的读取(C++)
  • 【AIGC】ChatGPT提示词Prompt精确控制指南：Scott Guthrie的建议详解与普通用户实践解析
  • 26.Redis主从架构
  • Hadoop-001-本地虚拟机环境搭建
  • oracle 行转列(PIVOT 多个行数据按照指定的列进行汇总) 列转行(UNPIVOT)
  • RHCE笔记-NFS服务
  • 第十七周：机器学习
  • 2025年软考高级哪个最简单？
  • 重构商业生态：DApp创新玩法与盈利模式的深度剖析
  • c语言中整数在内存中的存储