哈希表——时间复杂度O(1)
一、散列函数和哈希表
哈希表又叫散列表，哈希表中的元素可以直接查找，因此时间复杂度为O(1)。
二、代码实现
hash计算不要求掌握，明白原理即可。冲突是由于对maxkey取余造成的，避免hash冲突可采用链表法，开放地址法等。
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#define MaxKey 1000
// hash计算
int hash(const char* key) {
int h = 0, g;
while (*key) {
h = (h << 4) + *key++;
g = h & 0xf000000;
if (g) {
h ^= g >> 24;
}
h &= ~g;
}
return h % MaxKey;
}
int main()
{
const char* pStr[5] = {
"beijing","tianjin","shanghai","shenzhen","guangzhou" };
const char* pHash_table[MaxKey] = {
NULL}; // 将hash算过的值存入表中
for (int i = 0; i < 5; i++) {
printf("%s is key=%d
", pStr[i], hash(pStr[i]));
pHash_table[hash(pStr[i])] = pStr[i];
}
return 0;
}
