面试题：Go自定义哈希表设计

设计思路

数据结构：
- 使用一个二维数组 buckets 作为哈希表的基础结构，buckets 的每个元素是一个链表，用于存储哈希冲突的键值对。
- 定义一个 loadFactor 表示负载因子，当哈希表中元素数量与 buckets 长度的比值超过 loadFactor 时，进行扩容；当元素数量与 buckets 长度的比值低于一定阈值（如 loadFactor / 4）时，进行缩容。
- 为了支持高并发，使用 sync.RWMutex 来保护对哈希表的读写操作。
方法实现：
- NewCustomHashMap：初始化哈希表，设置初始容量和负载因子。
- HashFunc：自定义哈希函数，可根据业务需求进行调整。
- Put：向哈希表中插入键值对，若键已存在则更新值。插入后检查是否需要扩容。
- Get：从哈希表中获取键对应的值。
- Delete：从哈希表中删除键值对，删除后检查是否需要缩容。
- resize：扩容或缩容哈希表，重新计算所有键值对的哈希位置并重新分配。
并发安全问题处理：
- 使用 sync.RWMutex，读操作使用读锁（RLock），写操作（插入、删除、扩容、缩容）使用写锁（Lock），以保证在高并发环境下数据的一致性和安全性。

代码实现

package main

import (
    "container/list"
    "fmt"
    "sync"
)

// 定义键值对
type KeyValue struct {
    key   interface{}
    value interface{}
}

// 自定义哈希表结构体
type CustomHashMap struct {
    buckets    []*list.List
    count      int
    loadFactor float64
    mutex      sync.RWMutex
}

// 创建新的自定义哈希表
func NewCustomHashMap(initialCapacity int, loadFactor float64) *CustomHashMap {
    if initialCapacity <= 0 {
        initialCapacity = 16
    }
    if loadFactor <= 0 {
        loadFactor = 0.75
    }
    return &CustomHashMap{
        buckets:    make([]*list.List, initialCapacity),
        loadFactor: loadFactor,
    }
}

// 自定义哈希函数
func (hm *CustomHashMap) HashFunc(key interface{}) int {
    // 简单示例，实际可根据业务调整
    switch key := key.(type) {
    case int:
        return key % len(hm.buckets)
    case string:
        sum := 0
        for _, char := range key {
            sum += int(char)
        }
        return sum % len(hm.buckets)
    default:
        return 0
    }
}

// 插入键值对
func (hm *CustomHashMap) Put(key, value interface{}) {
    hm.mutex.Lock()
    defer hm.mutex.Unlock()

    index := hm.HashFunc(key)
    if hm.buckets[index] == nil {
        hm.buckets[index] = list.New()
    }
    for e := hm.buckets[index].Front(); e != nil; e = e.Next() {
        pair := e.Value.(KeyValue)
        if pair.key == key {
            pair.value = value
            return
        }
    }
    hm.buckets[index].PushBack(KeyValue{key, value})
    hm.count++
    if float64(hm.count)/float64(len(hm.buckets)) >= hm.loadFactor {
        hm.resize(true)
    }
}

// 获取键对应的值
func (hm *CustomHashMap) Get(key interface{}) (interface{}, bool) {
    hm.mutex.RLock()
    defer hm.mutex.RUnlock()

    index := hm.HashFunc(key)
    if hm.buckets[index] == nil {
        return nil, false
    }
    for e := hm.buckets[index].Front(); e != nil; e = e.Next() {
        pair := e.Value.(KeyValue)
        if pair.key == key {
            return pair.value, true
        }
    }
    return nil, false
}

// 删除键值对
func (hm *CustomHashMap) Delete(key interface{}) {
    hm.mutex.Lock()
    defer hm.mutex.Unlock()

    index := hm.HashFunc(key)
    if hm.buckets[index] == nil {
        return
    }
    for e := hm.buckets[index].Front(); e != nil; e = e.Next() {
        pair := e.Value.(KeyValue)
        if pair.key == key {
            hm.buckets[index].Remove(e)
            hm.count--
            if float64(hm.count)/float64(len(hm.buckets)) <= hm.loadFactor/4 && len(hm.buckets) > 16 {
                hm.resize(false)
            }
            return
        }
    }
}

// 扩容或缩容
func (hm *CustomHashMap) resize(isExpand bool) {
    newCapacity := len(hm.buckets)
    if isExpand {
        newCapacity *= 2
    } else {
        newCapacity /= 2
    }
    newBuckets := make([]*list.List, newCapacity)
    for _, bucket := range hm.buckets {
        if bucket != nil {
            for e := bucket.Front(); e != nil; e = e.Next() {
                pair := e.Value.(KeyValue)
                index := hm.HashFunc(pair.key)
                if newBuckets[index] == nil {
                    newBuckets[index] = list.New()
                }
                newBuckets[index].PushBack(pair)
            }
        }
    }
    hm.buckets = newBuckets
}

你可以通过以下方式调用：

func main() {
    hm := NewCustomHashMap(16, 0.75)
    hm.Put("key1", "value1")
    value, exists := hm.Get("key1")
    if exists {
        fmt.Printf("Value for key1: %v\n", value)
    }
    hm.Delete("key1")
    value, exists = hm.Get("key1")
    if exists {
        fmt.Printf("Value for key1: %v\n", value)
    } else {
        fmt.Println("Key key1 not found")
    }
}

星途面试题库

面试题：Go自定义哈希表设计

知识考点

面试题答案

设计思路

代码实现