哈希表的原理
摘要
- 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 国际许可协议进行许可。