go 哈希表——map的简单实现

2019-08-05 本文已影响0人卖毛玉的小贩

哈希表

什么是哈希表？
- 散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
- 给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。
那什么是哈希？
- Hash，一般是一个整数，通过某种算法，可以把一个字符串"压缩" 成一个整数，这个数称为Hash，常见的MD5,SHA1等
从这里可以看出来，我们常用的map或者说dictionary都属于哈希表里的关系
那么我们就来简单的实现下，简单的map吧

拉链法（链地址法）

在讲解步骤之前，首先说下为什么要用拉链法，而不是其他
- 首先拉链法的学习只需要数组和链表的知识点即可
- 其次，拉链法很简单的就解决了哈希表冲突
其特点：
- 数组的特点是：寻址容易，插入和删除困难。
- 而链表的特点是：寻址困难，插入和删除容易。
- 所以，哈希里拉链法就是寻址容易，插入删除简单

实现步骤

//1.首先定义结构体
type MpNode struct {
 Data Dict    // 定义数据  数据为存放k v 的结构体
 Next *MpNode // 下个节点
}
type Dict struct {
 Key   string
 Value interface{}
}

//2 初始化
//初始化链表的头节点
func newNodeHead() *MpNode {
 node := new(MpNode)
 node.Data.Key = "头key"
 node.Data.Value = "头value"
 node.Next = nil
 return node
}

//链方法
//3 封装结构体对象方法
// 封装key value 存放方法
func (node *MpNode) data(k string, v interface{}) *MpNode {
 if node == nil {
     node = newNodeHead()
 }
 node.Data.Key = k
 node.Data.Value = v
 return node
}

//4  向该链空节点创建新数据
func (node *MpNode) add(k string, v interface{}) {
 // 首先判断k是否是该链已有的key  因为根据哈希算法简化后  同样的字符串会在同样的链里存放
 if node.getKey(k) != nil {
     return
 }
 //遍历到尾节点
 for node.Next != nil {
     node = node.Next
 }
 // 创建新的尾节点
 node.Next = node.Next.data(k, v)
}

到这里我们已经初步实现了单链里存储key，value值

//5 测试下添加数据是否有问题
func MpDemo() {
  node := newNodeHead()
  node.add("1", "2")
  node.add("2", 3)
  node.Log()//看下面
  fmt.Println(node.Length())
}

//6 发现这样打印看不太方便 于是写个遍历值
func (node *MpNode) Log() {
  if node.Next == nil {
      return
  }
  fmt.Println(node.Next.Data)
  node.Next.Log()
}

// 7计算链表长度 防止数据堆积 为后续优化做准备
func (node *MpNode) Length() int {
   if node == nil {
      return 0
   }
   i := 0
   for node.Next != nil {
      i++
      node = node.Next
   }
   return i
}

//8 开始创建数组链表  也就是哈希表
// 定义数组链表
var Arr [16]*MpNode

//9 初始化哈希表
func NewHash() {
   for i := 0; i < 16; i++ {
      Arr[i] = newNodeHead()
   }
}

//哈希表方法
//10 往表里存key值
func SetKey(k string, v interface{}) {
   // 存k先判断存哪里  这里才使用了散列算法计算
   num := hashNum(k)
   Arr[num].add(k, v)
}

==这里你会发现，欸，哈希算法怎么写？于是我找了个简单的，并且能手撕的算法==

//11 获取16以内的散列算法
func hashNum(key string) int {
   var index int = 0
   index = int(key[0])
   // 询价累积新的数值
   for k := 0; k < len(key); k++ {
      index *= (1103515245 + int(key[k]))
   }
   // 右位移2^27次方  这里可以位移任何数  只要别太大导致直接清空
   index >>= 27
   // 按位&  这里想要求32以内就 32-1即可   也就是说  index跟 1111 进行&  得到15以内的数  跟11111取余则得31以内的数
   index &= 16 - 1

   return index
}

//12 根据key取value
func (node *MpNode) getKey(k string) interface{} {
   if node.Next == nil {
      return nil
   }
   for node.Next != nil {
      if node.Next.Data.Key == k {
         return node.Next.Data.Value
      } else {
         node = node.Next
      }
   }
   return nil
}
//13 根据valve取key  后面发现如果要写这个 就要给每个数组都遍历一遍后  就暂且放弃 等后续优化
//func (node *MpNode) getValue(v interface{}) string {
//    if node.Next == nil {
//        return ""
//    }
//    for node.Next != nil {
//        if node.Next.Data.Value == v {
//            return node.Next.Data.Key
//        } else {
//            node = node.Next
//        }
//    }
//    return ""
//}

//14 取key值
func GetKey(k string) interface{} {
   num := hashNum(k)
   return Arr[num].getKey(k)
}

到目前为止，整个算法结构已经初步完成

运行这个map吧！

首先整个算法在考虑封装等各种因素，对外只包含3个方法
- NewHash 创建一个哈希表
- SetKey 存键值对
- GetKey 取键值对
附上全代码

package data

import "fmt"

//1.首先定义结构体
type MpNode struct {
   Data Dict    // 定义数据  数据为存放k v 的结构体
   Next *MpNode // 下个节点
}
type Dict struct {
   Key   string
   Value interface{}
}

//8 开始创建数组链表  也就是哈希表
// 定义数组链表
var Arr [16]*MpNode

//2 初始化
//初始化链表的头节点
func newNodeHead() *MpNode {
   node := new(MpNode)
   node.Data.Key = "头key"
   node.Data.Value = "头value"
   node.Next = nil
   return node
}

//9 初始化哈希表
func NewHash() {
   for i := 0; i < 16; i++ {
      Arr[i] = newNodeHead()
   }
}

//链方法
//3 封装结构体对象方法
// 封装key value 存放方法
func (node *MpNode) data(k string, v interface{}) *MpNode {
   if node == nil {
      node = newNodeHead()
   }
   node.Data.Key = k
   node.Data.Value = v
   return node
}

//12 根据key取value
func (node *MpNode) getKey(k string) interface{} {
   if node.Next == nil {
      return nil
   }
   for node.Next != nil {
      if node.Next.Data.Key == k {
         return node.Next.Data.Value
      } else {
         node = node.Next
      }
   }
   return nil
}

//13 根据valve取key  后面发现如果要写这个 就要给每个数组都遍历一遍后  就暂且放弃 等后续优化
//func (node *MpNode) getValue(v interface{}) string {
// if node.Next == nil {
//    return ""
// }
// for node.Next != nil {
//    if node.Next.Data.Value == v {
//       return node.Next.Data.Key
//    } else {
//       node = node.Next
//    }
// }
// return ""
//}

//4  向该链空节点创建新数据
func (node *MpNode) add(k string, v interface{}) {
   // 首先判断k是否是该链已有的key  因为根据哈希算法简化后  同样的字符串会在同样的链里存放
   if node.getKey(k) != nil {
      return
   }
   //遍历到尾节点
   for node.Next != nil {
      node = node.Next
   }
   // 创建新的尾节点
   node.Next = node.Next.data(k, v)
}

//6 发现这样打印看不太方便 于是写个遍历值
func (node *MpNode) Log() {
   if node.Next == nil {
      return
   }
   fmt.Println(node.Next.Data)
   node.Next.Log()
}

// 7计算链表长度 防止数据堆积 为后续优化做准备
func (node *MpNode) Length() int {
   if node == nil {
      return 0
   }
   i := 0
   for node.Next != nil {
      i++
      node = node.Next
   }
   return i
}

//哈希表方法
//10 往表里存key值
func SetKey(k string, v interface{}) {
   // 存k先判断存哪里  这里才使用了散列算法计算
   num := hashNum(k)
   Arr[num].add(k, v)
}
//14 取key值
func GetKey(k string) interface{} {
   num := hashNum(k)
   return Arr[num].getKey(k)
}

//11 获取16以内的散列算法
func hashNum(key string) int {
   var index int = 0
   index = int(key[0])
   // 询价累积新的数值
   for k := 0; k < len(key); k++ {
      index *= (1103515245 + int(key[k]))
   }
   // 右位移2^27次方  这里可以位移任何数  只要别太大导致直接清空
   index >>= 27
   // 按位&  这里想要求32以内就 32-1即可   也就是说  index跟 1111 进行&  得到15以内的数  跟11111取余则得31以内的数
   index &= 16 - 1

   return index
}

//5 测试下添加数据是否有问题
func MpDemo() {
   //node := newNodeHead()
   //node.add("1", "2")
   //node.add("2", 3)
   //node.Log()
   //fmt.Println(node.Length())
}

go 哈希表——map的简单实现

哈希表

拉链法（链地址法）

实现步骤

运行这个map吧！

猜你喜欢

热点阅读