我对哈希表的理解是,它们使用散列函数将键与内存中的位置相关联,在内存中预先分配了总数量的“桶”。我们的目标是有足够的存储桶,而不必使用链接,从而将理想的O(1)访问时间复杂度降低到n/m x O(1),其中n是要存储的唯一键数,m是存储桶的数量。
因此,如果我有1000个唯一的项目要存储,我需要不少于1000个桶,也许更多,以尽量减少使用我的链式链表的可能性。如果不是这样的话,我们就会期望平均哈希表会有很多很多冲突。如果我们有1000个预先分配的桶,那就意味着我有1000个字节的分配内存,分布在我的内存周围。因此,我的哈希表中的每一个唯一键都会产生一个内存片段,从而分割我的RAM。
这是否意味
比如说,我想要一个位图来知道某个字符在字符串中出现的次数。
因此,例如,如果我读取字符串"abracadabra",我将有一个数据结构,它看起来如下所示:
a -> 5
b -> 2
r -> 2
c -> 1
d -> 1
我读过一本书(),书中写着:
哈希表比数组具有更高的查找开销。
数组将需要为每个可能的字符提供一个元素。
哈希表只需要存储实际出现在字符串中的字符。因此:
对于具有有限的可能字符集的长字符串,数组是一个更好的选择,而哈希表对于较短的字符串或当有许多可能的字符值时更有效。
我不明白为什么:
->哈希表比数组具有更高的查找开
我用rehash/resize函数创建了一个简单的链哈希表,但它似乎不起作用。我不知道问题出在哪里。
当有超过5个元素存储在一个键上时,我想重新进行散列。
我知道调试器是我的朋友,我试着用调试器找出问题所在,但没有成功。我知道这可能不是有史以来最好的哈希表,但这是我第一次这样做。
谢谢你的帮助
#include <stdio.h>
#include <stdlib.h>
#define MAX 10
#define CAPACITY 5
#define FACTOR 0.7 // not using currently
typedef struct ha
我想用以下方式实现一个哈希表:
struct list
{
char *string;
struct list *next;
};
struct hash_table
{
int size; /* the size of the table */
struct list **table; /* the table elements */
};
我可以使用以下命令来代替上面的结构hash_table吗:
struct hash_table
{
int size; /* the size of the table */
struct list