数据结构--散列表（哈希表）2

本文主要采用：

构造方法：除留余数法： f(key)=key%p (P<=m m:散列表的长度)

处理散列冲突方法：链地址法（单链表）

代码实例：

package main
 
import "fmt"
 
/*
 除留余数发定址 线性探测发解决冲突
*/
type keyType int   //key值的类型
type valueType int //value值的类型
const maxSize = 12 //hastable的最大长度
//除留余数发：  f(key)=key%p (P<=m   m:散列表的长度)
var p = 11
var nullKey = keyType(-65535)
var nullValue = valueType(-65535) //无效的数据
 
type hashData struct {
	key   keyType   //key值
	value valueType //value值
	next  *hashData
}
 
var hashTable [maxSize]hashData //定义哈希表，大小为maxSize，类型为：hashData
//初始化哈希表
func initHashTable() {
	for i := 0; i < len(hashTable); i++ {
		// 头结点
		p := new(hashData)
		p.key = nullKey     //空值
		p.value = nullValue //空值
		p.next = nil
		dataNode := hashData{keyType(nullKey), valueType(nullValue), p}
		hashTable[i] = dataNode
	}
}
 
//向哈希表添加数据元素
func insertHashTable(ht *[maxSize]hashData, key keyType, value valueType) bool {
	//先查找，如果key值已经存在，则替换成key新对应的value
	data:=searchHashTable(ht,key)
	if data!=nil{
		//已经存在
		data.value=value
		return true
	}
	addr := int(key) % p
	//开辟空间 新建节点
	q := new(hashData)
	q.key = key     //赋 key值
	q.value = value //赋value值
	r := ht[addr].next
	//找到最末尾元素
	for r.next != nil {
		r = r.next
	}
	q.next = r.next
	r.next = q
	return true
}
 
//查找数据
func searchHashTable(ht *[maxSize]hashData, key keyType) (data *hashData) {
	//按照添加的位置 找对应的数据（链表），而不是对数组遍历
	addr := int(key) % p
	//fmt.Println("------------",addr)
	data = nil
	q := ht[addr].next
	for q != nil {
		if q.key == key {
			return q //如果找个，返回对应的节点（指针指向此节点）
		}
		q = q.next //移动到下一个位置继续
	}
	return
}
 
//删除数据
func deleteHashTable(ht *[maxSize]hashData, key keyType) bool {
	addr := int(key) % p
	q := ht[addr].next
	r := q.next
	for r != nil {
		//删除节点
		if r.key == key {
			q.next = r.next
			return true
		}
		q = r
		r = q.next
	}
	return false
}
func main() {
	//初始化哈希表
	initHashTable()
	//添加数据
	// 元素0对应的数据
	insertHashTable(&hashTable, 0, 48)
	m := searchHashTable(&hashTable, 0)
	if m != nil {
		fmt.Printf("【%d】：%d\n", m.key, m.value)
	} else {
		fmt.Println("没有查找到数据！")
	}
 
	//添加key已经存在的数据
	insertHashTable(&hashTable,0,666)
	m = searchHashTable(&hashTable, 0)
	if m != nil {
		fmt.Printf("【%d】：%d\n", m.key, m.value)
	} else {
		fmt.Println("没有查找到数据！")
	}
 
	//删除数据元素
	deleteHashTable(&hashTable, 0)
 
	//删除之后 再次查找
	m = searchHashTable(&hashTable, 0)
	if m != nil {
		fmt.Printf("【%d】：%d\n", m.key, m.value)
	} else {
		fmt.Println("没有查找到数据！")
	}
 
}