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

本文主要采用：

构造方法：除留余数法： 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 nullValue = keyType(-65535)  //无效的数据
 
type hashData struct {
	key   keyType   //key值
	value valueType //value值
	//count int       //探查次数
}
 
var hashTable [maxSize]hashData //定义哈希表，大小为maxSize，类型为：hashData
//初始化哈希表
func initHashTable()  {
	for i:=0;i<len(hashTable);i++{
		dataNode:=hashData{nullValue,0,}
		hashTable[i]=dataNode
	}
}
//向哈希表添加数据元素
func insertHashTable(ht *[maxSize]hashData, key keyType, value valueType) bool{
	count := 0 //添加时 查找次数
	addr := int(key) % p
	//线性探测发： f(key)=(  f(key)+d)%m (d=1,d=2,d=3...)
	d := 0
	for count < maxSize {
		addr := (addr + d) % p
		if ht[addr].key ==nullValue {
			dataNode := hashData{key, value, }
			ht[addr] = dataNode
			return true
		}
		d++
		count++
	}
	return false
}
//查找数据
func searchHashTable( ht *[maxSize]hashData,key keyType) (positon int) {
	//addr:=int(key)%p
	positon=-1 //没有找到，返回值为：-1
	for index,data:=range ht{
		if data.key==key {
			positon=index
			return  //返回对应于数组的下标
		}
	}
	return
}
//删除数据
func deleteHashTable(ht *[maxSize]hashData,key keyType) bool {
	for index,data:=range ht{
		if data.key==key {
			/*
			特别注意;这种方法不能更改数据
			data.key=nullValue //重置key
			data.value=0  //清空数据
			*/
			dataNode:=hashData{nullValue,0}
			ht[index]=dataNode
			return true
		}
	}
	return false
 
}
func main() {
	//初始化哈希表
	initHashTable()
	//向哈希表中添加10个数据
	for i:=0;i<10;i++{
		insertHashTable(&hashTable,keyType(i),valueType(i*100))
	}
	fmt.Println(hashTable) //打印，是否添加成功
 
	//查找
	index:=searchHashTable(&hashTable,keyType(3))
	if index==-1 {
		fmt.Println("没有查询到对应的数据")
	}else {
		value:=hashTable[index].value
		fmt.Printf("key：%d对应的value：%d\n",index,value)
	}
 
	//删除数据元素
	deleteState:=deleteHashTable(&hashTable,keyType(3))
	if deleteState {
		fmt.Println("找到对应的元素，删除成功！")
	}else {
		fmt.Println("没有找到元素，删除失败！")
	}
 
	//再次查找，看是否真正删除
	index1:=searchHashTable(&hashTable,keyType(3))
	if index1==-1 {
		fmt.Println("没有查询到对应的数据")
	}else {
		value:=hashTable[index1].value
		fmt.Printf("key：%d对应的value：%d",index1,value)
	}
	//fmt.Println(hashTable)
}