如何为整数环形缓冲区设计高效哈希方法？

你当前的实现中，get_shifted方法通过循环逐个移动元素，时间复杂度为O(n²)，这是导致整体速度慢的核心瓶颈之一。先优化基础操作，再结合哈希方案可大幅提升性能。以下是针对你的需求的高效哈希方案：

一、基于归一化表示的哈希（直观易实现） #

核心思路是为每个环形缓冲区生成唯一的归一化标识：取原数组和反转数组的所有循环移位中字典序最小的结果，以此作为哈希的基础。相同的环形缓冲区会生成相同的归一化标识，哈希值也一致。

优化关键：用最小表示法替代全移位枚举 #

最小表示法可在O(n)时间内找到数组的最小循环移位，无需生成所有移位组合：

def min_rotation(self) -> tuple:
    arr = self.ids
    n = len(arr)
    if n == 0:
        return ()
    i, j, k = 0, 1, 0
    while i < n and j < n and k < n:
        a = arr[(i + k) % n]
        b = arr[(j + k) % n]
        if a == b:
            k += 1
        else:
            i += k + 1 if a > b else 0
            j += k + 1 if a < b else 0
            i = i + 1 if i == j else i
            k = 0
    start = min(i, j)
    return arr[start:] + arr[:start]

归一化与哈希实现 #

def get_normalized_key(self) -> tuple:
    # 原数组的最小循环移位
    original_min = self.min_rotation()
    # 反转数组的最小循环移位
    reversed_min = self.get_reversed().min_rotation()
    # 取字典序更小的作为唯一标识
    return original_min if original_min < reversed_min else reversed_min

def __eq__(self, other: 'Ring') -> bool:
    if len(self.ids) != len(other.ids):
        return False
    return self.get_normalized_key() == other.get_normalized_key()

def __hash__(self) -> int:
    return hash(self.get_normalized_key())

二、滚动哈希（Rabin-Karp变体，避免生成完整归一化数组） #

如果不想生成完整的归一化数组，可通过滚动哈希快速计算所有循环移位的哈希值，取原数组和反转数组的所有移位哈希中的最小值作为最终哈希，减少内存占用。

实现示例（多项式哈希） #

def _polynomial_hash(self, arr: tuple, base: int = 911382629, mod: int = 10**18 + 3) -> int:
    hash_val = 0
    for num in arr:
        hash_val = (hash_val * base + num) % mod
    return hash_val

def _get_all_cyclic_hashes(self) -> list:
    arr = self.ids
    n = len(arr)
    base = 911382629
    mod = 10**18 + 3
    prefix_hash = [0] * (n + 1)
    power = [1] * (n + 1)
    
    for i in range(n):
        prefix_hash[i+1] = (prefix_hash[i] * base + arr[i]) % mod
        power[i+1] = (power[i] * base) % mod
    
    cyclic_hashes = []
    for i in range(n):
        # 计算移位i后的哈希值
        hash_val = (prefix_hash[n] * power[i] + prefix_hash[i]) % mod
        cyclic_hashes.append(hash_val)
    return cyclic_hashes

def get_hash(self) -> int:
    original_hashes = self._get_all_cyclic_hashes()
    reversed_hashes = self.get_reversed()._get_all_cyclic_hashes()
    return min(min(original_hashes), min(reversed_hashes))

def __hash__(self) -> int:
    return self.get_hash()

# 滚动哈希存在碰撞风险，需保留归一化判断作为兜底
def __eq__(self, other: 'Ring') -> bool:
    if len(self.ids) != len(other.ids):
        return False
    return self.get_hash() == other.get_hash() and self.get_normalized_key() == other.get_normalized_key()

完整优化后的Ring类 #

替换原有低效实现，加入__hash__后，set的查找操作会从O(m*n)（m为集合大小）降至O(1)，性能大幅提升：

import random
from time import perf_counter
from typing import List, Tuple

class Ring:
    def __init__(self, ids: List[int]) -> None:
        # 用元组存储保证不可变性
        self.ids = tuple(ids)

    def get_reversed(self) -> 'Ring':
        return Ring(self.ids[::-1])

    def min_rotation(self) -> tuple:
        arr = self.ids
        n = len(arr)
        if n == 0:
            return ()
        i, j, k = 0, 1, 0
        while i < n and j < n and k < n:
            a = arr[(i + k) % n]
            b = arr[(j + k) % n]
            if a == b:
                k += 1
            else:
                i += k + 1 if a > b else 0
                j += k + 1 if a < b else 0
                i = i + 1 if i == j else i
                k = 0
        start = min(i, j)
        return arr[start:] + arr[:start]

    def get_normalized_key(self) -> tuple:
        original_min = self.min_rotation()
        reversed_min = self.get_reversed().min_rotation()
        return original_min if original_min < reversed_min else reversed_min

    def __eq__(self, other: 'Ring') -> bool:
        if len(self.ids) != len(other.ids):
            return False
        return self.get_normalized_key() == other.get_normalized_key()

    def __hash__(self) -> int:
        return hash(self.get_normalized_key())

    @staticmethod
    def Random(ring_capacity: int) -> 'Ring':
        unduplicated = set()
        while len(unduplicated) < ring_capacity:
            unduplicated.add(random.randint(0, 20))
        return Ring(list(unduplicated))


if __name__ == '__main__':
    random.seed(1)
    ring_capacity = 5
    num_rings = 2000

    ring_set = set()
    random_rings = [Ring.Random(ring_capacity) for _ in range(num_rings)]

    start = perf_counter()
    for ring in random_rings:
        ring_set.add(ring)
    end = perf_counter()

    print(end - start)
    print(f'{len(ring_set)} out of {num_rings} unduplicated rings')

性能对比说明 #

• 原代码get_shifted为O(n²)，优化后min_rotation为O(n)
• 原代码用list的in操作，时间复杂度O(m*n)；优化后用set哈希查找，时间复杂度O(m)
• 针对2000个元素的测试，优化后的代码运行速度会比原代码快数倍至数十倍

内容的提问来源于stack exchange，提问作者landings