哈希表与字典实现

// 1. 用户会话管理
sessionStore["session_abc123"] = User{ID: 1000, Name: "张三"}

// 2. 数据库查询缓存
queryCache["SELECT * FROM users WHERE id=1000"] = cachedResult

// 3. 配置中心
configMap["db.host"] = "192.168.1.100"
configMap["db.port"] = "3306"

// 4. Redis 核心数据结构
// SET key value → 底层就是哈希表
// GET key       → O(1) 查找

type DirectArray struct {
    data [1000000]string  // 假设键的范围是 0-999999
}

func (da *DirectArray) Get(key int) string {
    return da.data[key]  // O(1) 直接访问
}

func (da *DirectArray) Set(key int, value string) {
    da.data[key] = value  // O(1) 直接设置
}

type SortedArray struct {
    keys   []string
    values []interface{}
}

func (sa *SortedArray) Get(key string) (interface{}, bool) {
    // 二分查找
    left, right := 0, len(sa.keys)-1
    for left <= right {
        mid := left + (right-left)/2
        if sa.keys[mid] == key {
            return sa.values[mid], true
        } else if sa.keys[mid] < key {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return nil, false
}

func (sa *SortedArray) Set(key string, value interface{}) {
    // 二分查找位置
    pos := sa.findInsertPosition(key)

    // 插入需要移动元素 → O(n)
    sa.keys = append(sa.keys[:pos], append([]string{key}, sa.keys[pos:]...)...)
    sa.values = append(sa.values[:pos], append([]interface{}{value}, sa.values[pos:]...)...)
}

type HashTable struct {
    buckets []interface{}
    size    int
}

func (ht *HashTable) hash(key string) int {
    h := 0
    for _, c := range key {
        h = h*31 + int(c)
    }
    return h % ht.size
}

func (ht *HashTable) Get(key string) (interface{}, bool) {
    index := ht.hash(key)
    return ht.buckets[index], true  // 简化版，忽略冲突
}

type ChainNode struct {
    key   string
    value interface{}
    next  *ChainNode
}

type ChainHashTable struct {
    buckets []*ChainNode
    size    int
    count   int
}

func (ht *ChainHashTable) Set(key string, value interface{}) {
    index := ht.hash(key)

    // 检查链表中是否已存在
    current := ht.buckets[index]
    for current != nil {
        if current.key == key {
            current.value = value  // 更新
            return
        }
        current = current.next
    }

    // 头插法插入新节点
    newNode := &ChainNode{key: key, value: value}
    newNode.next = ht.buckets[index]
    ht.buckets[index] = newNode
    ht.count++
}

func (ht *ChainHashTable) Get(key string) (interface{}, bool) {
    index := ht.hash(key)

    // 遍历链表查找
    current := ht.buckets[index]
    for current != nil {
        if current.key == key {
            return current.value, true
        }
        current = current.next
    }

    return nil, false
}

// 删除问题示例
哈希表: [A] [B] [C] [D]
         5   6   7   8

删除 B 后不能直接清空:
错误: [A] [ ] [C] [D]  → 查找 C 时会在 6 停止!
正确: [A] [DELETED] [C] [D]  → 查找 C 时会继续探测

// 1. 正常情况：负载因子 ≥ 1
if dict.used >= dict.size {
    expand()  // 立即扩容
}

// 2. BGSAVE/BGREWRITEAOF 期间：负载因子 ≥ 5
// 原因：fork子进程时,写时复制(COW)机制会复制内存
// 推迟扩容可以减少内存拷贝
if server.isSavingOrRewriting() {
    if dict.used >= dict.size * 5 {
        expand()  // 负载过高才扩容
    }
}

// 寻找大于等于 size 的最小 2^n
func nextPower(size int) int {
    n := 4  // 最小容量
    for n < size {
        n *= 2
    }
    return n
}

// 示例：
// 当前大小 8 → 扩容到 16
// 当前大小 100 → 扩容到 128

type Dict struct {
    ht        [2]*HashTable  // 两个哈希表
    rehashidx int64          // rehash进度 (-1表示未进行)
}

// rehashidx 的含义：
// -1: 未在 rehash
// 0~size: 正在 rehash,表示已迁移到 ht[0] 的索引位置

func (d *Dict) Get(key string) (interface{}, bool) {
    // 1. 先在 ht[0] 查找
    if val, ok := d.ht[0].Get(key); ok {
        return val, true
    }

    // 2. 如果正在 rehash,再在 ht[1] 查找
    if d.isRehashing() {
        if val, ok := d.ht[1].Get(key); ok {
            return val, true
        }
    }

    return nil, false
}

func (d *Dict) Set(key string, value interface{}) {
    // 渐进式迁移1步
    if d.isRehashing() {
        d.rehashStep()
    }

    // 新键总是插入 ht[1] (如果正在rehash)
    table := d.ht[0]
    if d.isRehashing() {
        table = d.ht[1]
    }

    table.Set(key, value)
}

func (d *Dict) Delete(key string) bool {
    // 渐进式迁移1步
    if d.isRehashing() {
        d.rehashStep()
    }

    // 先尝试从 ht[0] 删除
    if d.ht[0].Delete(key) {
        return true
    }

    // 如果正在rehash,再尝试从 ht[1] 删除
    if d.isRehashing() {
        return d.ht[1].Delete(key)
    }

    return false
}

func (d *Dict) rehashStep() {
    // 每次只迁移 N 个桶 (Redis默认N=1)
    const N = 1

    for i := 0; i < N; i++ {
        // 检查是否完成
        if d.ht[0].used == 0 {
            // 所有键已迁移完成
            d.ht[0] = d.ht[1]
            d.ht[1] = nil
            d.rehashidx = -1
            return
        }

        // 跳过空桶
        for d.ht[0].table[d.rehashidx] == nil {
            d.rehashidx++
        }

        // 迁移当前桶的所有键
        entry := d.ht[0].table[d.rehashidx]
        for entry != nil {
            next := entry.next

            // 重新计算哈希值
            hash := d.hashFunc(entry.key)
            index := hash & d.ht[1].sizemask

            // 插入到新表 (头插法)
            entry.next = d.ht[1].table[index]
            d.ht[1].table[index] = entry

            d.ht[0].used--
            d.ht[1].used++

            entry = next
        }

        // 清空旧桶
        d.ht[0].table[d.rehashidx] = nil
        d.rehashidx++
    }
}

// Redis 定时任务 (每100ms执行一次)
func serverCron() {
    // 每次最多花费 1ms 推进 rehash
    start := time.Now()

    for _, db := range server.dbs {
        if db.dict.isRehashing() {
            // 每次迁移100个桶
            for i := 0; i < 100; i++ {
                db.dict.rehashStep()

                // 超时退出
                if time.Since(start) >= time.Millisecond {
                    return
                }
            }
        }
    }
}

// dict/dict.go
package dict

import (
    "fmt"
    "sync"
)

const (
    // 初始哈希表大小
    DICT_HT_INITIAL_SIZE = 4

    // 强制 rehash 的负载因子阈值
    DICT_FORCE_RESIZE_RATIO = 5
)

// 字典类型 (支持不同类型的键值)
type DictType struct {
    HashFunc  func(key interface{}) uint64        // 哈希函数
    KeyDup    func(key interface{}) interface{}   // 键复制
    ValDup    func(val interface{}) interface{}   // 值复制
    KeyCompare func(k1, k2 interface{}) bool      // 键比较
    KeyDestructor func(key interface{})           // 键析构
    ValDestructor func(val interface{})           // 值析构
}

// 字典节点
type DictEntry struct {
    key   interface{}
    value interface{}
    next  *DictEntry  // 链表指针 (解决冲突)
}

// 哈希表
type DictHt struct {
    table    []*DictEntry  // 哈希表数组
    size     uint64        // 哈希表大小
    sizemask uint64        // 哈希表大小掩码 (size - 1)
    used     uint64        // 已有节点数量
}

// 字典
type Dict struct {
    dictType  *DictType     // 类型特定函数
    privdata  interface{}   // 私有数据
    ht        [2]*DictHt    // 两个哈希表 (用于渐进式rehash)
    rehashidx int64         // rehash进度 (-1表示未进行)
    iterators int64         // 当前运行的迭代器数量
    mu        sync.RWMutex  // 读写锁
}

// 创建字典
func NewDict(dictType *DictType) *Dict {
    return &Dict{
        dictType:  dictType,
        ht:        [2]*DictHt{newDictHt(DICT_HT_INITIAL_SIZE), nil},
        rehashidx: -1,
        iterators: 0,
    }
}

// 创建哈希表
func newDictHt(size uint64) *DictHt {
    // 确保 size 是 2 的幂
    realSize := nextPower(size)

    return &DictHt{
        table:    make([]*DictEntry, realSize),
        size:     realSize,
        sizemask: realSize - 1,
        used:     0,
    }
}

// 计算下一个 2 的幂
func nextPower(size uint64) uint64 {
    if size >= (1 << 63) {
        return 1 << 63
    }

    n := uint64(DICT_HT_INITIAL_SIZE)
    for n < size {
        n *= 2
    }
    return n
}

// 默认哈希函数 (SipHash)
func defaultHashFunc(key interface{}) uint64 {
    switch k := key.(type) {
    case string:
        return sipHash([]byte(k))
    case int:
        return uint64(k) * 0x9e3779b97f4a7c15
    case int64:
        return uint64(k) * 0x9e3779b97f4a7c15
    case uint64:
        return k * 0x9e3779b97f4a7c15
    default:
        return sipHash([]byte(fmt.Sprintf("%v", k)))
    }
}

// SipHash 简化实现
func sipHash(data []byte) uint64 {
    // 简化版本,生产环境应使用完整SipHash
    h := uint64(0xcbf29ce484222325)
    for _, b := range data {
        h ^= uint64(b)
        h *= 0x100000001b3
    }
    return h
}

// dict/operations.go
package dict

// 设置键值对
func (d *Dict) Set(key, value interface{}) error {
    d.mu.Lock()
    defer d.mu.Unlock()

    // 渐进式 rehash
    if d.isRehashing() {
        d.rehashStep()
    }

    // 计算哈希值
    hash := d.dictType.HashFunc(key)

    // 确定使用哪个哈希表
    table := 0
    if d.isRehashing() {
        table = 1  // rehash期间,新键插入ht[1]
    }

    // 计算索引
    index := hash & d.ht[table].sizemask

    // 检查键是否已存在
    entry := d.ht[table].table[index]
    for entry != nil {
        if d.dictType.KeyCompare(entry.key, key) {
            // 更新值
            entry.value = value
            return nil
        }
        entry = entry.next
    }

    // 插入新节点 (头插法)
    newEntry := &DictEntry{
        key:   key,
        value: value,
        next:  d.ht[table].table[index],
    }
    d.ht[table].table[index] = newEntry
    d.ht[table].used++

    // 检查是否需要扩容
    d.expandIfNeeded()

    return nil
}

// 获取值
func (d *Dict) Get(key interface{}) (interface{}, bool) {
    d.mu.RLock()
    defer d.mu.RUnlock()

    if d.ht[0].used == 0 && (d.ht[1] == nil || d.ht[1].used == 0) {
        return nil, false
    }

    // 渐进式 rehash (读操作也推进)
    if d.isRehashing() {
        d.mu.RUnlock()
        d.mu.Lock()
        d.rehashStep()
        d.mu.Unlock()
        d.mu.RLock()
    }

    hash := d.dictType.HashFunc(key)

    // 先查 ht[0]
    if entry := d.findEntry(0, key, hash); entry != nil {
        return entry.value, true
    }

    // 如果在rehash,再查 ht[1]
    if d.isRehashing() {
        if entry := d.findEntry(1, key, hash); entry != nil {
            return entry.value, true
        }
    }

    return nil, false
}

// 删除键
func (d *Dict) Delete(key interface{}) bool {
    d.mu.Lock()
    defer d.mu.Unlock()

    if d.ht[0].used == 0 && (d.ht[1] == nil || d.ht[1].used == 0) {
        return false
    }

    // 渐进式 rehash
    if d.isRehashing() {
        d.rehashStep()
    }

    hash := d.dictType.HashFunc(key)

    // 先尝试从 ht[0] 删除
    if d.deleteEntry(0, key, hash) {
        return true
    }

    // 如果在rehash,再尝试从 ht[1] 删除
    if d.isRehashing() {
        return d.deleteEntry(1, key, hash)
    }

    return false
}

// 查找节点
func (d *Dict) findEntry(table int, key interface{}, hash uint64) *DictEntry {
    if d.ht[table] == nil {
        return nil
    }

    index := hash & d.ht[table].sizemask
    entry := d.ht[table].table[index]

    for entry != nil {
        if d.dictType.KeyCompare(entry.key, key) {
            return entry
        }
        entry = entry.next
    }

    return nil
}

// 删除节点
func (d *Dict) deleteEntry(table int, key interface{}, hash uint64) bool {
    if d.ht[table] == nil {
        return false
    }

    index := hash & d.ht[table].sizemask
    entry := d.ht[table].table[index]
    var prev *DictEntry

    for entry != nil {
        if d.dictType.KeyCompare(entry.key, key) {
            // 找到了,删除节点
            if prev == nil {
                d.ht[table].table[index] = entry.next
            } else {
                prev.next = entry.next
            }

            // 调用析构函数
            if d.dictType.KeyDestructor != nil {
                d.dictType.KeyDestructor(entry.key)
            }
            if d.dictType.ValDestructor != nil {
                d.dictType.ValDestructor(entry.value)
            }

            d.ht[table].used--
            return true
        }
        prev = entry
        entry = entry.next
    }

    return false
}

// 获取字典大小
func (d *Dict) Size() uint64 {
    d.mu.RLock()
    defer d.mu.RUnlock()

    size := d.ht[0].used
    if d.ht[1] != nil {
        size += d.ht[1].used
    }
    return size
}

// 检查是否为空
func (d *Dict) IsEmpty() bool {
    return d.Size() == 0
}

// dict/rehash.go
package dict

// 检查是否正在 rehash
func (d *Dict) isRehashing() bool {
    return d.rehashidx != -1
}

// 渐进式 rehash 一步
func (d *Dict) rehashStep() {
    if d.iterators == 0 {
        d.rehash(1)
    }
}

// rehash N 个桶
func (d *Dict) rehash(n int) int {
    if !d.isRehashing() {
        return 0
    }

    emptyVisits := n * 10  // 最多访问 10*n 个空桶

    for n > 0 && d.ht[0].used != 0 {
        // 跳过空桶
        for d.ht[0].table[d.rehashidx] == nil {
            d.rehashidx++
            emptyVisits--
            if emptyVisits == 0 {
                return 1  // 访问太多空桶,下次继续
            }
        }

        // 获取当前桶
        entry := d.ht[0].table[d.rehashidx]

        // 迁移当前桶的所有节点
        for entry != nil {
            next := entry.next

            // 重新计算哈希值
            hash := d.dictType.HashFunc(entry.key)
            index := hash & d.ht[1].sizemask

            // 头插法插入 ht[1]
            entry.next = d.ht[1].table[index]
            d.ht[1].table[index] = entry

            d.ht[0].used--
            d.ht[1].used++

            entry = next
        }

        // 清空旧桶
        d.ht[0].table[d.rehashidx] = nil
        d.rehashidx++
        n--
    }

    // 检查是否完成
    if d.ht[0].used == 0 {
        // 释放 ht[0],将 ht[1] 设置为 ht[0]
        d.ht[0] = d.ht[1]
        d.ht[1] = nil
        d.rehashidx = -1
        return 0  // 完成
    }

    return 1  // 未完成
}

// 检查是否需要扩容
func (d *Dict) expandIfNeeded() {
    // 已在 rehash,不处理
    if d.isRehashing() {
        return
    }

    // 哈希表为空,初始化
    if d.ht[0].size == 0 {
        d.expand(DICT_HT_INITIAL_SIZE)
        return
    }

    // 负载因子检查
    // 1. used >= size 且没有子进程在save → 扩容
    // 2. used / size >= 5 → 强制扩容
    ratio := float64(d.ht[0].used) / float64(d.ht[0].size)

    if (d.ht[0].used >= d.ht[0].size && !serverIsBackgroundSaving()) ||
        ratio >= DICT_FORCE_RESIZE_RATIO {
        d.expand(d.ht[0].used * 2)
    }
}

// 扩容
func (d *Dict) expand(size uint64) error {
    // 已在 rehash
    if d.isRehashing() {
        return fmt.Errorf("already rehashing")
    }

    // 计算实际大小 (≥ size 的最小2的幂)
    realSize := nextPower(size)

    // 不能缩小
    if realSize < d.ht[0].used {
        return fmt.Errorf("expand size too small")
    }

    // 创建新哈希表
    d.ht[1] = newDictHt(realSize)
    d.rehashidx = 0

    return nil
}

// 缩容
func (d *Dict) shrinkIfNeeded() {
    // TODO: 实现缩容逻辑
    // 当负载因子 < 0.1 时,缩容到合适大小
}

// 模拟检查是否有后台保存任务
func serverIsBackgroundSaving() bool {
    // 简化实现,实际应检查 BGSAVE/BGREWRITEAOF
    return false
}

// dict/iterator.go
package dict

// 字典迭代器
type DictIterator struct {
    d           *Dict
    table       int
    index       int64
    entry       *DictEntry
    nextEntry   *DictEntry
    fingerprint uint64
}

// 创建迭代器
func (d *Dict) GetIterator() *DictIterator {
    d.mu.RLock()

    iter := &DictIterator{
        d:           d,
        table:       0,
        index:       -1,
        entry:       nil,
        nextEntry:   nil,
        fingerprint: d.fingerprint(),
    }

    d.iterators++
    d.mu.RUnlock()

    return iter
}

// 获取下一个节点
func (iter *DictIterator) Next() *DictEntry {
    iter.d.mu.RLock()
    defer iter.d.mu.RUnlock()

    for {
        if iter.entry == nil {
            // 移动到下一个桶
            iter.index++

            // 检查是否遍历完当前表
            if iter.table == 0 && iter.index >= int64(iter.d.ht[0].size) {
                // 如果正在rehash,切换到ht[1]
                if iter.d.isRehashing() {
                    iter.table = 1
                    iter.index = 0
                } else {
                    break  // 遍历完成
                }
            } else if iter.table == 1 && iter.index >= int64(iter.d.ht[1].size) {
                break  // 遍历完成
            }

            // 获取当前桶的第一个节点
            if iter.table == 0 {
                iter.entry = iter.d.ht[0].table[iter.index]
            } else {
                iter.entry = iter.d.ht[1].table[iter.index]
            }
        } else {
            // 继续遍历当前链表
            iter.entry = iter.nextEntry
        }

        if iter.entry != nil {
            // 保存下一个节点
            iter.nextEntry = iter.entry.next
            return iter.entry
        }
    }

    return nil
}

// 释放迭代器
func (iter *DictIterator) Release() {
    iter.d.mu.Lock()
    defer iter.d.mu.Unlock()

    iter.d.iterators--

    // 检查指纹是否改变 (安全性检查)
    if iter.fingerprint != iter.d.fingerprint() {
        panic("dict was modified during iteration")
    }
}

// 计算指纹 (用于检测迭代期间是否被修改)
func (d *Dict) fingerprint() uint64 {
    integers := []uint64{
        uint64(uintptr(unsafe.Pointer(d.ht[0].table))),
        d.ht[0].size,
        d.ht[0].used,
    }

    if d.ht[1] != nil {
        integers = append(integers,
            uint64(uintptr(unsafe.Pointer(d.ht[1].table))),
            d.ht[1].size,
            d.ht[1].used,
        )
    }

    h := uint64(0)
    for _, v := range integers {
        h = h*31 + v
    }
    return h
}

// dict/dict_bench_test.go
package dict

import (
    "fmt"
    "math/rand"
    "testing"
)

// 默认字典类型
var defaultDictType = &DictType{
    HashFunc: defaultHashFunc,
    KeyCompare: func(k1, k2 interface{}) bool {
        return k1 == k2
    },
}

// 测试插入性能
func BenchmarkDictSet(b *testing.B) {
    d := NewDict(defaultDictType)

    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        key := fmt.Sprintf("key%d", i)
        d.Set(key, i)
    }
}

// 测试查找性能
func BenchmarkDictGet(b *testing.B) {
    d := NewDict(defaultDictType)

    // 预填充数据
    for i := 0; i < 1000000; i++ {
        key := fmt.Sprintf("key%d", i)
        d.Set(key, i)
    }

    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        key := fmt.Sprintf("key%d", rand.Intn(1000000))
        d.Get(key)
    }
}

// 测试删除性能
func BenchmarkDictDelete(b *testing.B) {
    d := NewDict(defaultDictType)

    // 预填充数据
    for i := 0; i < b.N; i++ {
        key := fmt.Sprintf("key%d", i)
        d.Set(key, i)
    }

    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        key := fmt.Sprintf("key%d", i)
        d.Delete(key)
    }
}

// 对比：Go 原生 map
func BenchmarkGoMap(b *testing.B) {
    m := make(map[string]int)

    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        key := fmt.Sprintf("key%d", i)
        m[key] = i
    }
}

type RedisDb struct {
    dict    *Dict  // 主字典：存储所有键值对
    expires *Dict  // 过期字典：存储键的过期时间
    id      int    // 数据库编号
}

// SET key value
func (db *RedisDb) Set(key string, value interface{}) {
    db.dict.Set(key, value)
}

// GET key
func (db *RedisDb) Get(key string) (interface{}, bool) {
    // 先检查是否过期
    if db.IsExpired(key) {
        db.Delete(key)
        return nil, false
    }

    return db.dict.Get(key)
}

// EXPIRE key seconds
func (db *RedisDb) Expire(key string, seconds int64) {
    expireAt := time.Now().Unix() + seconds
    db.expires.Set(key, expireAt)
}

// 检查是否过期
func (db *RedisDb) IsExpired(key string) bool {
    expireAt, exists := db.expires.Get(key)
    if !exists {
        return false
    }

    return time.Now().Unix() > expireAt.(int64)
}

// DEL key
func (db *RedisDb) Delete(key string) bool {
    db.expires.Delete(key)  // 删除过期时间
    return db.dict.Delete(key)
}

// 1. 正常情况: α ≥ 1.0 → 扩容
if used >= size {
    expand()
}

// 2. BGSAVE期间: α ≥ 5.0 → 才扩容
// 原因: 写时复制(COW)机制,延迟扩容减少内存拷贝
if isBGSaving() && used >= size * 5 {
    expand()
}

//  差的哈希函数
func badHash(s string) uint64 {
    return uint64(len(s))  // 只依赖长度,冲突严重!
}

//  好的哈希函数 (FNV-1a)
func fnvHash(s string) uint64 {
    h := uint64(14695981039346656037)  // FNV offset basis
    for _, c := range s {
        h ^= uint64(c)
        h *= 1099511628211  // FNV prime
    }
    return h
}

// SipHash 使用随机种子,攻击者无法预测哈希值
func sipHash(key []byte, seed [16]byte) uint64 {
    // 密码学级别的哈希函数
    // 即使知道算法,不知道 seed 也无法构造冲突
}

// 每次启动使用不同的随机种子
seed := generateRandomSeed()

// 当链表过长时,拒绝插入或报警
if chainLength > MAX_CHAIN_LENGTH {
    return error("possible hash flooding attack")
}

// 提示：环形哈希 + 虚拟节点
type ConsistentHash struct {
    circle map[uint64]string  // 哈希环
    nodes  []uint64           // 排序的哈希值
}

// 提示：哈希表 + 双向链表
type LRUCache struct {
    capacity int
    cache    map[string]*Node
    head     *Node
    tail     *Node
}

// 提示：多个哈希函数 + 位数组
type BloomFilter struct {
    bits []bool
    hashFuncs []func(string) uint64
}