网站建设制作确认单万能搜索引擎

当前位置： 首页 > news >正文

网站建设制作确认单,万能搜索引擎,公司网站用个人备案可以,北京精兴装饰公司口碑怎么样目录 1、散列表 2、散列函数 2.1 定义 2.2 散列函数的构造
2.2.1 除留余数法 2.2.2 直接定址法 2.2.3 数字分析法 2.2.4 平方取中法 3、冲突#xff08;碰撞#xff09; 4、处理冲突的方法
4.1 拉链法#xff08;链接法#xff09; 4.2 开放定址法 5、C语言…目录 1、散列表 2、散列函数 2.1 定义 2.2 散列函数的构造  2.2.1 除留余数法 2.2.2 直接定址法 2.2.3 数字分析法 2.2.4 平方取中法 3、冲突碰撞 4、处理冲突的方法  4.1 拉链法链接法 4.2 开放定址法 5、C语言实现散列表哈希表 方式一数组 方式二指针和动态内存分配 1、散列表 散列表Hash Table是一种数据结构它通过使用散列函数将关键字映射到表中的一个位置从而实现快速查找。散列表通常被用于实现字典、数据库索引等数据结构它可以提供关键字的高效插入、查找和删除操作。散列表的实现基于数组每个元素包含一个键值对key-value pair。其中键通常是一个字符串或整数值可以是任何类型的数据例如字符串、整数、对象等。在查找元素时散列表使用散列函数将关键字转换为数组索引并在此位置上查找键值对。如果存在则返回其对应的值如果不存在则返回空值。 2、散列函数 2.1 定义 散列函数是一种将输入数据映射到固定大小输出数据的函数。它将不同大小的输入数据转换成相同长度的散列值也称为哈希值、摘要或指纹通常用作数据加密、数字签名、消息认证码MAC等领域的基础。 散列函数应该满足以下要求

1. 均匀性散列函数应该将不同输入数据均匀地映射到输出空间的不同位置以减少散列冲突的发生。
2. 独立性输入数据的微小变化应该能够引起输出散列值的大幅度变化以增强散列函数的安全性。
3. 不可逆性根据输出散列值无法推导出输入数据即难以通过散列值反向计算出输入数据。 常见的散列函数算法包括MD5、SHA-1、SHA-2、SHA-3等。但是由于计算机计算能力的提高和攻击技术的发展目前常用的算法已不够安全需要不断更新和升级。 2.2 散列函数的构造  2.2.1 除留余数法 将关键字除以某个数m取余数作为散列地址即h(k)k%m。但是如果m的取值不合适可能会导致散列地址分布不均匀。m的取值一般是不大于散列表表长的最大质数。 2.2.2 直接定址法 将关键字直接映射为地址即h(k)a*kbab是常数。但是如果关键字取值范围较大则需要大量的内存空间。  2.2.3 数字分析法 选取数码分布较为均匀的若干位最为散列地址。 2.2.4 平方取中法 先将关键字平方然后取中间几位作为散列地址即h(k)取中间几位( k^2 )。这种方法能够减小散列地址的值的尺寸但是也可能出现分布不均匀的问题。 3、冲突碰撞 散列表的冲突指的是将两个或多个不同的键映射到了散列表的同一个位置上。这种情况称为冲突因为两个不同的键无法在同一个位置上存储。 散列表的冲突可以通过散列函数的优化和冲突解决方法来减少或避免。以下是几种常见的冲突解决方法 链接法 (Chaining)将相同位置上的键值对通过链表等数据结构链接在一起。开放地址法 (Open Addressing)在发生冲突时按照一定规则去寻找数组内的下一个空闲位置存储。双散列法 (Double Hashing)当发生冲突时使用另一个散列函数对键进行再次散列再根据新的散列值去找到空位置存储。 4、处理冲突的方法  4.1 拉链法链接法 散列表解决冲突的链接法又被称为“拉链法”其主要思想是将散列到同一个位置的元素存储在一个链表中。当散列到同一个位置的元素出现冲突时只需要将新的元素插入到链表的末尾即可。 具体实现方式如下
4. 创建一个散列表其中每个位置都是一个链表的头结点。
5. 对于要插入的元素先计算它的散列值并找到对应的链表头结点。
6. 遍历该链表查找是否有相同的元素如果有则更新它的值否则在链表末尾插入新元素。
7. 如果插入操作导致链表长度超过一定阈值可以考虑进行动态扩容或者重新散列操作。
8. 对于查询和删除操作也需要先计算元素的散列值找到对应的链表然后再进行操作。 在实际使用中为了避免链表过长影响性能可以设置一个阈值当链表长度超过该阈值时可以考虑进行扩容或者重新散列操作。 4.2 开放定址法 开放定址法是一种常用的解决冲突的方法。具体来说开放定址法的思想是当发现散列表中的某个位置已经被占用时就去寻找下一个可用的位置直到找到一个空槽或者遍历完整个散列表。 开放定址法中有四种基本的探测方法 1. 线性探测逐个查看表中的下一个空单元直到找到一个空的单元为止。 2. 平方探测访问下一个位置的时候是按照下一个位置的平方进行访问的。 3. 双重散列访问下一个位置的时候是根据第二个哈希函数得到的值来访问的。 4.伪随机序列法访问下一个位置的时候是根据伪随机序列数得到的值来访问的。 利用开放定址法解决冲突的散列表的具体实现步骤如下 1. 对于给定的键值计算其散列值。 2. 如果在散列表中的该位置为空则将该键值存储在该位置上。 3. 如果在散列表中的该位置已经被占用则使用开放定址法寻找下一个可用的位置直到找到一个空槽或者遍历完整个散列表。 4. 在寻找到的空槽上存储该键值。 5. 当需要查找某个键值时首先计算该键值的散列值并在散列表中查找该键值。如果已经找到则返回该键值的值。如果未找到则表示该键值不存在于散列表中。 开放定址法可能会造成散列表中某些位置被长时间占用导致散列表性能下降。因此在实现散列表时需要进行合理的设计和优化。 5、C语言实现散列表哈希表 方式一数组 哈希表是一种常用的数据结构它可以在平均情况下实现常数时间的插入、删除和查找操作。下面是用C语言数组实现哈希表的代码 #includestdio.h #includestdlib.h #includestring.h#define MAX_SIZE 100 //哈希表的最大长度//定义哈希表结构体 typedef struct HashTable{int size;int* keys;char** values; }HashTable;//哈希函数 int hashFunction(int key, int size){return key % size; }//创建哈希表 HashTable* createHashTable(int size){HashTable* hashtable (HashTable)malloc(sizeof(HashTable));hashtable-size size;hashtable-keys (int)calloc(size, sizeof(int));hashtable-values (char*)calloc(size, sizeof(char));for(int i0; isize; i){hashtable-keys[i] -1;}return hashtable; }//插入键值对 void insert(HashTable* hashtable, int key, char* value){int index hashFunction(key, hashtable-size);while(hashtable-keys[index] ! -1){ //如果该位置已经被占用则线性探测到下一个位置index;index % MAX_SIZE;}hashtable-keys[index] key;hashtable-valuesindexmalloc(sizeof(char) * (strlen(value)1));strcpy(hashtable-values[index], value); }//获取键对应的值 char* get(HashTable* hashtable, int key){int index hashFunction(key, hashtable-size);while(hashtable-keys[index] ! key){index;index % MAX_SIZE;}return hashtable-values[index]; }//删除键值对 void delete(HashTable* hashtable, int key){int index hashFunction(key, hashtable-size);while(hashtable-keys[index] ! key){index;index % MAX_SIZE;}hashtable-keys[index] -1;free(hashtable-values[index]); }//测试代码 int main(){HashTable* hashtable createHashTable(MAX_SIZE);insert(hashtable, 1, 张三);insert(hashtable, 2, 李四);insert(hashtable, 3, 王五);printf(%s\n, get(hashtable, 2)); //输出李四delete(hashtable, 1);printf(%s\n, get(hashtable, 1)); //输出空字符串return 0; }在该实现中我们使用了线性探测解决了哈希冲突的问题。对于哈希冲突我们首先根据哈希函数计算键的索引如果该位置已经被占用则继续向下线性探测直到找到空闲位置为止。当我们要查找或删除键值对时我们也需要进行线性探测直到找到对应的键为止。 方式二指针和动态内存分配 哈希表是一种常见的数据结构它可以支持快速的查询和插入操作。在C语言中我们可以使用指针和动态内存分配来实现一个哈希表。 下面是一个简单的哈希表实现示例 #include stdio.h #include stdlib.h #include string.h#define TABLE_SIZE 10000// 哈希表节点结构体 typedef struct HashNode {int key;int value;struct HashNode* next; } HashNode;// 哈希表结构体 typedef struct HashTable {HashNode* table[TABLE_SIZE]; } HashTable;// 哈希函数将key映射成一个索引 int hash(int key) {return key % TABLE_SIZE; }// 初始化一个哈希表 HashTable* initHashTable() {HashTable* ht (HashTable)malloc(sizeof(HashTable));memset(ht-table, 0, sizeof(ht-table));return ht; }// 插入一个键值对到哈希表中 void insert(HashTable ht, int key, int value) {int index hash(key);HashNode* node (HashNode)malloc(sizeof(HashNode));node-key key;node-value value;node-next NULL;if (ht-table[index] NULL) {ht-table[index] node;} else {HashNode cur ht-table[index];while (cur-next ! NULL) {cur cur-next;}cur-next node;} }// 查找一个key对应的值 int find(HashTable* ht, int key) {int index hash(key);HashNode* cur ht-table[index];while (cur ! NULL) {if (cur-key key) {return cur-value;}cur cur-next;}return -1; }// 从哈希表中删除一个键值对 void delete(HashTable* ht, int key) {int index hash(key);HashNode* cur ht-table[index];if (cur NULL) {return;}if (cur-key key) {ht-table[index] cur-next;free(cur);return;}HashNode* prev cur;cur cur-next;while (cur ! NULL) {if (cur-key key) {prev-next cur-next;free(cur);return;}prev cur;cur cur-next;} }int main() {HashTable* ht initHashTable();insert(ht, 1, 10);insert(ht, 2, 20);insert(ht, 3, 30);printf(%d\n, find(ht, 1));printf(%d\n, find(ht, 2));printf(%d\n, find(ht, 3));delete(ht, 2);printf(%d\n, find(ht, 2));return 0; }在上面的代码中我们定义了一个哈希表节点结构体HashNode包含了一个键值对和指向下一个节点的指针还定义了一个哈希表结构体HashTable包含了一个指针数组每个指针指向一个节点链表。 哈希函数hash将键映射成一个索引使用求余运算实现。初始化函数initHashTable动态分配内存并将指针数组初始化为空。插入函数insert根据哈希函数计算出索引再将节点插入到指针数组对应位置的链表中。查找函数find根据哈希函数计算出索引再在对应链表中遍历查找键值对。删除函数delete根据哈希函数计算出索引再在对应链表中遍历查找要删除的节点并释放对应的内存。 在主函数中我们创建一个哈希表并插入三个键值对。然后分别查找这三个键并删除第二个键。最后再次查找第二个键由于已经被删除输出-1。