HashTable

理想的情况，希望不经过任何比较，一次存取便能得到所查记录，在记录存储位置和它的关键字之间建立一个确定的对应关系f,对于关系f称为哈希函数

在查找时，根据这个对应关系f找到给定值K 的像

哈希表

#define NIL -1
#define m 13
typedef int KeyType;struct ElemType
{keyType key;//关键码void *ptr;//value
};typedef struct
{ElemType data[m];int cursize;
}HashTable;void Init_HashTable(HashTable* pt)
{assert(pt!=nullptr);pt->cursize = 0;for(int i = 0;i<m;++i){pt->data[i].key = NIL;pt->data[i].prt = nullptr;}
}
int Inc(int i)
{return i;//线性探测//return i*i;//平方探测
}
int Hash_Inc(KeyType kx,int i)
{return (Hash(kx)+Inc(i)) % m;
}
int Hash(KeyType kx)
{return kx % m;//m = 13;
}
bool Insert_Item(HashTable* pt,ElemType item)
{assert(pt!=nullptr);for(int i = 0;i<m;++i){int index = Hash_Inc(item.key,i);//用关键码找下标if(pt->data[i].key == NIL){pt->data[index] = item;pt->cursize += 1;return true;}}return false;
}
void *FindValue(HashTable *pt,KeyType kx)
{assert(pt != nullptr);for(int i = 0;i<m;++i){int pos = Hash_Inc(kx,i);if(pt->data[pos].key == kx){return pt->data[pos].ptr;}if(pt->data[pos].key == NIL){return nullptr;}}return nullptr;
}
int main()
{HashTable ht;Init_HashTable(&ht);int ar[] = {12,23,25,8,19,29};int n = sizeof(ar)/sizeof(ar[0]);for(int i = 0;i<n;++i){struct ElemType item = {ar[i],nullptr};bool tag = Insert_Item(&ht,item);}return 0;
}

ElemType x;x.key = NIL;
x.ptr = nullptr;

如果感觉自己彻底理解此程序？

画出结构内存图

1. HashTable初始化

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Sb4ECnLi-1632805088085)(C:\Users\Lenovo\AppData\Roaming\Typora\typora-user-images\image-20210927105747111.png)]

2. HashTable插入值

使用规则：

关键码从大到小排序，折半查询

不适合频繁的插入和删除，否则要进行大规模的数据移动

哈希冲突，以及解决哈希冲突的方法，查询方式

以链式哈希解决哈希冲突

根据这个图设计出哈希结构

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RM8EYfjW-1632805088087)(C:\Users\Lenovo\AppData\Roaming\Typora\typora-user-images\image-20210927114530048.png)]

#define NIL -1
#define m 13
typedef int KetType;
typedef struct
{KeyType key;void *ptr;
}ElemType;
typedef struct HashNode
{ElemType data;struct HashNode* next;
}HashNode;
typedef struct
{HashNode* data[m];int cursize;
}HashTable;int Hash(KeyType kx)
{return kx % m;
}
void Init_Hash(HashTable *pt)
{assert(pt != nullptr);for(int i = 0;i < m;++i){pt->data[i] = nullptr;}pt->cursize = 0;
}
bool Insert_Item(HashTable* pt,ElemType item)
{assert(pt != nullptr);int index = Hash(item.key);HashNode *s = (HashNode*)malloc(sizeof(HashNode));if(nullptr == s) exit(1);s->data = item;s->next = pt->table[index];pt->table[index] = s;pt->cursize += 1;
}
HashNode *FindValue(HashTable *pt,KeyType kx)
{int index = Hash(kx);HashNode *p = pt->table[index];while(p != nullptr && p->data.key != kx){p = p -> next;}return p;
}
void ClearHash(HashTable*pt)
{}
void Remove(HashTable *pt,KeyType kx)
{}
int main()
{int ar[] = {1,55,19,20,10,11,14,68,84,23,27,79};int n = sizeof(ar)/sizeof(ar[0]);HashTable ht;Init_Hash(&ht);for(int i = 0;i<n;++i){ElemType item = {ar[i],nullptr};Insert_Item(&ht,item);}KeyType kx;scanf_s("%d",&kx);HashNode *p = FindValue(kx);if(p != nullptr){}return 0;
}

面试试题：

如果为字符串，怎么做？

int Hash(KeyType kx)
{return kx % m;
}