hash表哈希游戏系统开发流程分析（Python框架）

哈希表的类型定义

系统部署+铭籽

typedef struct {
    RcdType *rcd;    //哈希表记录的地址指针 
    int size;    //哈希表的规模 
    int count;    //记录个数 
    int *tag;    //标志指针：1为有，0为空，-1为已删除 
    int (*hash)(KeyType key,int size) ;    //起映射作用的哈希函数指针 
    int (*collision)(int &hashValue,int size) ;    //处理冲突的函数指针 
}HashTable; 

哈希表的初始化

//哈希表的初始化
Status InitHash (HashTable &H,int size,int (*hash)(KeyType,int),int (*collision)(int &,int)) {
    //申请了size个连续的RcdType类型的存储空间
    H.rcd = (RcdType*)malloc(size*sizeof(RcdType));
    //申请了同样个数（size）的连续的整形的存储空间
    //方便后面一对一登记各点的记录状态
    //将地址赋值给指针H.tag
    H.tag = (int*)malloc(size*sizeof(int));
    //每次申请存储空间，习惯判断是否申请成功
    if (H.rcd==NULL||H.tag==NULL) {
        return OVERFLOW;
    }
    
    for (int i=0;i
        H.tag[i] = 0;    
        //数组初始化，很多时候我们都需要保持初始化的习惯
        //特别是刚定义变量/申请存储空间时
        //因为他们可能带有默认值影响结果
    }
    H.size = size;
    H.count = 0;
    H.hash = hash;
    H.collision = collision;    //处理冲突函数
    return OK;
}

冲突函数

//冲突函数
void collision(int & hashValue,int hashSize) {
//冲突函数可以根据实际问题具体设计
    hashValue = (hashValue+1)%hashSize;
} 

哈希表的查找

//哈希表的查找
Status SearchHash(HashTable H,KeyType key,int &p,int &c) {
    p = H.hash(key,H.size);        //求得哈希地址
    //如果地址p存在不等记录或者记录已经删除，则进入循环 
    while((1==H.tag[p]&&H.rcd[p].key!=key)||-1==H.tag) {
        H.collision(p,H.size);    //一开始存放的时候是通过冲突函数处理的，
        //现在查找也通过同样的方式查找，
        //就好像你将东西放在某个地方，你要查找的时候还是要按同样的路前去取出 
        c++;    //c代表层次，经过n次冲突函数，则c=n 
    }
     //存在相等记录 
    if(H.rcd[p].key==key&&1==H.tag[p]) {
        return OK;
    }
    else {    //不存在记录 
        return ERROR;
    }
} 

插入记录

//插入
int InsertHash(HashTable &H,RcdType e) {
    int c=0,j;
    //判断待插入记录是否已经存在，通过哈稀函数返回地址j，层次c(这两个参数属于引用形参，可双向传递) 
    if(OK == SearchHash(H,e.key,j,c)) {
        return -1;
    }
    else {    //待插入记录在哈希表中不存在，则执行插入操作 
        H.rcd[j] = e;
        H.tag[j] = 1;
        ++H.count;
        return c;
    }
} 

删除记录

//删除
Status DeleteHash (HashTable &H,KeyType key,RcdType &e) {
    int j,c;    //用于接收SearchHash函数中引用形参的返回值 
    if (ERROR == SearchHash(Hey,j,c)) {
        return ERROR;
    }
    else {
        e = H.rcd[j] ;
        H.tag[j] = -1 ;
        H.count--;
        return OK;
    }
}