散列算法实现Go语言Map函数

概述

Hash一般翻译做“散列”,也有直接音译为哈希的,就是把任意长度的输入(又叫做预映射),通过散列算法,变换成固定长度的输出,该输出就是散列值,这种转化是一种压缩映射,也就是散列值的空间通常远小于输入值的空间,不同的输入可能会散列成相同的输出,二不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要函数。

哈希算法

Hash主要用于信息安全领域中的加密算法,它把一些长度不同的信息转化成杂乱的128位的编码,这些编码值叫做HASH值,也可以说,hash就是找到一种数据内容和数据存放地址之间的映射关系。具体哈希算法可以参考哈希算法总结这篇文章。
散列表是一种用于以常熟平均时间执行插入、删除、查找的算法。

散列函数

散列表每个关键字被影射到0~ArrSize这个范围内(本文选取的数组长度为16的数组,取的关键字为1103515245),这个映射叫做散列函数。上面的两个函数取值保证了,关键字被影射到0-15下标数组的概率一样。

Map实现原理

创建一个容量为16的链表数组,依据上面散列函数的原理,将Key值等概率的转换成0-16之间的下标值。然后根据下标值,将key和value插入到对应的下标数组中的链表上。 原理如下图:





代码实现

结构体作为数据域的类型


type DM struct {
	K string
	V string
}

声明全局变量,保存头结点

var head *Node
var curr *Node

声明节点类型

type Node struct {
	//数据域
	Data DM
	//地址域
	NextNode *Node
}

创建头结点

func CreateHeadNode(k string, v string) *Node {
	var node *Node = new(Node)
	//设置数据域结构体中的键值对
	node.Data.K = k
	node.Data.V = v
	//设置地址域
	node.NextNode = nil
	//保存头结点
	head = node
	curr = node

	return node

}

在指定的节点(curr)后边添加新节点

func AddNode(k string, v string, curr *Node) *Node {
	var newNode *Node = new(Node)
	//设置新节点中的数据域
	newNode.Data.K = k
	newNode.Data.V = v

	//设置地址域
	newNode.NextNode = nil
	//挂接节点
	curr.NextNode = newNode
	curr = newNode
	//返回值
	return newNode
}

在指定的节点后边遍历链表

func ShowNodes(n *Node) {
	var node = n
	for {
		if node.NextNode == nil {
			fmt.Print(node.Data)
			break
		} else {
			fmt.Println(node.Data)
			node = node.NextNode
		}
	}

}

计算节点的个数


func NodeCnt() int {
	var cnt int = 1
	var node = head
	for {
		if node.NextNode == nil {
			break
		} else {
			node = node.NextNode
			cnt = cnt + 1
		}

	}
	return cnt
}

声明全局数组

var bultArr [16]*Node

给数组初始化

func CreateBulet() {

	var arr = [16]*Node{}
	for i := 0; i < 16; i++ {
	 // 为数组中每个元素都创建头节点
		arr[i] = CreateHeadNode("头节点", "头结点")

	}
	bultArr = arr

}

将key转换成数组下标的散列算法

此方法为固定的方法,科学家算的🤫🤭,即上面的散列函数

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
}

向数组中添加键值对

func AddKeyValue(k string, v string) {

	//计算建所对应的木桶下标
	var pos = HashCode(k)
	//获得木桶数组

	var head *Node = bultArr[pos]
	//向指定下标的头节点添加节点
	AddNode(k, v, head)

}

获取数据

func GetValueByKey(k string) string {
	var pos = HashCode(k)
	var head *Node = bultArr[pos]
	//通过头节点遍历链表
	
	//查找对应下标下的链表,判断在key与节点中的key一直时打印
	for {
		if head.Data.K == k {
			fmt.Println(head.Data.V)
			break
		} else {
			head = head.NextNode
			if head.NextNode == nil {

			}
		}
	}

	return ""
}

总结

哈希散列算法的数值指定数组长度也可以是32,64,但是对应的数字就不是1103515245了,有其他的数,感兴趣的可以去查询一下。


喜欢就star一下吧!👻👻👻

作者原创,转载请注明出处,如有错误描述,请评论纠正,谢谢大家!🐳🐳🐳

打赏一个呗

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码支持
扫码打赏,你说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦