怎么建立自己公司的网站,上海网站建设的英文,公众号制作培训,石家庄网站建设哈希表 这里没有讲哈希表底层的概念#xff0c;什么转红黑树#xff0c;什么链表的#xff0c;这篇文章主要讲的是如何用C实现哈希表#xff0c;以及哈希表的基本概念。后面我会出一篇文章来讲C中hashmap中的底层逻辑的知识。 哈希表的概念 哈希表是一种数据结构#xff0… 哈希表 这里没有讲哈希表底层的概念什么转红黑树什么链表的这篇文章主要讲的是如何用C实现哈希表以及哈希表的基本概念。后面我会出一篇文章来讲C中hashmap中的底层逻辑的知识。 哈希表的概念 哈希表是一种数据结构类似于数组但它的主要优势在于快速查找和检索数据。在数组中每个位置可以存储值查找或删除特定位置的值的效率是O(1)只需将相应的索引提供给数组即可直接访问。然而如果您只有值想要在数组中查找这个值时时间复杂度会变成O(n)因为您需要遍历整个数组来找到匹配的值。 哈希表通过使用哈希函数来改善这种情况将查找操作的平均时间复杂度降低到O(1)。哈希函数将键key映射到数组的特定位置这个位置通常称为“桶”。通过哈希函数我们可以快速确定要查找或删除的数据所在的桶从而显著减少了查找的时间。 然而哈希表的优化是基于空间换时间的原则。它需要使用额外的内存空间来存储哈希表本身而且在某些情况下不同的键可能会映射到相同的桶导致哈希冲突。解决哈希冲突需要额外的处理例如链地址法或开放寻址法。尽管如此总体而言哈希表仍然提供了一种高效的数据存储和检索方式特别适用于需要快速查找数据的应用场景。 它的数据结构 结构定义 物理结构 数据域存储数据的位置也就是概念中所说的桶每个桶用于存储一个数据项或多个数据项的链表或其他数据结构。数组的大小通常是一个固定的值但在一些实现中也可以动态调整。 哈希函数哈希函数接受键Key作为输入并生成一个整数值这个值通常被称为索引。哈希函数的作用是将键映射到数组(桶)中的一个特定位置然后就可以通过Key值获得索引看当前位置是否有Key值。 冲突处理机制由于不同的键可能映射到相同的桶位置因此哈希表需要一种方法来处理这种冲突。常见的冲突处理方法包括链地址法在同一个位置也就是同一个通中形成一个链表讲不同的Key值像链表一样串起来开放寻址法在冲突的情况下寻找下一个可用的桶或者再哈希法讲带入过哈希函数的返回的值再次带入哈希函数。 typedef struct Node {//结点void key;//这里就是存储的key值可以是任何类型字符串数值字符等等struct Node *next;//链表肯定需要记录下一个结点的地址嘛
} Node;typedef struct Hash{int size;//哈希表的长度Node **data;//数据域这里用到了链表也就是链式地址法俗称拉链法//假如哈希冲突了不同的key值找到了同一个位置然后就直接接到这个链表的后面然后进行对比该条链表的结点的key值如果找到了说明存在key值如果没找到就说不不纯在key值
} Hash;int Hashfunchtion(void key) {//哈希函数return ;//这里就需要看key是对应的什么类型来定义哈希函数
} 逻辑结构 键-值对哈希表的逻辑结构由键-值对组成。键是用户提供的数据而值是与键关联的实际数据。哈希表使用键来计算索引并将值存储在对应的桶中。 索引索引是通过哈希函数计算得到的整数值它用于确定数据项在数组中的位置。索引是键的逻辑表示在查找、插入和删除数据时都用到。 结构操作 哈希表主要就是插入和查找操作其他的操作只要学会了前面两个操作基本都能自己实现下面我就讲述插入和查找操作 插入操作 如图插入操作这里的key值用的是字符串将字符串ABC添加入哈希表中 假如key值换了然后获得的下标也是4下面就是防冲突机制处理,这里添加的字符串是abc 然后完成了冲突操作的插入 片段代码实现 int Hashfunchtion(char *key) {//哈希函数这里用到的和图中的不一样这样可以更高效的防冲突int seed 18, hash 0;for (int i 0; key[i]; i) hash hash * seed key[i];//这里可能会变为负数return hash 0x7fffffff;//0x7fffffff这是16进制你转换为二进制就是除了符号位都是1//正数与上它不变负数与上就变为整数
}Node *getNewNode(char *key, Node *head) {Node *p (Node *)malloc(sizeof(Node));p-key strdup(key);p-next head;//这里用到的是头插法,从头部直接插入接上后面的结点,如果是第一次插入这个位置那么head就是NULLreturn p;
}int insert(Hash *h, char *key) {//插入元素int ind Hashfunchtion(key) % h-size;//先将key带入哈希函数转为整数然后模上哈希表的长度使他的值不会超出哈希表的范围最后获得索引h-data[ind] getNewNode(key, h-data[ind]);return 1;
} 查找操作 现在我添加了几个元素进这个哈希表中如图 现在在这个哈希表中查找Key good 在哈希表中查询该位置的地址为空那么就说明在哈希表中没有该元素返回0 现在查询Key buc 索引为4对应地址不为空那么就创建一个指针进行对链表遍历进行对链表中每个结点中的对应的Key值进行对比最后发现没有遍历完链表现在指针应该指向空一样返回0 现在查询Key ABC 索引为4对应地址不为空那么就创建一个指针进行对链表遍历进行对链表中每个结点中的对应的Key值进行对比然后指针指到地址2时匹配成功最后返回该指针是否为空为空就返回0不为空返回1那么现在返回的就是1查找成功 ok集中查询情况了解了来看一下代码片段是如何实现的 int Hashfunchtion(char *key) {//哈希函数int seed 18, hash 0;for (int i 0; key[i]; i) hash hash * seed key[i];//这里可能会变为负数return hash 0x7fffffff;//0x7fffffff这是16进制你转换为二进制就是除了符号位都是1//正数与上它不变负数与上就变为整数
}int search(Hash *h, char *key) {//查找key是否在哈希表中int ind Hashfunchtion(key) % h-size; //先获取key值对应索引Node *p h-data[ind];while (p strcmp(p-key, key)) p p-next;//比较当前索引的结点链表中的key因为这里key是字符串需要用到strcmp函数进行对比return p ! NULL;//如果pNULL返回0说明没有找到如果p不为空那说明找到
} 最终代码 #include stdio.h
#include string.h
#include stdlib.htypedef struct Node {//结点char *key;//这里就是存储的key值可以是任何类型字符串数值字符等等struct Node *next;//链表肯定需要记录下一个结点的地址嘛
} Node;typedef struct Hash{int size;//哈希表的长度Node **data;//数据域这里用到了链表也就是链式地址法俗称拉链法//假如哈希冲突了不同的key值找到了同一个位置然后就直接接到这个链表的后面然后进行对比该条链表的结点的key值如果找到了说明存在key值如果没找到就说不不纯在key值
} Hash;Hash *getNewHash(int n) {Hash *h (Hash *)malloc(sizeof(Hash)); h-size n 1;//为了防止以外开两倍h-data (Node **)calloc(sizeof(Node *), h-size);return h;
}int Hashfunchtion(char *key) {//哈希函数int seed 18, hash 0;for (int i 0; key[i]; i) hash hash * seed key[i];//这里可能会变为负数return hash 0x7fffffff;//0x7fffffff这是16进制你转换为二进制就是除了符号位都是1//正数与上它不变负数与上就变为整数
}Node *getNewNode(char *key, Node *head) {Node *p (Node *)malloc(sizeof(Node));p-key strdup(key);p-next head;//这里用到的是头插法,从头部直接插入接上后面的结点,如果是第一次插入这个位置那么head就是NULLreturn p;
}int insert(Hash *h, char *key) {//插入元素int ind Hashfunchtion(key) % h-size;//先将key带入哈希函数转为整数然后模上哈希表的长度使他的值不会超出哈希表的范围最后获得索引h-data[ind] getNewNode(key, h-data[ind]);return 1;
}int search(Hash *h, char *key) {//查找key是否在哈希表中int ind Hashfunchtion(key) % h-size; //先获取key值对应索引Node *p h-data[ind];while (p strcmp(p-key, key)) p p-next;//比较当前索引的结点链表中的key因为这里key是字符串需要用到strcmp函数进行对比return p ! NULL;//如果pNULL返回0说明没有找到如果p不为空那说明找到
}void clearNode(Node *root) {if (!root) return ;Node *p root, *q;while (p) {q p-next;free(p-key);free(p);p q;}free(q);return ;
}void clearHash(Hash *h) {if (!h) return ;for (int i 0; i h-size; i) clearNode(h-data[i]);free(h-data);free(h);return ;
}int main() {int op;char key[105] {0};Hash *h getNewHash(100);while (~scanf(%d%s, op, key)) {switch (op) {case 0: {printf(insert %s from Hash is success\n, key);insert(h, key);} break;case 1: {printf(search %s from Hash is %d\n, key, search(h, key)); } break;default:{clearHash(h);return 0;}}}return 0;
} 这里我只是实现了一种放冲突方法其实还有很多优秀的防冲突方法比如这个链表存地址的方法如果一个位置冲突多了链表的长度也变长了查找效率也变低了然后在c中的hashmap中转换为一个红黑树的结构这样插入和查找效率稳定在O(logn)
