哈希表

哈希表(hash table)，又称散列表。它通过建立键(key)与值(value)之间的映射关系，实现高效的元素查询效率。具体而言，我们向哈希表输入一个键值key，则可以在O(1)时间内获取对应的值value。同样在哈希表中添加元素，删除元素，时间复杂度均为O(1)。

哈希表常用操作

哈希表常用操作包括：初始化，查询，添加键值对，删除键值对。示例代码如下:

// 初始化
var ht = make(map[string]string)

// 添加操作
ht["12301"] = "小文"
ht["12302"] = "小学"
ht["12303"] = "小天"

// 查询操作
name := ht["12301"]

// 删除操作
delete (ht, "12301")

哈希表遍历：

for key, value := range ht {
    fmt.Printf("%s = %s \n"), key, value  
}

哈希表简单实现

我们考虑最简单的情况，使用数组来实现哈希表。在哈希表中，我们将数组中每个空位称为桶（bucket），每个桶可存储一个键值对。因此，查询操作就是找到key对应的桶，并在桶中获取value。
那么，如何基于key定位对应的桶呢？这时通过哈希函数实现的。哈希函数的作用是将一个较大的输入空间映射到一个较小的输出空间。在hash表中，输入空间是所有Key,输出空间是所有桶（数组索引）。换句话说，我们可以通过哈希函数得到该key对应的键值对在数组中的存储位置。这个过程分为两步：

• 1. 通过某种哈希算法计算得到哈希值。
• 2. 将哈希值对桶容量(capacity)取模，从而获取该key对应的数组索引index。
     index = hash(key) % capacity，至此我们的代码实现如下：

/* 键值对 */
type pair struct {
    key int
    val string
}

/* 基于数组实现的哈希表 */
type arrayHashMap struct {
    buckets []*pair
}

/* 初始化哈希表 */
func newArrayHashMap() *arrayHashMap {
    // 初始化数组，包含 100 个桶
    buckets := make([]*pair, 100)
    return &arrayHashMap{buckets: buckets}
}

/* 哈希函数 */
func (a *arrayHashMap) hashFunc(key int) int {
    index := key % 100
    return index
}

/* 查询操作 */
func (a *arrayHashMap) get(key int) string {
    index := a.hashFunc(key)
    pair := a.buckets[index]
    if pair == nil {
        return "Not Found"
    }
    return pair.val
}

/* 添加操作 */
func (a *arrayHashMap) put(key int, val string) {
    pair := &pair{key: key, val: val}
    index := a.hashFunc(key)
    a.buckets[index] = pair
}

/* 删除操作 */
func (a *arrayHashMap) remove(key int) {
    index := a.hashFunc(key)
    // 置为 nil ，代表删除
    a.buckets[index] = nil
}

/* 获取所有键对 */
func (a *arrayHashMap) pairSet() []*pair {
    var pairs []*pair
    for _, pair := range a.buckets {
        if pair != nil {
            pairs = append(pairs, pair)
        }
    }
    return pairs
}

/* 获取所有键 */
func (a *arrayHashMap) keySet() []int {
    var keys []int
    for _, pair := range a.buckets {
        if pair != nil {
            keys = append(keys, pair.key)
        }
    }
    return keys
}

/* 获取所有值 */
func (a *arrayHashMap) valueSet() []string {
    var values []string
    for _, pair := range a.buckets {
        if pair != nil {
            values = append(values, pair.val)
        }
    }
    return values
}

/* 打印哈希表 */
func (a *arrayHashMap) print() {
    for _, pair := range a.buckets {
        if pair != nil {
            fmt.Println(pair.key, "->", pair.val)
        }
    }
}

以上代码实现中，我们定义了键值对pair，桶buckets，通过自定义的hasfFunc函数来建立键值对之间的映射关系。实现比较简单。

哈希冲突与扩容

从本质上看，哈希函数的作用是将所有的的key构成的输入空间映射到数组所有索引构成的输出空间,而输入空间远大于输出空间。因此，理论上一定存在“多个输入对应相同输出”的情况。

哈希冲突

hash_table_reshash.png

类似于数组扩容，哈希表扩容需将所有的键值对从原哈希表迁移至新哈希表，非常耗时。并且，由于哈希表容量改变，我们需要计算所有的key来重新计算所有键值对的位置,这进一步增加了扩容的计算开销。为此，一些编程语言通常会预留足够大的哈希表容量，防止频繁扩容。

负载因子(load factor)是哈希表的一个重要概念，其定义为哈希表元素数量除以桶数量，用于衡量哈希冲突的严重情况，也常作为哈希表扩容的触发条件。

改良方案

通常情况下哈希函数的输入空间远大于输出空间，因此理论上哈希冲突是不可避免地。哈希冲突会导致查询结果错误，严重影响哈希表的可用性。每次遇到哈希冲突时，我们就进行哈希表扩容，此方法简单粗暴，但效率太低，因为哈希表扩容需要进行大量的数据搬运和哈希值计算，为了提升效率，我们可以采用以下策略：

• 改良哈希表数据结构，使得哈希表可以在出现哈希冲突时正常工作。
• 仅在必要时，才进行哈希表扩容。

哈希表的改良方法主要包括：链式地址和开放寻址

链式地址

在原始哈希表中，每个桶仅能存储一个键值对。链式地址将单个元素转换为链表，将键值对作为链表节点，将所有发生冲突的键值对都存储在同一链表中。

哈希表结构

发生改变后的哈希表操作上变化：

• 查询元素：输入key，经过哈希函数得到桶索引，即可访问链表头节点，然后遍历链表并对比key以查找目标键值对。
• 添加元素：首先通过哈希函数访问链表头节点，然后将节点添加到链表中。
• 删除元素：根据哈希函数的结果访问链表头部，接着遍历链表以查找目标节点并将其删除。
• 占用空间增大：链表包含节点指针，它相比数组更加耗费内存空间。
• 查询效率降低：因为需要线性遍历链表来查找对应元素。

以下是一个简单实现：

/* 链式地址哈希表 */
type hashMapChaining struct {
    size        int      // 键值对数量
    capacity    int      // 哈希表容量
    loadThres   float64  // 触发扩容的负载因子阈值
    extendRatio int      // 扩容倍数
    buckets     [][]pair // 桶数组
}

/* 构造方法 */
func newHashMapChaining() *hashMapChaining {
    buckets := make([][]pair, 4)
    for i := 0; i < 4; i++ {
        buckets[i] = make([]pair, 0)
    }
    return &hashMapChaining{
        size:        0,
        capacity:    4,
        loadThres:   2.0 / 3.0,
        extendRatio: 2,
        buckets:     buckets,
    }
}

/* 哈希函数 */
func (m *hashMapChaining) hashFunc(key int) int {
    return key % m.capacity
}

/* 负载因子 */
func (m *hashMapChaining) loadFactor() float64 {
    return float64(m.size) / float64(m.capacity)
}

/* 查询操作 */
func (m *hashMapChaining) get(key int) string {
    idx := m.hashFunc(key)
    bucket := m.buckets[idx]
    // 遍历桶，若找到 key ，则返回对应 val
    for _, p := range bucket {
        if p.key == key {
            return p.val
        }
    }
    // 若未找到 key ，则返回空字符串
    return ""
}

/* 添加操作 */
func (m *hashMapChaining) put(key int, val string) {
    // 当负载因子超过阈值时，执行扩容
    if m.loadFactor() > m.loadThres {
        m.extend()
    }
    idx := m.hashFunc(key)
    // 遍历桶，若遇到指定 key ，则更新对应 val 并返回
    for i := range m.buckets[idx] {
        if m.buckets[idx][i].key == key {
            m.buckets[idx][i].val = val
            return
        }
    }
    // 若无该 key ，则将键值对添加至尾部
    p := pair{
        key: key,
        val: val,
    }
    m.buckets[idx] = append(m.buckets[idx], p)
    m.size += 1
}

/* 删除操作 */
func (m *hashMapChaining) remove(key int) {
    idx := m.hashFunc(key)
    // 遍历桶，从中删除键值对
    for i, p := range m.buckets[idx] {
        if p.key == key {
            // 切片删除
            m.buckets[idx] = append(m.buckets[idx][:i], m.buckets[idx][i+1:]...)
            m.size -= 1
            break
        }
    }
}

/* 扩容哈希表 */
func (m *hashMapChaining) extend() {
    // 暂存原哈希表
    tmpBuckets := make([][]pair, len(m.buckets))
    for i := 0; i < len(m.buckets); i++ {
        tmpBuckets[i] = make([]pair, len(m.buckets[i]))
        copy(tmpBuckets[i], m.buckets[i])
    }
    // 初始化扩容后的新哈希表
    m.capacity *= m.extendRatio
    m.buckets = make([][]pair, m.capacity)
    for i := 0; i < m.capacity; i++ {
        m.buckets[i] = make([]pair, 0)
    }
    m.size = 0
    // 将键值对从原哈希表搬运至新哈希表
    for _, bucket := range tmpBuckets {
        for _, p := range bucket {
            m.put(p.key, p.val)
        }
    }
}

/* 打印哈希表 */
func (m *hashMapChaining) print() {
    var builder strings.Builder

    for _, bucket := range m.buckets {
        builder.WriteString("[")
        for _, p := range bucket {
            builder.WriteString(strconv.Itoa(p.key) + " -> " + p.val + " ")
        }
        builder.WriteString("]")
        fmt.Println(builder.String())
        builder.Reset()
    }
}

开放定址

开放寻址不引入额外的数据结构，而是通过多次探测来处理哈希冲突，探测方式主要分为：线性探测，平方探测和多次哈希等。

1. 线性探测
   线性探测采用固定步长的线性搜索来进行探测。

• 插入元素：通过哈希函数计算桶索引，若发现桶内已有元素，则从冲突位置向后线性遍历，直到找到空桶，将元素插入其中。
• 查找元素：若发现哈希冲突，则使用相同步长向后进行线性遍历，直到找到对应元素，返回 value 即可；如果遇到空桶，说明目标元素不在哈希表中，返回 None 。