0

我正在将一个小 C++ 程序重写为纯 C，这是一个非常简单的程序，它使用map. 我正在使用静态大小的哈希表（包含大小和指向链接节点列表的指针数组的结构）。我无法将以下部分重写为 C

#if 1       // switch between 1 and 0
# include <tr1/unordered_map>
  typedef std::tr1::unordered_map<std::string,int>  map_t;
#else
# include <map>
  typedef std::map<std::string,int>  map_t;
#endif

我主要使用哈希函数实现了无序版本，我是这样使用的

#if 1    // switch between 1 and 0
    int hash_function(const char *key, int size);
#else
    #define hash_function(key, size) .......
#endif

但现在我不知道宏应该是什么样子，因为我想要订购表格并且我有表格的静态大小。因为我没有使用地图的经验，所以我不知道是否有任何传统的方式来实现这一点。

我想到了将表格用作二维数组，作为简单矩阵，并从上到下逐列填充。

再说一次，有没有更好的传统方式来做到这一点？

4

1 回答 1

1

有序 hashmap 的一个非常典型的实现就是一个常规的 hashmap，它带有一个按顺序遍历所有元素的附加链表。诀窍是在每次插入和删除时都正确地维护这个链表。散列函数不需要（需要）改变 b/w 和有序和无序的 hashmap。

您的二维数组想法的主要问题是它消耗n*sizeOfHashTable空间，其中大部分都被浪费了。

如果您正在实现排序映射，您通常采用任何有序的数据结构，如二叉搜索树，并让键（这是您排序的对象）也具有与它们关联的值。然后你根本不使用散列函数。

于 2012-04-22T21:18:53.307 回答