哈希表（hash_table） 哈希存储 算法相关知识 稳定性 时间复杂度

哈希存储(散列存储)

为了快速定位数据

哈希表

哈希冲突 / 哈希矛盾

关键字不一样，但是映射之后结果一样

如何避免 哈希矛盾？

1、重新设计哈希函数，尽可能均匀散列分布在哈希表

2、开放定址法：向下寻找未存储的位置进行存放数据

3、链地址法： 将数据链表的首地址存入哈希表，只需将数据结点往链表后链接即可

 
#include "head.h"
#include "hash.h"
 
HASH_NODE *hash_table[HASH_SIZE] = {NULL};
 
int hash_fun(char ch)
{
	if(ch>'a' && ch<='z')
	{
		return ch - 'a';
	}
	else if(ch > 'A' && ch <= 'Z')
	{
		return ch - 'A';
	}
	else
	{
	   return HASH_SIZE - 1;
	}
}
 
/*建立haxi表插入数据*/
int insert_hash_table(DATA_TYPE data) 
{
	HASH_NODE *pnode = malloc(sizeof(HASH_NODE));
	if(NULL == pnode)
	{
		perror("fail malloc");
		return -1;
	}
	pnode->data = data;
	pnode->pnext = NULL;
	
	int addr = hash_fun(data.name[0]);
	
	pnode -> pnext = hash_table[addr];
	hash_table[addr]= pnode;
}
 
 
 
/* 遍历 */
void hash_table_for_each()
{
	int i = 0;
	
	for( i = 0; i<HASH_SIZE;i++)
	{
		HASH_NODE *ptmp = hash_table[i];
		while(ptmp!=NULL)
		{
			printf("%s ",ptmp->data.name);
			printf("%s ",ptmp->data.tel);
			printf("%s ",ptmp->data.addr);
			printf("%d ",ptmp->data.age);
			ptmp = ptmp -> pnext;
		}
		printf("\n");
	}
}
/*查找*/
void find_hash_table_message(char *name)
{
	HASH_NODE *ptmp = NULL;
	
	ptmp = hash_table[hash_fun(*name)];
	while(strcmp(ptmp->data.name,name)) 
	{
		ptmp=ptmp->pnext;
	}
	printf("===========================\n");
	printf("%s ",ptmp->data.name);
	printf("%s ",ptmp->data.tel);
	printf("%s ",ptmp->data.addr);
	printf("%d ",ptmp->data.age);
	printf("\n===========================\n");
}
/*销毁*/
int destory_hash_table()
{
	int i = 0;
	HASH_NODE *ptmp = NULL;
	for(i = 0; i<HASH_SIZE;i++)
	{
		while(hash_table[i]!=NULL)
		{
			ptmp = hash_table[i];
			hash_table[i] = ptmp->pnext;
			free(ptmp);
		}
	}
}
 

算法

解决特定问题求解步骤

算法的设计
1、正确性
        语法正确

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

        对非法的输入，给出满足要求的规格说明；对精心选择，甚至刁难的测试都能正常运行，结果正确

2、可读性
        便于交流，阅读，理解，高内聚，低耦合

3、健壮性
        输入非法数据，能进行相应的处理，而不是产生异常

4、高效率
        时间复杂度

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

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

一般用大O表示法：O(n) —— 时间复杂度是关于数据n的一个函数，随着n的增加，时间复杂度增长较慢的算法时间复杂度低

时间复杂度的计算规则
        1，用常数1 取代运行时间中的所有加法常数

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

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

5、低储存
         空间复杂度

    稳定性  一样的数经过排序 两个相等的数看其位置是否发生变换 未发生则稳定

        排序算法：           
    稳定  冒泡 for for if 交换  时间复杂度 O(n^2)
          
  不稳定  选择 O(n^2)
          
    稳定  插入 O(n^2)
          
  不稳定  快速 O(nlogn)
          
          二分查找 O(logn)