如何实现带容差的浮点数集合并支持O(1)复杂度查找？

分桶哈希（Bucket Hashing）：最实用的O(1)方案 #

这是满足需求最直接高效的思路，核心是用哈希表将浮点数按公差tol分桶，通过限制需检查的桶数量实现平均O(1)的查找效率。

原理 #

把整个浮点数空间按tol的大小划分为连续区间（桶），每个区间对应哈希表的一个键。插入浮点数f时，计算其所属桶并加入该桶的元素列表；查找x时，仅需检查x所在桶以及相邻两个桶（因为x与相邻桶内的数也可能满足abs(x-f) < tol），无需遍历所有元素。

实现步骤 #

1. 桶索引计算：用math.floor(f / tol)作为桶的索引，确保每个桶覆盖区间为[k*tol, (k+1)*tol)（k为整数），负数也能正确划分。
2. 插入操作：计算f的桶索引，将f加入对应桶的元素列表（可选：插入前先检查是否已有接近的数，避免重复存储）。
3. 查找操作：计算x的桶索引，遍历当前桶、前一个桶、后一个桶内的所有元素，判断是否存在满足abs(x-f) < tol的数。

代码示例（Python） #

import math

class ApproxFloatSet:
    def __init__(self, tol):
        self.tol = tol
        self.buckets = {}
    
    def add(self, f):
        bucket_idx = math.floor(f / self.tol)
        # 可选：若需避免存储重复的近似值，先检查再插入
        # if self.__contains__(f):
        #     return
        self.buckets.setdefault(bucket_idx, []).append(f)
    
    def __contains__(self, x):
        bucket_idx = math.floor(x / self.tol)
        # 仅检查当前桶和相邻两个桶，保证平均O(1)效率
        for idx in (bucket_idx - 1, bucket_idx, bucket_idx + 1):
            if idx in self.buckets:
                for f in self.buckets[idx]:
                    if abs(x - f) < self.tol:
                        return True
        return False

优缺点 #

• 优点：平均情况下插入和查找都是O(1)，实现简单，对大多数场景足够高效。
• 缺点：最坏情况（所有数都落在同一个桶）下是O(N)，但只要tol设置合理，实际中几乎不会出现；需注意浮点数精度误差，可通过给tol添加极小epsilon缓解。

量化存储（Quantization）：简化版近似查找 #

如果可以接受对浮点数进行量化处理，也可以将每个数映射为tol的整数倍，再用普通哈希集合存储量化后的值。查找时，量化目标x并检查自身及相邻的两个量化值是否存在于集合中。

注意事项 #

这种方法本质是分桶哈希的简化，但要注意量化方式的选择：若用round(f / tol) * tol，可能出现漏判；更稳妥的方式是结合相邻量化值的检查，逻辑和分桶哈希一致。

总结 #

分桶哈希是最推荐的方案，既保证了平均O(1)的时间复杂度，又能准确满足“近似相等”的查找需求，实现成本低且鲁棒性强。

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