一文搞懂Go实现HashTable

// HashTable 是一个自定义的哈希表结构
type HashTable struct {
	buckets    []*Bucket // 存储桶数组
	loadFactor float64   // 加载因子，当达到某个阈值时触发扩容
	capacity   int       // 当前容量
}

// Bucket 是哈希表中的一个存储桶
type Bucket struct {
	key   interface{}
	value interface{}
	next  *Bucket // 链表下一个节点
}

// NewHashTable 创建一个新的哈希表
func NewHashTable(capacity int, loadFactor float64) *HashTable {
	if capacity <= 0 {
		capacity = 1
	}
	if loadFactor <= 0 || loadFactor >= 1 {
		loadFactor = 0.75
	}
	return &HashTable{
		buckets:    make([]*Bucket, capacity),
		loadFactor: loadFactor,
		capacity:   capacity,
	}
}

// hash 计算键的哈希值并返回其在存储桶数组中的索引
func (h *HashTable) hash(key interface{}) int {
	hasher := fnv.New32a()
	_, _ = hasher.Write([]byte(fmt.Sprintf("%v", key)))
	return int(hasher.Sum32()) % h.capacity
}

// Put 向哈希表中添加或更新一个键值对
func (h *HashTable) Put(key, value interface{}) {
	index := h.hash(key)
	bucket := h.buckets[index]

	// 查找是否存在相同的键
	for bucket != nil {
		if bucket.key == key {
			bucket.value = value // 更新值
			return
		}
		bucket = bucket.next
	}

	// 创建新节点并添加到链表末尾
	newNode := &Bucket{key: key, value: value}
	if h.buckets[index] == nil {
		h.buckets[index] = newNode
	} else {
		lastBucket := h.buckets[index]
		for lastBucket.next != nil {
			lastBucket = lastBucket.next
		}
		lastBucket.next = newNode
	}

	// 检查是否需要扩容
	if float64(len(h.buckets))*h.loadFactor < float64(len(h.buckets)+len(h.buckets[:index])+1) {
		h.resize()
	}
}

// Get 从哈希表中获取一个键对应的值
func (h *HashTable) Get(key interface{}) (interface{}, bool) {
	index := h.hash(key)
	bucket := h.buckets[index]

	for bucket != nil {
		if bucket.key == key {
			return bucket.value, true
		}
		bucket = bucket.next
	}

	return nil, false
}

// Delete 从哈希表中删除一个键值对
func (h *HashTable) Delete(key interface{}) {
	index := h.hash(key)
	bucket := h.buckets[index]
	prev := &bucket

	for bucket != nil {
		if bucket.key == key {
			// 移除节点
			*prev = bucket.next
			return
		}
		prev = &bucket.next
		bucket = bucket.next
	}
}

// resize 重新调整哈希表的大小
func (h *HashTable) resize() {
	newCapacity := h.capacity * 2
	newBuckets := make([]*Bucket, newCapacity)

	for _, bucket := range h.buckets {
		for bucket != nil {
			index := h.hash(bucket.key) // 重新计算新索引
			next := bucket.next
			bucket.next = newBuckets[index]
			newBuckets[index] = bucket
			bucket = next
		}
	}

	h.buckets = newBuckets
	h.capacity = newCapacity
}

func main() {  
	hashTable := NewHashTable(10, 0.75)  
  
	hashTable.Put("name", "John")  
	hashTable.Put("age", 30)  
	hashTable.Put("city", "New York")  
  
	fmt.Println("Initial HashTable:", hashTable)  
	fmt.Println("Length:", hashTable.Len())  
	fmt.Println("Is Empty?", hashTable.IsEmpty())  
	fmt.Println("Contains 'name'?", hashTable.Contains("name"))  
  
	hashTable.Iterate()  
  
	value, found := hashTable.Get("age")  
	if found {  
		fmt.Println("Found age:", value)  
	}  
  
	hashTable.Delete("age")  
	fmt.Println("HashTable after deleting 'age':", hashTable)  
  
	// Trigger resize  
	for i := 0; i < 100; i++ {  
		hashTable.Put(fmt.Sprintf("key%d", i), i)  
	}  
  
	fmt.Println("HashTable after resizing:", hashTable)  
}