最新要闻

广告

手机

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

家电

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

来源:博客园


(资料图片)

数据结构 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 mainfunc 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 函数

关键词: