-哈希表-

代码

#include<stdio.h>
#include<malloc.h>

#define table_size 19

typedef struct node {
	int key;
	char value;
}node,*nodeptr;

typedef struct hashlist {
	int length;
	nodeptr elements;
}hashlist,*listptr;

listptr initlist(int* parakeys, char* paravalues, int paralength) {
	int i, tempposition;
	listptr resultptr = (listptr)malloc(sizeof(struct hashlist));

	resultptr->length = paralength;
	resultptr->elements = (nodeptr)malloc(table_size * sizeof(struct node));
	for (i = 0; i < table_size; i++) {
		resultptr->elements[i].key = -1;
		resultptr->elements[i].value = 'x';
	}

	for (i = 0; i < paralength; i++) {
		tempposition = parakeys[i] % table_size;

		while (resultptr->elements[tempposition].key != -1) {
			tempposition = (tempposition + 1) % table_size;
			printf("collision, move forward for key %d.\r\n", parakeys[i]);
		}

		resultptr->elements[tempposition].key = parakeys[i];
		resultptr->elements[tempposition].value = paravalues[i];
	}
	return resultptr;
}

char hashsearch(listptr paraptr, int parakey) {
	int tempposition = parakey % table_size;

	while (paraptr->elements[tempposition].key != -1) {
		if (paraptr->elements[tempposition].key == parakey) {
			// printf("found\r\n");
			return paraptr->elements[tempposition].value;
		}
		// printf("not this one for %d.\r\n", parakey);
		tempposition = (tempposition + 1) % table_size;
		// printf("looking at position %d\r\n", tempposition);
	}
	return 'x';
}

void hashsearchtest() {
	int tempunsortedkeys[] = { 16, 33, 38, 69, 57, 95, 86 };
	char tempcontents[] = { 'h', 'e', 'l', 'o', 'w', 'r', 'd' };
	listptr tempptr = initlist(tempunsortedkeys, tempcontents, 7);

	printf("search result of 95 is: %c\r\n", hashsearch(tempptr, 95));
	printf("search result of 38 is: %c\r\n", hashsearch(tempptr, 38));
	printf("search result of 57 is: %c\r\n", hashsearch(tempptr, 57));
	printf("search result of 4 is: %c\r\n", hashsearch(tempptr, 4));
}

int main() {
	hashsearchtest();
	return 1;
}

运行结果

collision, move forward for key 57.
collision, move forward for key 95.
collision, move forward for key 95.
search result of 95 is: r
search result of 38 is: l
search result of 57 is: w
search result of 4 is: x

代码解说

哈希表（hash table）是一种非常重要的数据结构，它使用哈希函数（hashing function）将键（key）映射到存储桶（bucket）中，从而实现数据的快速存储、查找、删除等操作。哈希表在平均情况下能够实现o(1)的查找、插入和删除时间复杂度，因此被广泛应用于各种场景，如缓存系统、数据库索引、编程语言中的字典等。