Python 算法高级篇：跳跃表和布隆过滤器的应用

小蓝枣

发布于 2023-10-28 09:55:04

2480

发布于 2023-10-28 09:55:04

文章被收录于专栏：CSDN博客专家-小蓝枣的博客

引言

在计算机科学中，数据结构和算法是构建强大应用的基础。本文将介绍两个非常有用的数据结构：跳跃表和布隆过滤器。这些数据结构可以在各种应用中提供高效的数据存储和检索解决方案。

😃😄 ❤️ ❤️ ❤️

1. 跳跃表（ Skip List ）

跳跃表是一种随机化数据结构，类似于有序链表。跳跃表以有序方式存储元素，并使用多层级别的链表来实现快速查找。这使得在跳跃表中查找元素的时间复杂度为 O ( log n )，与二叉搜索树类似，但它更容易实现。

1.1 跳跃表的基本结构

跳跃表包括多个层级，每个层级都是一个有序链表。最底层的链表包含所有元素，而更高级别的链表则包含较少的元素，以便更快地定位到目标元素。

一个简单的跳跃表可以如下所示：

Level 3: 1 → 3 → 5 → 9
Level 2: 1 → 5
Level 1: 1 → 9
Level 0: 1 → 5 → 9

1.2 跳跃表的操作

跳跃表支持以下操作：

插入：在 O ( log n )时间内插入元素。
删除：在 O ( log n )时间内删除元素。
查找：在 O ( log n )时间内查找元素。

1.3 Python 中的跳跃表实现

以下是一个简单的 Python 实现跳跃表的示例：

import random

class Node:
    def __init__(self, key, level=0):
        """
        跳跃表节点的构造函数。
        
        Args:
        - key: 节点的键值。
        - level: 节点的层级（用于索引层次结构）。
        """
        self.key = key
        self.forward = [None] * (level + 1)

class SkipList:
    def __init__(self, max_level):
        """
        初始化跳跃表。
        
        Args:
        - max_level: 跳跃表的最大层级。
        """
        self.max_level = max_level
        self.header = self.create_node(max_level, None)
        self.level = 0
    
    def create_node(self, level, key):
        """
        创建一个新的节点。
        
        Args:
        - level: 节点的层级。
        - key: 节点的键值。
        
        Returns:
        - 新创建的节点。
        """
        return Node(key, level)

    def random_level(self):
        """
        随机生成节点的层级，用于插入新节点。
        
        Returns:
        - 随机生成的层级。
        """
        level = 0
        while random.random() < 0.5 and level < self.max_level:
            level += 1
        return level

    def insert(self, key):
        """
        在跳跃表中插入一个节点。
        
        Args:
        - key: 要插入的节点的键值。
        """
        update = [None] * (self.max_level + 1)
        current = self.header

        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].key < key:
                current = current.forward[i]
            update[i] = current

        current = current.forward[0]

        if current is None or current.key != key:
            new_level = self.random_level()
            
            if new_level > self.level:
                for i in range(self.level + 1, new_level + 1):
                    update[i] = self.header
                self.level = new_level

            new_node = self.create_node(new_level, key)

            for i in range(new_level + 1):
                new_node.forward[i] = update[i].forward[i]
                update[i].forward[i] = new_node

    def search(self, key):
        """
        在跳跃表中查找一个节点。
        
        Args:
        - key: 要查找的节点的键值。
        
        Returns:
        - 如果找到，返回节点的键值；否则，返回 None。
        """
        current = self.header

        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].key < key:
                current = current.forward[i]

        current = current.forward[0]

        if current and current.key == key:
            return current.key
        else:
            return None

    def delete(self, key):
        """
        从跳跃表中删除一个节点。
        
        Args:
        - key: 要删除的节点的键值。
        """
        update = [None] * (self.max_level + 1)
        current = self.header

        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].key < key:
                current = current.forward[i]
            update[i] = current

        current = current.forward[0]

        if current and current.key == key:
            for i in range(self.level + 1):
                if update[i].forward[i] != current:
                    break
                update[i].forward[i] = current.forward[i]

            while self.level > 0 and self.header.forward[self.level] is None:
                self.level -= 1

# 创建一个最大层级为 4 的跳跃表
skip_list = SkipList(4)

# 插入一些节点
skip_list.insert(1)
skip_list.insert(2)
skip_list.insert(3)
skip_list.insert(5)

# 查找节点
print(skip_list.search(3))  # Output: 3
print(skip_list.search(4))  # Output: None

# 删除节点
skip_list.delete(3)
print(skip_list.search(3))  # Output: None

这个示例展示了如何在 Python 中实现一个基本的跳跃表。跳跃表的每个节点包括一个键值对，以及指向下一个和下面一层节点的指针。

2. 布隆过滤器（ Bloom Filter ）

布隆过滤器是一种空间高效的概率数据结构，用于快速检查一个元素是否属于一个大型集合。布隆过滤器不存储实际元素，而是使用位数组和多个哈希函数来表示元素的存在与否。它通常用于减少磁盘或内存访问的次数，以提高性能。

2.1 布隆过滤器的基本结构

布隆过滤器包括以下基本组成部分：

一个位数组：通常很大，包含大量位。
多个哈希函数：用于将元素映射到位数组中的多个位置。

2.2 布隆过滤器的操作

布隆过滤器支持以下操作：

插入：将元素映射到位数组中的多个位置，并将相应的位设置为 1 。
查询：检查元素是否可能存在，即检查所有相关位是否都为 1 。如果有任何一个位为 0 ，元素肯定不存在。
删除：由于布隆过滤器的设计目的是快速检查元素是否存在，通常不支持删除操作。

2.3 Python 中的布隆过滤器实现

以下是一个简单的 Python 示例，展示了如何使用布隆过滤器：

import mmh3
from bitarray import bitarray

class BloomFilter:
    def __init__(self, size, hash_count):
        """
        初始化布隆过滤器。
        
        Args:
        - size: 位数组的大小，决定了布隆过滤器的容量。
        - hash_count: 哈希函数的数量，影响性能和误判率。
        """
        self.size = size
        self.hash_count = hash_count
        self.bit_array = bitarray(size)
        self.bit_array.setall(0)

    def add(self, item):
        """
        向布隆过滤器中添加元素。
        
        Args:
        - item: 要添加的元素。
        """
        for seed in range(self.hash_count):
            # 使用哈希函数计算索引并将相应的位设置为1。
            index = mmh3.hash(item, seed) % self.size
            self.bit_array[index] = 1

    def lookup(self, item):
        """
        查询元素是否存在于布隆过滤器中。
        
        Args:
        - item: 要查询的元素。
        
        Returns:
        - True，如果元素可能存在（存在误判的可能性）；False，如果元素肯定不存在。
        """
        for seed in range(self.hash_count):
            index = mmh3.hash(item, seed) % self.size
            if self.bit_array[index] == 0:
                return False
        return True

# 创建一个布隆过滤器
bf = BloomFilter(100, 5)

# 向布隆过滤器中添加元素
bf.add("example")

# 查询元素是否存在于布隆过滤器中
print(bf.lookup("example"))  # Output: True
print(bf.lookup("nonexistent"))  # Output: False

这个示例使用了 MurmurHash3 哈希函数和 bitarray 库来实现一个简单的布隆过滤器。