数据结构 - hashtable

// 对外暴露的hashtable
type LinkedDict struct {
	// 2个存储桶，0号正常使用，1号在rehash过程中使用；rehash完成之后，1号赋值给0号然后重置1号。
	ht [2]*hashtable
	// 初始值 -1，表示没有在rehash
	rehashIdx int
}

// 存储桶
type hashtable struct {
	// 底层“数组”
	table []*dictEntry
	size int
	sizemask int
	used int
}

// hashtable 元素定义
type dictEntry struct {
	key string
	value interface{}
	next *dictEntry
}

func (d *LinkedDict) Set(key string, value interface{}) {
	if d.ht[0].table == nil {
		d.ht[0].init(InitTableSize)
	}

	// isRehashing 判定：`rehashIdx != -1`
	// needRehash 判定: 装载因子 used / size > 1.0 时触发扩容rehash
	if !d.isRehashing() && d.needRehash() {
		// rehashGrowup 表示本次rehash是需要扩容，在配置ht[1].table时会扩展为当前的2倍
		// 反之则会缩减内存空间
		// startrehash 会设置 rehashIdx = 0, 标志rehash的进度
		d.startrehash(rehashGrowup) 
	}

	if d.isRehashing() {
		// 如果在rehash过程中，则完成一部分任务: 
		// 根据rehash的进度rehashIdx，选择搬移 d.ht[0].table[rehashIdx]部分的数据，添加到d.ht[1]中
		d.steprehash()
	}

	// 上述工作完成之后，就可以考虑新增数据了
	hashkey := d.hashkey(key)
	if d.isRehashing() {
		// 如果在rehash过程中，毋庸考虑，直接新增到d.ht[1]中
		d.ht[1].insert(hashkey, newDictEntry(key, value, nil))
		return
	}

	// 反之，不在rehash过程中，则直接新增到d.ht[0]中
	d.ht[0].insert(hashkey, newDictEntry(key, value, nil))
	return
}

// 渐进式rehash，根据rehashIdx确定，要搬移那一部分的数据。
func (d *LinkedDict) steprehash() {
	entry := d.ht[0].table[d.rehashIdx]
	// 如果rehashIdx指向的侧链为空，则rehashIdx自增，直到找到有数据的侧链或者数据均搬移完成
	for entry == nil {
		d.rehashIdx++
		if d.rehashIdx > d.ht[0].sizemask {
			d.finishrehash()
			return
		}
		entry = d.ht[0].table[d.rehashIdx]
	}

	// 开始搬移动作
	// 遍历链表，将所有数据，新增到d.ht[1]中
	next := entry.next
	for entry != nil {
		entry.next = nil
		d.ht[1].insert(d.hashkey(entry.key), entry)
		if next == nil {
			break
		}
		entry = next
		next = next.next
	}

	// 释放d.ht[0].table[rehashIdx]链表：避免干扰查询；释放内存
	d.ht[0].table[d.rehashIdx] = nil
	d.rehashIdx++

	if d.rehashIdx > d.ht[0].sizemask {
		// 是否已经结束，如果结束则：
		// d.ht[0] = d.ht[1]
		// d.ht[1] = newHashTable()
		// rehashIdx = -1
		d.finishrehash()
	}
}

// 新增一个元素到到存储桶：
// 根据hash函数的结果(hashkey)对存储桶大小(size)取模得到结果(pos)；ht.table[pos]完成对链表的新增工作。
func (ht *hashtable) insert(hashkey uint64, item *dictEntry) {
	pos := hashkey % uint64(ht.size)
	entry := ht.table[pos]
	last := entry
	if entry == nil {
		ht.used++
		ht.table[pos] = item
		return
	}

	for entry != nil {
		if ht.keyCompare(entry.key, item.key) {
			// 如果key已经存在则覆盖旧值
			entry.value = item.value
			return
		}
		last = entry
		entry = entry.next
	}
	ht.used++
	last.next = item
}

func (d *LinkedDict) Get(key string) (v interface{}, ok bool) {
	// 同上SET，不过多赘述
	if d.isRehashing() {
		d.steprehash()
	}

	hashkey := d.hashkey(key)
	v, ok = d.ht[0].lookup(hashkey, key)
	if !d.isRehashing() {
		// 如果不在rehash过程中 d.ht[0]中检索的结果便是最终结果
		return
	} else if ok {
		// 如果在rehash过程中且命中，也返回结果
		return v, ok
	}

	// 反之 rehash过程中，但在d.ht[0]中没找到，却不代表该key真的不存在, 还需要在d.ht[1]中确定
	v, ok = d.ht[1].lookup(hashkey, key)
	return
}

// Del to delete an item in hashtable.
func (d *LinkedDict) Del(key string) {
	if d.ht[0].used == 0 && d.ht[1].used == 0 {
		return
	}

	// 这里相比Set，区别在于：判定的内容不是是否需要扩容而是缩容
	// 缩容判定：d.ht[0]的内存空间大于初始值4且“填充率”少于 10%
	// d.ht[0].size > 4 && (d.ht[0].used*100/d.ht[0].size) < 10
	if !d.isRehashing() && d.needShrink() {
		d.startrehash(rehashShrink)
	}

	if d.isRehashing() {
		d.steprehash()
	}

	hashkey := d.hashkey(key)
	d.ht[0].del(hashkey, key)

	if d.isRehashing() {
		d.ht[1].del(hashkey, key)
	}
}

builtinMap_1000                  cost: 0ms
builtinLinkedDict_1000           cost: 0ms
getMap_1000                      cost: 0ms
getLinkedDict_1000               cost: 0ms

builtinMap_10000                 cost: 4ms
builtinLinkedDict_10000          cost: 6ms
getMap_10000                     cost: 2ms
getLinkedDict_10000              cost: 5ms

builtinMap_100000                cost: 76ms
builtinLinkedDict_100000         cost: 108ms
getMap_100000                    cost: 56ms
getLinkedDict_100000             cost: 131ms

builtinMap_1000000               cost: 1053ms
builtinLinkedDict_1000000        cost: 1230ms
getMap_1000000                   cost: 581ms
getLinkedDict_1000000            cost: 915ms

builtinMap_10000000              cost: 13520ms
builtinLinkedDict_10000000       cost: 17137ms
getMap_10000000                  cost: 8663ms
getLinkedDict_10000000           cost: 14271ms