哈希表的原理

摘要

HashMap和HashSet的联系和区别
哈希表Hash Table的基本原理
什么是哈希函数Hash Function
如何解决冲突Collision
- 开散列Open Hash
- 闭散列Closed Hash
哈希表扩容问题

哈希表的基本原理

O (size of key)

开哈希

每个位置存储一个链表

闭哈希

每个位置存储一个 <key, value> pair
闭哈希在删除元素注意需要把位置置为 deleted 状态，防止查找时找不到因冲突而放到后面的元素

128 · 哈希函数

取模过程要使用同余定理：
(a * b ) % MOD = ((a % MOD) * (b % MOD)) % MOD

/**
 * @param key: A string you should hash
 * @param hASH_SIZE: An integer
 * @return: An integer
 */
func HashCode(key string, hASH_SIZE int) int {
	var ans int
	for _, r := range key {
		ans = (ans*33 + int(r)) % hASH_SIZE
	}
	return ans
}

129 · 重哈希

func Rehashing(hashTable []*ListNode) []*ListNode {
	newTable := make([]*ListNode, len(hashTable)*2)
	for _, node := range hashTable {
		p := node
		for p != nil {
			addNode(newTable, p.Val)
			p = p.Next
		}
	}
	return newTable
}

func addListNode(node *ListNode, num int) {
	if node.Next != nil {
		addListNode(node.Next, num)
	} else {
		node.Next = &ListNode{Val: num}
	}
}

func addNode(newTable []*ListNode, num int) {
	idx := num % len(newTable)
	if newTable[idx] == nil {
		newTable[idx] = &ListNode{Val: num}
	} else {
		addListNode(newTable[idx], num)
	}
}

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。