内容简介:简单说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。一个优秀的Hash算法,将能实现:
Hash(散列函数)
简单说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
一个优秀的Hash算法,将能实现:
正向快速 逆向困难 输入敏感 冲突避免
典型的Hash算法
//将任何长度的字符串,通过运算,散列成0-15整数 func HashCode(key string) int { var index int = 0 index = int(key[0]) for k := 0; k < len(key); k++ { //1103515245是个好数字,使通过hashCode散列出的0-15的数字的概率是相等的 index *= (1103515245 + int(key[k])) } index >>= 27 index &= 16 - 1 return index }
hash表结构
将v存到hash表中的步骤:
- 通过HashCode计算v的HashCode值,从而确定存在在哪个hash链表下(0-15,共16个hash链).
- 将v追加的hash链表的尾部.
go实现hash表
main.go
package main import ( "./HMap" "fmt" ) func main() { //每个空间都存有一个链表头 HMap.InitBuckets() HMap.AddKeyValue("a","hello world") HMap.AddKeyValue("abc","hello China") fmt.Println(HMap.GetValueByKey("a")) fmt.Println(HMap.GetValueByKey("abc")) }
HMap.go
package HMap import "../LNodes" //实现hashmap原理 //创建长度为16的数组 var buckets = make([]*LNodes.Node,16) func InitBuckets() { for i:=0;i<16;i++{ buckets[i]= LNodes.CreateHead(LNodes.KValue{"head","node"}) } } //将任何长度的字符串,通过运算,散列成0-15整数 //通过hashCode散列出的0-15的数字的概率是相等的 func HashCode(key string) int { var index int = 0 index = int(key[0]) for k := 0; k < len(key); k++ { index *= (1103515245 + int(key[k])) } index >>= 27 index &= 16 - 1 return index } //先hashmap中保存键值对 func AddKeyValue(key string ,value string ) { //计算key散列的结果,数组下标 var nIndex = HashCode(key) //在数组中获得头结点 var headNode = buckets[nIndex] //获得当前链表的尾节点 var tailNode = LNodes.TailNode(headNode) //添加节点 LNodes.AddNode(LNodes.KValue{key,value},tailNode) } //获取键值对 func GetValueByKey(key string ) string { var nIndex = HashCode(key) var headNode = buckets[nIndex] //通过链表查询对应key 的value var value = LNodes.FindValueByKey(key,headNode) return value }
LNode.go
package LNodes import "fmt" type KValue struct { Key string Value string } type Node struct { Data KValue NextNode *Node } //创建头结点 func CreateHead(data KValue ) *Node { var head = &Node{data,nil } return head } //添加节点 func AddNode(data KValue ,node *Node) *Node { var newNode = &Node{data ,nil} node.NextNode = newNode return newNode } //节点的遍历 func ShowNodes(head *Node) { node:= head for { if node.NextNode !=nil { fmt.Println(node.Data) node = node.NextNode }else { break } } fmt.Println(node.Data) } //获得当前链表的尾节点 func TailNode(head *Node) *Node { node :=head for { if node.NextNode == nil { return node } else { node = node.NextNode } } } func FindValueByKey(key string ,head *Node) string { node :=head for { if node.NextNode!=nil { if node.Data.Key == key { return node.Data.Value } node = node.NextNode }else { break } } return node.Data.Value }
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- 密码学初学者可以理解的密码学库
- 密码学幼稚园 | 密码朋克的社会实验(二)
- 简述密码学应用四阶段:对称加密、公钥加密、区块链与高等密码学
- 密码密钥傻傻分不清?认识密码学中的最高机密
- 密码学幼稚园丨密码朋克的社会实验(二)
- 应用密码学概要(一)
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。