go实现哈希表

末蓝、 2021-07-24 22:53 378阅读 0赞

# 一 点睛 #

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70][]

# 二 使用 hashtable 来实现一个雇员的管理系统 #

## 1 需求 ##

有一个公司，当有新的员工来报道时，要求将该员工的信息加入(id、性别、年龄、住址..)，当输入该员工的 id 时，要求查找到该员工的 所有信息。

要求：

a 不使用数据库，尽量节省内存，速度越快越好。

b 添加时，保证按照雇员的 id 从低到高插入

## 2 思路分析 ##

a 使用链表来实现哈希表, 该链表不带表头。即链表的第一个结点就存放雇员信息。

b 图解

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70 1][]

## 3 代码 ##

package main
    
    import (
       "fmt"
       "os"
    )
    
    // 定义员工结构体
    type Emp struct {
       Id   int
       Name string
       Next *Emp
    }
    
    // 显示员工信息
    func (this *Emp) ShowMe() {
       fmt.Printf("链表%d 找到该雇员 %d\n", this.Id%7, this.Id)
    }
    
    // EmpLink
    // 这里的 EmpLink 不带表头，即第一个结点就存放雇员
    type EmpLink struct {
       Head *Emp
    }
    
    // 1 添加员工的方法, 保证添加时，编号从小到大
    func (this *EmpLink) Insert(emp *Emp) {
       cur := this.Head   // 辅助指针
       var pre *Emp = nil // 辅助指针 pre 在 cur 前面
       // 如果当前的 EmpLink 就是一个空链表
       if cur == nil {
          this.Head = emp // 完成
          return
       }
       // 如果不是一个空链表,给 emp 找到对应的位置并插入
       // 让 cur 和 emp 比较，然后让 pre 保持在 cur 前面
       for {
          if cur != nil {
             // 比较
             if cur.Id > emp.Id {
                // 找到位置
                break
             }
             pre = cur // 保证同步
             cur = cur.Next
          } else {
             break
          }
       }
       pre.Next = emp
       emp.Next = cur
    }
    
    // 显示链表的信息
    func (this *EmpLink) ShowLink(no int) {
       if this.Head == nil {
          fmt.Printf("链表%d 为空\n", no)
          return
       }
       // 遍历当前的链表，并显示数据
       cur := this.Head // 辅助的指针
       for {
          if cur != nil {
             fmt.Printf("链表%d 雇员id=%d 名字=%s ->", no, cur.Id, cur.Name)
             cur = cur.Next
          } else {
             break
          }
       }
       fmt.Println() // 换行处理
    }
    
    // 根据 id 查找对应的雇员，如果没有就返回 nil
    func (this *EmpLink) FindById(id int) *Emp {
       cur := this.Head
       for {
          if cur != nil && cur.Id == id {
             return cur
          } else if cur == nil {
             break
          }
          cur = cur.Next
       }
       return nil
    }
    
    // hashtable ,含有一个链表数组
    type HashTable struct {
       LinkArr [7]EmpLink
    }
    
    // 给 HashTable 编写 Insert 雇员的方法.
    func (this *HashTable) Insert(emp *Emp) {
       // 使用散列函数，确定将该雇员添加到哪个链表
       linkNo := this.HashFun(emp.Id)
       // 使用对应的链表添加
       this.LinkArr[linkNo].Insert(emp)
    }
    
    
    // 显示 hashtable 的所有雇员
    func (this *HashTable) ShowAll() {
       for i := 0; i < len(this.LinkArr); i++ {
          this.LinkArr[i].ShowLink(i)
       }
    }
    
    // 编写一个散列方法
    func (this *HashTable) HashFun(id int) int {
       return id % 7 //得到一个值，就是对于的链表的下标
    }
    
    // 完成查找
    func (this *HashTable) FindById(id int) *Emp {
       // 使用散列函数，确定将该雇员应该在哪个链表
       linkNo := this.HashFun(id)
       return this.LinkArr[linkNo].FindById(id)
    }
    
    func main() {
       key := ""
       id := 0
       name := ""
       var hashtable HashTable
       for {
          fmt.Println("===============雇员系统菜单============")
          fmt.Println("input 表示添加雇员")
          fmt.Println("show  表示显示雇员")
          fmt.Println("find  表示查找雇员")
          fmt.Println("exit  表示退出系统")
          fmt.Println("请输入你的选择")
          fmt.Scanln(&key)
          switch key {
          case "input":
             fmt.Println("输入雇员id")
             fmt.Scanln(&id)
             fmt.Println("输入雇员name")
             fmt.Scanln(&name)
             emp := &Emp{
                Id:   id,
                Name: name,
             }
             hashtable.Insert(emp)
          case "show":
             hashtable.ShowAll()
          case "find":
             fmt.Println("请输入id号:")
             fmt.Scanln(&id)
             emp := hashtable.FindById(id)
             if emp == nil {
                fmt.Printf("id=%d 的雇员不存在\n", id)
             } else {
                //编写一个方法，显示雇员信息
                emp.ShowMe()
             }
          case "exit":
             os.Exit(0)
          default:
             fmt.Println("输入错误")
          }
       }
    }

## 4 测试 ##

> ===============雇员系统菜单============
> 
> input 表示添加雇员
> 
> show  表示显示雇员
> 
> find  表示查找雇员
> 
> exit  表示退出系统
> 
> 请输入你的选择
> 
> input
> 
> 输入雇员id
> 
> 1
> 
> 输入雇员name
> 
> cakin1
> 
> ===============雇员系统菜单============
> 
> input 表示添加雇员
> 
> show  表示显示雇员
> 
> find  表示查找雇员
> 
> exit  表示退出系统
> 
> 请输入你的选择
> 
> input
> 
> 输入雇员id
> 
> 2
> 
> 输入雇员name
> 
> cakin2
> 
> ===============雇员系统菜单============
> 
> input 表示添加雇员
> 
> show  表示显示雇员
> 
> find  表示查找雇员
> 
> exit  表示退出系统
> 
> 请输入你的选择
> 
> show
> 
> 链表0 为空
> 
> 链表1 雇员id=1 名字=cakin1 ->
> 
> 链表2 雇员id=2 名字=cakin2 ->
> 
> 链表3 为空
> 
> 链表4 为空
> 
> 链表5 为空
> 
> 链表6 为空
> 
> ===============雇员系统菜单============
> 
> input 表示添加雇员
> 
> show  表示显示雇员
> 
> find  表示查找雇员
> 
> exit  表示退出系统
> 
> 请输入你的选择

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70]: /images/20210724/877422656a584e728589b7131ce4279d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70 1]: /images/20210724/fc3adf9b4d7345b7b6f0a6682f9400b8.png