img

微信:zhq496927203

´

sweetsmelon

sweetsmelon博客

链乎问答社区
链乎公众号

go语言实现一个hash表

| 阅读：次



假设我现在有一条链表，链表中每个节点上都存储一个key-value的键值对，那么我就可以通过遍历链表，找到一个给定的key值对应的value，链表的结构是这样的


//声明节点类型
type Node struct {
	//数据域
	Data DM
	//地址域
	NextNode *Node
}
//用结构体做数据域的类型
type DM struct {
	K string
	V string
}

上面的代码将key-value封装为一个结构体DM，节点Node数据域存储当前的key-value键值对，地址域存储下一个节点的地址

假设现在有一个链表，长度为10，第8个节点上的Data.K = “name” Data.V = “sweet”，那么如果要查找“name”对应的值“sweet”,就需要遍历这个链表8次，当数据量很大时，这样查找就会很费时，为了提高效率，就有了hash表

一、hash表

1、定义

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

hash表

意思就是，有一个长度为16的数组（散列表）,这个数组中的每个元素都是一个链表，即这个数组有16个链表，当有一个新的节点插入时，这个节点的key值通过一个函数算出自己应该存放在数组中的哪一条链上，这个函数叫做 散列函数

2、怎么将一个key字符串转成一个[0~15]的数字

散列函数

Hash函数应用的主要对象是数组（比如，字符串），而其目标一般是一个int类型。

//将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
}

上面的代码就是一个hash函数，通过这个函数可以返回一个[0~15]的整数

  • 1103515245称为散列因子,在这个算法中，这个值是确定的，不能更改

  • 这个hash函数只试用于长度为16的hash表

  • 长度为16的hash算法并不是只有这一种

下面介绍一下hash函数分类，与本文关系不大

一般的说，Hash函数可以简单的划分为如下几类：

  1. 加法Hash；
  2. 位运算Hash；
  3. 乘法Hash；
  4. 除法Hash；
  5. 查表Hash；
  6. 混合Hash； 下面详细的介绍以上各种方式在实际中的运用。 （1） 加法Hash

所谓的加法Hash就是把输入元素一个一个的加起来构成最后的结果。标准的加法Hash的构造如下:

static int additiveHash(String key, int prime)
 {
 int hash, i;
  for (hash = key.length(), i = 0; i <key.length(); i++)
   hash += key.charAt(i);
  return (hash % prime);
  }

这里的prime是任意的质数，看得出，结果的值域为[0,prime-1]。

（2） 位运算Hash

这类型Hash函数通过利用各种位运算（常见的是移位和异或）来充分的混合输入元素。比如，标准的旋转Hash的构造如下：

static int rotatingHash(String key, int prime)
 {
   int hash, i;
   for (hash=key.length(), i=0; i<key.length(); ++i)
     hash = (hash<<4)^(hash>>28)^key.charAt(i);
   return (hash % prime);
 }

先移位，然后再进行各种位运算是这种类型Hash函数的主要特点。比如，以上的那段计算hash的代码还可以有如下几种变形：

  1. hash = (hash«5)^(hash»27)^key.charAt(i);
  2. hash += key.charAt(i); hash += (hash « 10); hash ^= (hash » 6);
  3. if((i&1) == 0) { hash ^= (hash«7) ^ key.charAt(i) ^ (hash»3); } else { hash ^= ~((hash«11) ^ key.charAt(i) ^ (hash »5)); }
  4. hash += (hash«5) + key.charAt(i);
  5. hash = key.charAt(i) + (hash«6) + (hash»16) – hash;
  6. hash ^= ((hash«5) + key.charAt(i) + (hash»2));

(3) 乘法Hash

这种类型的Hash函数利用了乘法的不相关性（乘法的这种性质，最有名的莫过于平方取头尾的随机数生成算法，虽然这种算法效果并不好）。比如，

 static int bernstein(String key)
 {
   int hash = 0;
   int i;
   for (i=0; i<key.length(); ++i) hash = 33*hash + key.charAt(i);
   return hash;
 }

jdk5.0里面的String类的hashCode()方法也使用乘法Hash。不过，它使用的乘数是31。推荐的乘数还有：131, 1313, 13131, 131313等等。

使用这种方式的著名Hash函数还有： // 32位FNV算法 int M_SHIFT = 0; public int FNVHash(byte[] data) { int hash = (int)2166136261L; for(byte b : data) hash = (hash * 16777619) ^ b; if (M_SHIFT == 0) return hash; return (hash ^ (hash » M_SHIFT)) & M_MASK; }

以及改进的FNV算法： public static int FNVHash1(String data) { final int p = 16777619; int hash = (int)2166136261L; for(int i=0;i<data.length();i++) hash = (hash ^ data.charAt(i)) * p; hash += hash « 13; hash ^= hash » 7; hash += hash « 3; hash ^= hash » 17; hash += hash « 5; return hash; }

除了乘以一个固定的数，常见的还有乘以一个不断改变的数，比如： static int RSHash(String str) { int b = 378551; int a = 63689; int hash = 0;

   for(int i = 0; i < str.length(); i++)
   {
      hash = hash * a + str.charAt(i);
      a    = a * b;
   }
   return (hash & 0x7FFFFFFF); }

虽然Adler32算法的应用没有CRC32广泛，不过，它可能是乘法Hash里面最有名的一个了。关于它的介绍，大家可以去看RFC 1950规范。 (4) 除法Hash

除法和乘法一样，同样具有表面上看起来的不相关性。不过，因为除法太慢，这种方式几乎找不到真正的应用。需要注意的是，我们在前面看到的hash的 结果除以一个prime的目的只是为了保证结果的范围。如果你不需要它限制一个范围的话，可以使用如下的代码替代”hash%prime”： hash = hash ^ (hash»10) ^ (hash»20)。 (5) 查表Hash

查表Hash最有名的例子莫过于CRC系列算法。虽然CRC系列算法本身并不是查表，但是，查表是它的一种最快的实现方式。查表Hash中有名的例子有：Universal Hashing和Zobrist Hashing。他们的表格都是随机生成的。 (6) 混合Hash

混合Hash算法利用了以上各种方式。各种常见的Hash算法，比如MD5、Tiger都属于这个范围。它们一般很少在面向查找的Hash函数里面使用。 (7) 对Hash算法的评价

http://www.burtleburtle.net/bob/hash/doobs.html 这个页面提供了对几种流行Hash算法的评价。我们对Hash函数的建议如下：

  1. 字符串的Hash。最简单可以使用基本的乘法Hash，当乘数为33时，对于英文单词有很好的散列效果（小于6个的小写形式可以保证没有冲突）。复杂一点可以使用FNV算法（及其改进形式），它对于比较长的字符串，在速度和效果上都不错。

  2. 长数组的Hash。可以使用http://burtleburtle.net/bob/c/lookup3.c这种算法，它一次运算多个字节，速度还算不错。 (8) 后记

以上介绍了一番实际应用中的用于查找的Hash算法。Hash算法除了应用于这个方面以外，另外一个著名的应用是巨型字符串匹配（这时的 Hash算法叫做：rolling hash，因为它必须可以滚动的计算）。设计一个真正好的Hash算法并不是一件容易的事情。做为应用来说，选择一个适合的算法是最重要的。

（9） 数组hash

inline int hashcode(const int *v) { int s = 0; for(int i=0; i<k; i++) s=((s«2)+(v[i]»4))^(v[i]«10); s = s % M; s = s < 0 ? s + M : s; return s; }

注：虽说以上的hash能极大程度地避免冲突，但是冲突是在所难免的。所以无论用哪种hash函数，都要加上处理冲突的方法。

二、实现hash表

hash表是一个有多条链表的数组，那么先要实现一条链表

1、实现一条链表

  • 创建节点结构体
//声明节点类型
type Node struct {
	//数据域
	Data DM
	//地址域
	NextNode *Node
	//头结点的当前节点
	curr *Node

}
//用结构体做数据域的类型
type DM struct {
	K string
	V string
}

curr节点，也可以叫lastNode,即链表的最后一个节点，因为当我们插入数据时，都是插入到链表的最后

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

func AddNode(k,v string,currHead *Node) *Node {
	fmt.Println("addNode",currHead)
	var newNode *Node = new(Node)
	newNode.Data.K = k
	newNode.Data.V = v
	//设置地址域
	newNode.NextNode = nil
	//挂接节点
	currHead.curr.NextNode = newNode
	fmt.Printf("newNode:%p\n",newNode)
	//链表的curr节点始终指向这个链表的最后一个节点
	currHead.curr = newNode
	return currHead
}

到此链表就完成了，接下来创建16条链表，插入到数组中即创建一个hash表

var buletArr  [16]*linknodes.Node

//给数组初始化
func CreateBulet()  {
	var arr  [16]*linknodes.Node
	for i := 0; i < 16; i++ {
		arr[i] = linknodes.CreateHeadNode("头key"+strconv.Itoa(i),"头结点")
	}
	buletArr = arr
}

创建16条链，每条链的头节点的Data.k和Data.v都是定义好的，头结点的位置，并没有通过hash算法计算Data.k的值存到对应位置，所以如果查找“头key0”可能找不到对应的值，因为，查找”头key0”和“头key0”可能不在一条链上。

  • 向hash表中插入数据
func AddKeyValue(k,v string )  {
	//计算键所对应的木桶下标
	var pos = HashCode(k)
	//获得木桶数组
	//var arr = buletArr
	var head *linknodes.Node = buletArr[pos]
	//向指定下标的头结点，添加节点
	linknodes.AddNode(k,v,head)
}

通过HashCode方法，计算出k值对应的数组下标pos，从数组中取出pos对应的链表的头结点head，最后将数据插入到这条链上

  • 查询数据
//获取数据
func GetValueByKey(k string)string  {
	var pos = HashCode(k)
	var head * linknodes.Node = buletArr[pos]
	fmt.Println(buletArr)
	//通过头结点遍历链表
	//linknodes.ShowNodes(head)
	//查找对应下标下的链表,只有判断在key与节点中的key一致时打印
	var n = head
	for  {
		//如果 节点为nil说明已经到链表最后，也就是链表中不存在这个值
		if n == nil {
			fmt.Println("没有对应的值")
			break
		}
		if n.Data.K == k {
			fmt.Println(n.Data.V)
			break
		}else {
			n = n.NextNode
		}
	}
	return ""
}
  • hash函数
//将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
}

将key值转[0~15]的整数，即数组下标

到此hash表就完成了

项目源码

写在最后

这个hash表只做了一级hash，效率可以提高16倍，还可以对每条链表做二级，三级hash，即把一个子个节点作为一个头结点从而衍生出另一个长度为16的hash表，效率可以更高

打赏一个呗

取消

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

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

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