哈希表、算法

哈希表

hash：

在编程和数据结构中，"hash" 通常指的是哈希函数，它是一种算法，用于将数据（通常是字符

串）映射到一个固定大小的数字（哈希值）。哈希函数在哈希表中尤为重要，哈希表是一种通过哈

希函数将键映射到表中位置的数据结构，以实现快速的数据插入和检索。

哈希表（Hash Table）：

也称为散列表，是一种通过哈希函数将键（Key）映射到表中一个位置以

便快速访问记录的数据结构。哈希表可以快速地插入和查找数据。

哈希算法：

将要存储的关键字与要存储的位置建立一种联系，这种联系就叫哈希函数/散列函数

哈希表的相关函数：

插入数据

int insert_hashtable(HSDataType data)
{int addr = hash_function(data.name[0]);HSNode_t *hanode = malloc(sizeof(HSNode_t));if(NULL == hanode){perror("fail malloc");return -1;}hanode->data = data;hanode->pnext = NULL;hanode->pnext = hashtable[addr];hashtable[addr] = hanode;
}

遍历哈希表

void hashtable_for_each()
{for(int i = 0;i < HASH_SIZE;++i){HSNode_t *p = hashtable[i];while(p != NULL){printf("**%10s  **%3s\n",p->data.name,p->data.tel);p = p->pnext;}}printf("\n");
}

查找数据

int find_key_hashtable(HSDataType data)
{int addr = hash_function(data.name[0]);HSNode_t *p = hashtable[addr];while(p != NULL){if(!strcmp(p->data.name,data.name)){printf("%s  %s\n",p->data.name,p->data.tel);return 0;}p = p->pnext;}return -1;
}

销毁哈希表

int destory_hashtable()
{for(int i = 0;i < HASH_SIZE;++i){HSNode_t *p = NULL;while(hashtable[i] != NULL){p = hashtable[i];hashtable[i] = p->pnext;free(p);}}
}

---

算法

算法即解决特定问题求解步骤

算法的设计

1.正确性

语法正确

合法的输入得到合理的结果

对非法的输入，给出满足要求的规格说明

对精心选择，甚至刁难的测试都能正常运行，结果正确

2.可读性

便于交流，阅读，理解 高内聚，低耦合

3.健壮性

输入非法内容，能进行相应的处理，而不是产生异常

4.高效率（时间复杂度）

算法时间复杂度：

执行这个算法所花时间的度量

将数据量增长和时间增长用函数表示出来，这个函数就叫做时间复杂度。

一般用大0表示法：0(n)------>时间复杂度是关于数据n的一个函数

随着n的增加，时间复杂度增长较慢的算法时间复杂度低

时间复杂度的计算规则

1，用常数1 取代运行时间中的所有加法常数

2，在修改后的运行函数中，只保留最高阶项

3，如果最高阶存在且系数不是1，则去除这个项相乘的常数

5.低存储（空间复杂度）

空间复杂度越低：低存储 越高：高存储

时间复杂度越低：高效率 越高：低效率

几种常见时间复杂度比较