c-为什么我要使用数据结构(例如哈希表)而不是数组

这听起来可能很愚蠢，但我正在努力制作一个高效的程序(时间/内存方面)，并研究哈希表。我已经看到，它基本上是一个链表数组，当表中的所有位置都被占用时，就会开始填满。这开始需要内存和时间，因为与数组不同，它们需要mallocs来存储数据和时间来搜索元素；这一切都是因为阵列不是动态的，并且具有有限的

所以我只是想知道，为什么我不能制作一个200亿长的数组，这样我就可以使用索引访问O(1)，而不需要mallocs？就像，一个巨大的阵列在主，这都是

我需要将文本保存为一堆行，这样我就知道每一行在哪里(第1行将是第一行，duh)，对我来说似乎没有必要使用哈希表，但问题是我不知道它会有多少行，所以如果我制作一个50行的数组，可能还不够，我想知道是使用列表/哈希表/其他结构更好，还是只使用一个字符数组数组更好

这听起来可能很愚蠢，但我正在努力制作一个高效的程序(时间/内存)

高效程序要做什么？你从来没有真正说出你想做什么。

研究哈希表我已经看到它基本上是一个链表数组

这是一个常见的实现，但它并不能说明为什么首先要使用哈希表。

在搜索基于非数字键(即字符串)的记录时，可以使用哈希表。您将该键输入一个哈希函数，该函数会输出一个整数值，然后使用该值对表进行索引。因此，如果f("foo")吐出3，那么这就是用于存储具有关键字"foo"的数据的表索引。

没有一个实用的哈希函数是完美的，不同的字符串可能会导致相同的哈希值，称为冲突。使用链表是解决冲突的一种方法，其他方法是计算表中的辅助索引，或者只在返回的索引上加1。

相对于线性或二进制搜索，从密钥计算哈希的速度快，与线性搜索时间O(n)和二进制搜索时间O相比，时间复杂度为O(1)(log₂n)。折衷的办法是，您的表在任何方面都不是有序的——线性遍历将显示为随机有序。

编辑

来自评论：

我需要将文本保存为一堆行，这样我就知道每一行在哪里(第1行将是第一行，duh)，对我来说似乎没有必要使用哈希表，但问题是我不知道它会有多少行，所以如果我制作一个50行的数组，可能还不够，我想知道是使用列表/哈希表/其他结构更好，还是只使用一个字符数组数组(也在帖子中添加)

如果只需要存储字符串序列，可以动态分配一个数组，然后根据需要扩展该数组。假设所有的行都是已知的固定长度，您可以这样做(将文件读取到内存中，将内容转储到标准输出)：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_LENGTH 80
size_t read_arr( FILE *in, char (**arr)[MAX_LENGTH+1] ) 
{
size_t size = 1;
size_t read = 0;
*arr = malloc( sizeof **arr * size );
if ( !*arr )
{
return 0;
}
char buf[MAX_LENGTH+1];
while( fgets( buf, sizeof buf, in ) )
{
if ( read == size )
{
char (*tmp)[MAX_LENGTH+1] = realloc( *arr, sizeof **arr * (size * 2) );
if ( tmp )
{
*arr = tmp;
size *= 2;
}
else
{
fprintf( stderr, "Unable to extend array past %zu entries, returning what we have so far.n", read );
return read;
}
}
strcpy( (*arr)[read++], buf );
}
return read;
}
int main( int argc, char **argv )
{
if ( argc < 2 )
{
fprintf( stderr, "USAGE: %s <file name>n", argv[0] );
return EXIT_FAILURE;
}
FILE *in = fopen( argv[1], "r" );
if ( !in )
{
fprintf( stderr, "File %s not foundn", argv[0] );
return EXIT_FAILURE;
}
char (*arr)[MAX_LENGTH+1];
size_t n = read_arr( in, &arr );
for ( size_t i = 0; i < n; i++ )
printf( "%s", arr[i] );
free( arr );
return EXIT_SUCCESS;
}

realloc是一个相对昂贵的操作，因此您不希望对文件中的每一行都执行它。每次将数组加倍可以最大限度地减少调用次数，尽管代价是内部碎片的可能性(例如，需要256行来存储129行)。但总的来说，这应该不是问题。

你能告诉我什么是char (**arr)[MAX_LENGTH+1]吗？我从来没有见过这种结构；它是一个2d阵列吗？

是的，我想我应该解释一下。

T (*a)[N];

将a声明为指向T的N元素数组的指针。CCD_ 8类型的表达式将"；衰变；以键入T (*)[N](而不是T **)。

我想动态地分配足够的空间来存储T [N]类型的M个对象。因此，我们从常见的习语开始

P *p = malloc( sizeof *p * M );

sizeof *p等价于sizeof (P)，因此我们分配了足够的空间来存储P类型的M个对象。现在，我们将类型P替换为数组类型T [N]，这为我们提供了

T (*p)[N] = malloc( sizeof *p * M );

在这种情况下，sizeof *p等价于sizeof (T [N])，因此我们分配了足够的空间来存储T的M个N元素阵列。

由于a[i]被定义为*(a + i)，因此以下情况成立：

(*p)[i] == (*(p + 0))[i] == (p[0])[i] == p[0][i]

因此，我们可以像任何其他2D数组一样索引到p中。

因此，在上面的main函数中，我将arr声明为指向char的MAX_LENGTH+1数组的指针。由于我希望read_arr更新存储在arr中的值(分配内存的地址)，因此我需要向arr传递指针。请记住，如果您希望函数更新其某个参数，则必须将指针传递给该参数¹，即使该参数已经是指针类型。如果arr的类型是char (*)[MAX_LENGTH+1]，则&arr的类型是"char (**)[MAX_LENGTH+1]"；指向CCD_ 34的指针的指针-CCD_；。

同样，这假设文件中的所有行都接近相同的长度，并且它们都小于某个已知的最大长度。如果你有一个文件，其中的行长度相差很大，或者99%的行长度为20，一两行长度为200，那么你会想做其他事情。

^{数组很奇怪，但在这种情况下，我们处理的不是数组类型，而是指针类型}

哈希表是一种数据结构，允许在给定键的情况下快速检索数据项。

哈希表使用键的哈希进行索引。它将键映射到用于索引表的整数上。哈希函数通常非常快。

哈希表通常比可能的键的数量小得多。因此，散列函数可以为多个不同的键生成相同的索引。这被称为碰撞。为了处理冲突，哈希表条目通常有一个链表(但平衡的二进制树也是可能的)。该列表存储哈希表条目的所有冲突。

因此，给定一个键，散列函数确定表中的索引，然后在该条目的列表中搜索实际键，然后检索与该键相关的数据。正如您所看到的，这比搜索链表要快得多，并且比为每个可能的键都有一个条目的数组占用的内存要少得多。

维护表和列表会有一些开销，但主要的好处是快速的数据检索。

设计散列函数本身就是一门科学。

注意：因此哈希表由两个数据结构组成：哈希表本身及其大小和哈希函数，以及哈希表条目，该条目可以是列表、排序列表、树或其他任何内容。

您可以。如果你有那么多的记忆力。但从统计的角度来看，一个哈希表也同样好。它们在平均上具有O(1)查找。这可能很难理解如何以及为什么，所以我的建议是尝试实现自己的，只是为了学习。此外，malloc调用在一个好的操作系统上应该不会很慢。

它实际上非常简单。

不能使用200亿长的阵列的原因是它需要80G的RAM。如果是64位，则为160 GB。

此外，您不能用字符串对它们进行索引。myArray["hello"] = "world";永远不会工作。

如果您已经知道要搜索的每个元素的索引，那么使用数组非常有用，可以减少所有操作的时间。

在内存部分，因为数组具有固定的维度，所以如果您知道或不知道必须保存的总数据，则一切都会下降；因为如果"；只是为了确定"；如果创建一个具有200亿个索引的数组，然后只使用前100个索引，那么与使用动态内存相比，这是一个非常糟糕的选择，动态内存只能在需要更多空间的情况下进行扩展。

相关内容

最新更新

热门标签：