Cython实现HashMap遇OverflowError：整数过大无法转换问题求助

我正在练习用Cython实现HashMap，后续计划基于它做更多开发。以下是我的实现代码：

#cython language_level=3

from libc.stdlib cimport malloc, free
from cpython.ref cimport PyObject, Py_INCREF, Py_CLEAR, Py_DECREF, Py_TYPE, PyTypeObject, Py_XDECREF, Py_XDECREF, Py_XINCREF

cdef struct Entry:
    long long key
    PyObject* value

cdef class HashMap:
    cdef Entry** table
    cdef long long size
    cdef long long capacity

    def __cinit__(self, long long capacity=16):
        cdef Entry** entry
        self.capacity = capacity
        self.size = 0
        self.table = <Entry**>malloc(capacity * sizeof(Entry))
        entry = self.table
        for i in range(self.capacity):
            entry[i] = <Entry*>malloc(sizeof(Entry))

    def __dealloc__(self):
        cdef Entry** entry
        for i in range(self.capacity):
            entry = <Entry**>self.table
            if entry != NULL:
                free(entry)
        free(self.table)

    cdef long long hash(self, long long x):
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb
        x = x ^ (x >> 31)
        return x

    cpdef put(self, long long key, object value):
        cdef Entry** entry
        key = self.hash(key)
        if len(self) == 0:
            self.table[0].key = key
            self.table[0].value = <PyObject*>value
            self.size += 1
            return        
        entry = <Entry**>self.table
        for i in range(self.capacity):
            if entry == NULL:
                entry[0].key = key
                entry[0].value = <PyObject*>value
                self.size += 1
                break

    cpdef get(self, long long key):
        cdef Entry** entry
        find_key = self.hash(key)
        entry = <Entry**>self.table
        for i in range(self.capacity):
            if entry[0].key == find_key:
                return <object>(entry[0].value)
        raise KeyError(key)

    def __len__(self):
        return self.size

我构建代码后执行以下测试：

>>> from hashmap.hashmap import HashMap
>>> hm = HashMap()     
>>> hm.put(27, "hello")

此时触发了如下错误：

OverflowError: int too big to convert
Exception ignored in: 'hashmap.HashMap.hash'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
OverflowError: int too big to convert

最初我使用int类型，改为long long后仍出现该错误，请求帮助解决此问题。

错误原因分析 #

溢出错误来自hash函数中的乘法运算：你使用的哈希常量0xbf58476d1ce4e5b9和0x94d049bb133111eb都是64位无符号整数，当和long long类型的x相乘时，会产生超出64位有符号整数范围的结果，Cython默认会对这种溢出抛出错误。此外，代码还存在内存释放、哈希冲突处理等逻辑错误。

修复步骤 #

1. 禁用哈希函数的溢出检查
   哈希算法依赖整数溢出的特性，需要在hash函数上添加装饰器关闭溢出检查：

   import cython
   
   @cython.overflowcheck(False)
   cdef long long hash(self, long long x):
       x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9
       x = (x ^ (x >> 27)) * 0x94d049bb133111eb
       x = x ^ (x >> 31)
       return x
   

2. 修正内存释放逻辑
   当前代码错误地释放整个table指针，改为逐个释放entry：

   def __dealloc__(self):
       cdef Entry** entry = self.table
       if entry != NULL:
           for i in range(self.capacity):
               if entry[i] != NULL:
                   free(entry[i])
           free(entry)
   

3. 修正put函数的哈希冲突处理
   修复遍历逻辑，添加线性探测解决冲突，同时正确管理Python对象引用：

   cpdef put(self, long long key, object value):
       cdef long long hashed_key = self.hash(key)
       cdef long long idx = hashed_key % self.capacity
       cdef Entry* entry = self.table[idx]
       
       # 处理已存在的键
       while entry.key != 0 or entry.value != NULL:
           if entry.key == hashed_key:
               Py_XDECREF(entry.value)
               entry.value = <PyObject*>value
               Py_INCREF(value)
               return
           # 线性探测下一个位置
           idx = (idx + 1) % self.capacity
           entry = self.table[idx]
       
       # 插入新键值对
       entry.key = hashed_key
       entry.value = <PyObject*>value
       Py_INCREF(value)
       self.size += 1
       
       # 负载因子超过0.5时扩容
       if self.size * 2 >= self.capacity:
           self._resize()
   

4. 修正get函数的查找逻辑
   同步调整查找逻辑，匹配线性探测的冲突处理：

   cpdef get(self, long long key):
       cdef long long hashed_key = self.hash(key)
       cdef long long idx = hashed_key % self.capacity
       cdef Entry* entry = self.table[idx]
       
       while entry.key != 0 or entry.value != NULL:
           if entry.key == hashed_key:
               return <object>(entry.value)
           idx = (idx + 1) % self.capacity
           entry = self.table[idx]
       
       raise KeyError(key)
   

5. 添加扩容辅助函数
   避免哈希表负载过高导致性能下降：

   cdef void _resize(self):
       cdef long long old_capacity = self.capacity
       cdef Entry** old_table = self.table
       cdef long long new_capacity = old_capacity * 2
       cdef Entry** new_table = <Entry**>malloc(new_capacity * sizeof(Entry*))
       cdef long long i, idx
       cdef Entry* entry
       
       # 初始化新表
       for i in range(new_capacity):
           new_table[i] = <Entry*>malloc(sizeof(Entry))
           new_table[i].key = 0
           new_table[i].value = NULL
       
       self.capacity = new_capacity
       self.table = new_table
       self.size = 0
       
       # 迁移旧表数据
       for i in range(old_capacity):
           entry = old_table[i]
           if entry.key != 0 or entry.value != NULL:
               self.put(entry.key, <object>(entry.value))
               free(entry)
       
       free(old_table)
   

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