3B.md

多路Hash表

狡兔三窟

　　解决Hash冲突的另一个重要思想是分散风险。将元素分散到拥有不同Hash函数的子Hash表中，可以期望某元素在所有子表中都遇到冲突的可能性较低。

type node struct {      //元素节点
    code [4]uint32
    key  string
}
type hashSet struct {
    buckets [4][]*node  //有多个子表
    master  int         //当前主表号
    size    int
}

我们把子表组织成环状队列，并且其容量递减，这样可以在扩容时获得一些便利。

func (s *hashSet) init() {
    s.master, s.size = 0, 0
    size := 2                   //2^n
    for i := 3; i >= 0; i-- {
        size *= 2               //逆向倍增即顺向减半
        s.buckets[i] = make([]*node, size)
}   }

func (s *hashSet) expand() {
    s.master = (s.master + 3) % 4
    oldBucket := s.buckets[s.master]
    bucket := make([]*node, len(oldBucket)<<4)
    for _, unit := range oldBucket {
        if unit != nil {
            pos := mod(unit.code[s.master], len(bucket))
            bucket[pos] = unit  //倍扩，绝对不会冲突
    }   }
    s.buckets[s.master] = bucket
}

接力

　　当插入一个元素时，仅仅让这个元素在不同子表处碰运气是不够的，我们要将已经在表内的元素也调动起来。具体地说，就是当元素A在子表1中遇到冲突元素B时，不是转向子表2，而是将B换出，并让B到子表2寻求落点。

func (s *hashSet) Insert(key string) bool {
    if s.find(key, false) { return false }
    s.size++
    unit := new(node)
    unit.key = key
    unit.code = hash(key)
    for obj, age := unit, 0; ; age++ {
        for idx, trys := s.master, 0; trys < 4; idx = (idx + 1) % 4 {
            bucket := s.buckets[idx]
            pos := mod(obj.code[idx], len(bucket))
            if bucket[pos] == nil {
                bucket[pos] = obj           //找到空位
                return true                 //结束
            }
            obj, bucket[pos] = bucket[pos], obj
            if obj == unit {
                trys++                      //回绕计数
        }   }
        if age > 0 {                        //这里设定一个阈值，限制扩容次数
            panic("too many conflicts")     //实际上不能解决大量hash重码的情况，最坏情况只能报错
        }
        s.expand()                          //调整失败(回绕)，扩容
    }
    return false
}

与开链式比较

　　多路Hash表的实现比开链式Hash表要复杂很多，而且不如后者稳定可靠。不过，多路Hash表可以保证最坏情况下单个元素的查询时间。

---

目录　上一节　下一节