Hash（散列函数）

简单说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

• 正向快速：给定明文，快速计算出hash值。
• 逆向困难：给定hash值，很难逆推出明文。
• 输入敏感：原始输入信息修改一点消息，产生的hash值看起来应该都有很大不同。
• 冲突避免：很难找到2段不同的明文，使他们的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 mainimport (    "./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 HMapimport "../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 LNodesimport "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}