45.Go语言·数据结构·哈希表

main.go

// Go语言·数据结构·哈希表
package main

import (
    "fmt"
)

var content string = `
————————————————Go语言·数据结构·哈希表————————————————————
一、哈希表
    
`

type Emp struct {
    Id   int
    Name string
    Next *Emp
}

func (this *Emp) EmpInfo() {
    fmt.Println()
    fmt.Printf("<No.%d, %s> \n", this.Id,this.Name)
}


// 定义一个EmpLink，不带表头，
// 第一个就存放数据
type EpmLink struct {
    Head *Emp
}

// 添加员工的方法
// 保证添加时候，是从小到大
func (this *EpmLink) Add(emp *Emp) {
    var pre *Emp = nil
    current := this.Head

    if current == nil {
        this.Head = emp
        return
    }
    
    for {
        if current != nil {
            // emp.id 和 current.id比较
            if current.Id > emp.Id {
                // 找到位置：
                break
            }
            // pre保持在cur前面
            pre = current
            current = current.Next
        }else{
            break
        }
    }
    // 利用pre进行添加
    // 顺序：pre-->emp--->current
    pre.Next = emp
    emp.Next = current
}

// 显示
func (this *EpmLink) ShowLink(num int) {
    fmt.Printf("链表<NO.%d>：",num)
    current := this.Head
    for {
        if current != nil {
            fmt.Printf("[No.%.4d %s]-->",current.Id,current.Name)
            current = current.Next
        }else{
            break
        }
    }
    fmt.Println()
}

// 根据id查找信息，没有就返回 nil
func (this *EpmLink) FindById(id int) *Emp {
    curr := this.Head
    for {
        if curr != nil  && curr.Id == id {
            return curr
        }else if curr == nil{
            break
        }
        curr = curr.Next
    }
    return  nil
}



// 定义一个hashTable,含有一个链表数组
type HashTable struct {
    LinkArr [7]EpmLink
}

// 编写一个散列的方法
// 对应的链表的下标
func (this *HashTable) HashSet(id int) int {
    return id % len(this.LinkArr)
}

// 给hashTable  添加的方法
func (this *HashTable) Hset(emp *Emp) {
    // 使用散列函数，确定将该雇员，添加到那个链表
    linkNo := this.HashSet(emp.Id)
    // 对应的链表添加
    this.LinkArr[linkNo].Add(emp)
}

// 显示
func (this *HashTable) ShGetall() {
    for i := 0; i <len(this.LinkArr); i++ {
        this.LinkArr[i] .ShowLink(i)
    }
}

// 根据id查找
func (this *HashTable) FindById(id int) *Emp {
    linkNo := this.HashSet(id)
    return this.LinkArr[linkNo].FindById(id)
}



func main() {
    htable := &HashTable{}
    emp1 := &Emp{Id:7,Name:"Faker"}
    htable.Hset(emp1)
    emp2 := &Emp{Id:14,Name:"Uzi"}
    htable.Hset(emp2)
    emp3 := &Emp{Id:989,Name:"Mata"}
    htable.Hset(emp3)
    emp4 := &Emp{Id:36,Name:"Mata"}
    htable.Hset(emp4)

    htable.ShGetall()
    my := htable.FindById(36)
    if my != nil{
        my.EmpInfo()
    }
}