散列表（哈希表）

哈希表的构造和冲突解决方法：
http://data.biancheng.net/view/63.html
其中二次探测法：d= 1²,-1²,……
哈希查找算法：
给定要查找的关键字key之后,先用过哈希函数找到key对应的地址，然后取该地址的值进行比较，如果不相等，说明在构造哈希表的过程中出现过冲突并采用过解决冲突的方法，这里假设采用的是开放定址法中的线性探测法。此时，也要通过线性探测法重新结算H(key），并进行比较。
代码：

#define HASHSIZE 12
#define NULLKEY -32768

typedef struct
{
    
	int *elem;	// 数据元素的基址，动态分配数组
	int count;	// 当前数据元素的个数
}HashTable;

int InitHashTable(HashTable *H)
{
    
	H->count = HASHSIZE;
	H->elem = (int *)malloc(HASHSIZE * sizeof(int));
	if( !H->elem )
	{
    
		return -1;
	}
	for( i=0; i < HASHSIZE; i++ )
	{
    
		H->elem[i] = NULLKEY;
	}
	return 0;
}

// 使用除留余数法
int Hash(int key)
{
    
	return key % HASHSIZE;
}

// 插入关键字到散列表
void InsertHash(HashTable *H, int key)
{
    
	int addr;
	
	addr = Hash(key);
	
	while( H->elem[addr] != NULLKEY )	// 如果不为空，则冲突出现
	{
    
		addr = (addr + 1) % HASHSIZE;	// 开放定址法的线性探测
	}
	
	H->elem[addr] = key;
}

// 散列表查找关键字
int SearchHash(HashTable H, int key, int *addr)
{
    
	*addr = Hash(key);
	
	while( H.elem[*addr] != key )
	{
    
		*addr = (*addr + 1) % HASHSIZE;
		/* *addr == Hash(key)说明已经查找过一个周期也没找到， H.elem[*addr] == NULLKEY说明在最原始的addr往后依次查找时，遇到了空位，说明这个key并没有存放在此表中*/
		if( H.elem[*addr] == NULLKEY || *addr == Hash(key) )
		{
    
			return -1;
		}
	}
	
	return 0;
}

代码讲解：
B站小甲鱼视频：
https://www.bilibili.com/video/BV1jW411K7yg?p=87