首页 > 其他分享 >Go 哈希

Go 哈希

时间:2022-09-18 21:01:10浏览次数:107  
标签:cur fmt 雇员 链表 emp 哈希 Go id

一 哈希表的基本介绍

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

 

 

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

应用实例 :

​ google 公司的一个上机题:
​ 有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,住址…),当输入该员工
的 id 时,要求查找到该员工的 所有信息.

要求:

不使用数据库,尽量节省内存,速度越快越好=>哈希表(散列)
添加时,保证按照雇员的 id 从低到高插入
思路分析:

使用链表来实现哈希表, 该链表不带表头(即: 链表的第一个结点就存放雇员信息)
思路分析并画出示意图

 

 

package main

import (
	"fmt"
	"os"
)

//定义 emp
type Emp struct {
	Id   int
	Name string
	Next *Emp
}

// 编写一个方法显示雇员信息
func (e *Emp) ShowMe() {
	fmt.Printf("链表%d 找到该雇员 %d\n", e.Id%7, e.Id)
}

//定义 EmpLink
//我们这里的 EmpLink 不带表头,即第一个结点就存放雇员
type EmpLink struct {
	Head *Emp
}

//添加员工的方法, 保证添加时,编号从小到大
func (e *EmpLink) Insert(emp *Emp) {
	cur := e.Head      // 这是辅助指针
	var pre *Emp = nil // 这是一个辅助指针 pre 在 cur 前面
	//如果当前的 EmpLink 就是一个空链表
	if cur == nil {
		e.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
		}
	}
	//退出时,将 emp 添加到链表最后
	pre.Next = emp
	emp.Next = cur
}

//显示链表的信息
func (e *EmpLink) ShowLink(no int) {
	if e.Head == nil {
		fmt.Printf("链表%d 为空\n", no)
		return
	}
	//变量当前的链表,并显示数据
	cur := e.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 (e *EmpLink) FindById(id int) *Emp {
	cur := e.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 (h *HashTable) Insert(emp *Emp) {
	//使用散列函数,确定将该雇员添加到哪个链表
	linkNo := h.HashFun(emp.Id)
	//使用对应的链表添加
	h.LinkArr[linkNo].Insert(emp)
}

//编写方法,显示 hashtable 的所有雇员
func (h *HashTable) ShowAll() {
	for i := 0; i < len(h.LinkArr); i++ {
		h.LinkArr[i].ShowLink(i)
	}
}

//编写一个散列方法
func (h *HashTable) HashFun(id int) int {
	return id % 7 //得到一个值,就是对于的链表的下标
}

// 编写一个方法完成查找
func (h *HashTable) FindById(id int) *Emp {
	//使用散列函数,确定将该雇员在哪个链表
	linkNo := h.HashFun(id)
	return h.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("输入错误")
		}
	}
}

  

标签:cur,fmt,雇员,链表,emp,哈希,Go,id
From: https://www.cnblogs.com/wuchangblog/p/16705758.html

相关文章

  • goo-cqhttp帮助文档
    目录帮助文档一、简介二、创建帮助文档三、最后帮助文档一、简介在经历这个专栏的学习之后,我想go-cqhttp+flask的学习也该告一段落了,因为有部分功能,如定时发送功能,......
  • GO 栈
    栈的介绍有些程序员也把栈称为堆栈,即栈和堆栈是同一个概念栈的英文为(stack)栈是一个先入后出(FILO-FirstInLastOut)的有序列表。栈(stack)是限制线性表中元素的插入和......
  • leetcode 127 -- 哈希表
    题目描述217手写哈希表classSolution{public:#defineDEFAULT_LEN16#defineDEFAULT_FACTOR0.75fconstfloatfactor=DEFAULT_FACTOR;typed......
  • buf connect-go 试用
    golang包含一个grpc-web可以让浏览器运行grpc,但是是需要一些中间件工具的,connect-go简化了处理,可以基于post通过http协议就可以试用grpc了包含的特性基于http......
  • Go 双向链表
    1.双向链表的应用实例使用带head头的双向链表实现——王者容易英雄排行榜单向链表的缺点分析:1)单向链表,查找的方向只能是一个方向,而双向链表可以向前或者向后查找2)单向......
  • Go 单向环形链表
    单向环形链表单向环形链表是一种特殊的单向链表。单向链表最后一个节点的Next指针指向空。而单向环形链表最后一个节点的Next指针指向头节点。如图所示: packa......
  • Go 学习(一) : Get started with Go
    安装gohttps://go.dev/doc/install安装以后命令行执行goversion然后随便创建一个文件,比如hello.gopackagemainimport"fmt"funcmain(){ fmt.Printl......
  • Go 单链表2
    插入节点1)、头插法packagemainimport"fmt"typeNodestruct{dataintnext*Node}funcShownode(p*Node){//遍历forp!=nil{fm......
  • 使用pymongo管理MongoDB
    基于pymongo的MongoDB系列操作,会不定时补充更新frompymongoimportMongoClientimportpymongoimportdatetime##连接本地MongoDBclient=MongoClient("mongodb:......
  • golang air 热部署
    1、安装在这里就介绍大众使用的两个版本MacOS和Windows;(建议使用第一种)//1.16可以同时使用这两种方法goget-ugithub.com/cosmtrek/air//1.16......