数据结构 in Golang:Hash Tables(哈希表)

数据结构inGolang:HashTables(哈希表)场景水果店的价格表:苹果Apple:3元香蕉Banana:4元桃子Peach:2元梨Pear:3元找到一种水果的价格:可以使用binarysearch,通过名称来查找,耗时:O(logn)如何只耗时

数据结构 in Golang:Hash Tables(哈希表)

场景

  • 水果店的价格表:
    • 苹果 Apple:3元
    • 香蕉 Banana:4元
    • 桃子 Peach:2元
    • 梨 Pear:3元
  • 找到一种水果的价格:
    • 可以使用 binary search,通过名称来查找,耗时:O(logn)
    • 如何只耗时 O(1) 来找到价格呢?

Hash 函数

  • Hash 函数:通过一个字符串 -> 一个数值
  • 例如:
    • "Apple" -> 1
    • "Banana" -> 2
    • "Peach" -> 7
    • "Pear" -> 8
  • 将字符串映射为数值

Hash 函数的要求

  • 一致性
  • 将不同的字符串映射为不同的数值

Hash 函数有什么用?

方便 快捷的得到自己想要的值...

Hash Table

  • Hash 函数 + 数组 = Hash Table
  • 数组直接映射到内存
  • Hash Table 具有额外的逻辑,它使用 Hash 函数智能的找到存放元素的位置
  • 在 Go 语言中叫 Map
package main

func main() {
  dict := make(map[string]int)
  dict1 := map[string]int{"Apple": 3, "Orange": 4}
}
  • 其它语言中:Dictionary、Map、Hash Map......

使用场景

  • 电话簿
  • DNS 解析
  • 缓存

冲突

  • 冲突就是:两个 Key 被安排到了同一个位置
  • 也就是说:K1 != K2,但 H(K1) == H(K2)

解决冲突

  • 开放地址法、再 Hash 法、建立公共溢出区 ...
  • 链地址法:链表

注意

  • Hash 函数应尽可能的将 Key 平均的映射
  • 如果链表过长,会让 Hash Table 变得很慢

选择 Hash 函数

Hash Table 平均 Hash Table 最坏 数组 链表
查找 O(1) O(n) O(1) O(n)

避免冲突

  • 装载因子(load factor)要低
  • 一个好的 Hash 函数

装载因子(load factor)

  • 调整大小,Resize
    • 例如:load factor 为 75% 的时候,就可以调整大小,通常是原来大小的两倍
    • 注意:调整大小也会花费很多时间

选择好的 Hash 函数

  • 好的 Hash 函数会将值尽可能的平均分布在数组中
  • 不好的 Hash 函数经常会把值聚集,并产生很多冲突
  • 通常不需要自己编写 Hash 函数,可以了解 SHA 函数
点赞 0
收藏 0
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
寻月隐君
寻月隐君
0x750E...B6f5
不要放弃,如果你喜欢这件事,就不要放弃。如果你不喜欢,那这也不好,因为一个人不应该做自己不喜欢的事。