哈希表定义及实现

哈希表也叫散列表，是快速执行查找，删除，插入的技术，不支持元素排序信息。原理是通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。
关键码值到存储位置的映射被称为哈希函数也叫散列函数，当不同关键key被映射到同一value时，称为冲突。
解决冲突主要有：
分离链接法：对Hash表中每个Hash值建立一个冲突表，即将冲突的几个记录以表的形式存储在其中。
开发定址法：根据冲突算法找到空的单元为止（线性探测法，平方探测法...）。

编程实例

算法实现

采用平方探测法的实现放在git@code.aliyun.com:c-program/projecteuler.git上projecteulerccommonstruct目录下elr_hash_int.h elr_hash_int.c两个单元内。

解决问题

https://www.hackerrank.com/ch...
要求用一个map结构存放名字name和电话phone。

定义结构

#define MaxStr 20typedef unsigned long int Index;typedef Index Position;typedef char *KeyType;typedef long int *ValueType;struct HashTbl;typedef struct HashTbl *HashTable;enum KindOfEntry { Legitimate, Empty, Deleted };struct HashEntry {  KeyType Key;  ValueType Value;  enum KindOfEntry Info;};typedef struct HashEntry Cell;struct HashTbl {  long int TableSize;  Cell *TheCells;};

初始化及释放

HashTable InitializeTable(long int TableSize) {  HashTable H;  long int i;  H = malloc(sizeof(struct HashTbl));  if (H == NULL) {    printf("Out of space!\n");  }  H->TableSize = TableSize;  H->TheCells = malloc(sizeof(Cell) * H->TableSize);  if (H->TheCells == NULL) {    printf("Out of space!\n");  }  for (i = 0; i < H->TableSize; i++) {    H->TheCells[i].Info = Empty;    H->TheCells[i].Key = NULL;    H->TheCells[i].Value = 0;  }  return H;}void DestroyTable(HashTable H) {  int i;  if (H == NULL) {    return;  }  for (i = 0; i < H->TableSize; i++) {    H->TheCells[i].Info = Empty;    if (H->TheCells[i].Key != NULL) {      free(H->TheCells[i].Key);    }  }  free(H);}

哈希及冲突插入操作

Position Hash(KeyType Key, long int TableSize) {  long int keyValue = 0;  register unsigned char *p;  for (p = (unsigned char *)Key; *p; p++) {    keyValue = 31 * keyValue + *p;  }  return keyValue % TableSize;}int KeyEqual(KeyType a, KeyType b) {  if ((a == NULL) || (b == NULL)) {    return 1;  }  return strcmp(a, b) == 0 ? 0 : 1;}int Find(KeyType Key, HashTable H, Position *Pos) {  Position CurrentPos;  long int CollisionNum;  int rst = 0;  CollisionNum = 0;  CurrentPos = Hash(Key, H->TableSize);  while (1) {    if (H->TheCells[CurrentPos].Info == Empty)      break;    if (KeyEqual(H->TheCells[CurrentPos].Key, Key) == 0) {      rst = 1;      break;    }    CurrentPos += (++CollisionNum << 1) - 1;    if (CurrentPos >= H->TableSize) {      CurrentPos -= H->TableSize;    }  }  *Pos = CurrentPos;  return rst;}void Insert(KeyType Key, ValueType Value, HashTable H) {  Position Pos;  int exist;  exist = Find(Key, H, &Pos);  H->TheCells[Pos].Info = Legitimate;  if (!exist) {    H->TheCells[Pos].Key = malloc(sizeof(char) * MaxStr);  }  strcpy(H->TheCells[Pos].Key, Key);  H->TheCells[Pos].Value = Value;}

调用解决问题

#include <math.h>#include <stdio.h>#include <stdlib.h>#include <string.h>int main() {  long int n = 0;  scanf("%ld", &n);  HashTable H = InitializeTable(n * 2);  for (int i = 0; i < n; i++) {    char name[20];    long int phone;    scanf("%s %ld", name, &phone);    Insert(name, phone, H);    }    for (int i = 0; i < n; i++) {      char name[20];      Position Pos;      int exist;      scanf("%s", name);      // while (() != '\n');      exist = Find(name, H, &Pos);      if (exist == 1) {          ValueType Value = H->TheCells[Pos].Value;          printf("%s=%ld\n", name, Value);      } else {        printf("Not found\n");      }      if (getchar() == EOF)        break;    }    DestroyTable(H);        return 0;}