一 哈希表的基本介绍
散列表(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