more-math-lib

more-math-lib is an extension of the Python math library, which includes: gcdext, isqrt_rem, ceil_div, ilog, fibonacci, and the tr function.

Among them, there is a class called HashTable, which is a chaining hash table with dynamic resizing and uniform key distribution.

The most common application areas for the HashTable class include:

• Databases
• Caching systems
• Compilers/Interpreters
• Network protocols
• Competitive programming
• Cryptography
• Game development
• Web crawlers

Functions

gcdext

Returns (g, x, y) such that ax + by = g = gcd(a, b)

isqrt_rem

Returns (s, r) such that n = s² + r, and 0 ≤ r < 2s+1

ceil_div

Returns ⌈a/b⌉ (ceiling division)

ilog

Returns the largest integer e such that base^e ≤ n

fibonacci

Returns the n-th Fibonacci number (F₀=0, F₁=1)

tr

Returns the n-th hexagonal number plus floor(sqrt(n)): n*(2*n-1) + isqrt(n).

Classes

HashTable

Description

A chaining hash table with dynamic resizing and uniform key distribution.

This implementation uses separate chaining for collision resolution and 
automatically doubles its capacity when the load factor exceeds 0.7.

The hash function incorporates MurmurHash-style mixing and a specialized
integer mixer `tr()` to achieve good distribution even for sequential keys.

Time Complexity:
    - Insert/Update: O(1) average, O(n) worst-case
    - Lookup: O(1) average, O(n) worst-case
    - Delete: O(1) average, O(n) worst-case
    - Resize: O(n) amortized

Space Complexity: O(n) where n is the number of stored items.

Supports dict-like syntax:
```python
ht = HashTable()
ht['key'] = 'value'      # __setitem__
value = ht['key']        # __getitem__
del ht['key']            # __delitem__
'key' in ht              # __contains__
```

Examples:
```python
>>> ht = HashTable()
>>> ht.insert("apple", 1)
>>> ht.get("apple")
1
>>> ht["banana"] = 2
>>> print(ht["banana"])
2
>>> "banana" in ht
True
>>> del ht["banana"]
```

Basic Methods

insert

Inserts or updates a key-value pair.

get

Retrieves the value associated with a given key.

delete

Removes a key-value pair from the table.

more-math-lib

more-math-lib 是一个 Python 数学库的扩展，里面包含：gcdext、isqrt_rem、ceil_div、ilog、fibonacci、tr函数

其中，有一个叫 HashTable 的类，是一个使用链地址法、支持动态扩容且键分布均匀的哈希表。

对于 HashTable 这个类，它最常用的领域包含：

• 数据库
• 缓存系统
• 编译器/解释器
• 网络协议
• 算法竞赛
• 密码学
• 游戏开发
• 爬虫系统

函数

gcdext

返回 (g, x, y) 使得 ax + by = g = gcd(a, b)

isqrt_rem

返回 (s, r) 使得 n = s² + r, 且 0 ≤ r < 2s+1

ceil_div

返回 ⌈a/b⌉（向上取整）

ilog

返回最大整数 e 使得 base^e ≤ n

fibonacci

返回第 n 个斐波那契数（F₀=0, F₁=1）

tr

返回第 n 个六边形数加上 floor(sqrt(n)): n*(2*n-1) isqrt(n)。

类

HashTable

介绍

一个使用链地址法、支持动态扩容且键分布均匀的哈希表。

本实现采用分离链地址法解决哈希冲突，并在负载因子超过 0.7 时自动将容量扩展为原来的两倍。

哈希函数结合了 MurmurHash 风格的混合算法和专门的整数混合器 `tr()`，即使在键值连续的情况下也能实现良好的分布。

时间复杂度：
- 插入/更新：平均 O(1)，最坏情况 O(n)
- 查找：平均 O(1)，最坏情况 O(n)
- 删除：平均 O(1)，最坏情况 O(n)
- 扩容：均摊 O(n)

空间复杂度： O(n)，其中 n 为存储的元素数量。

支持类似字典的语法：
```python
ht = HashTable()
ht['key'] = 'value'      # __setitem__
value = ht['key']        # __getitem__
del ht['key']            # __delitem__
'key' in ht              # __contains__
```

示例：
```python
>>> ht = HashTable()
>>> ht.insert("apple", 1)
>>> ht.get("apple")
1
>>> ht["banana"] = 2
>>> print(ht["banana"])
2
>>> "banana" in ht
True
>>> del ht["banana"]
```

基础功能

insert

插入或更新一个键值对。

get

获取与某个键关联的值。

delete

从表中删除一个键值对。