如何实现关联数组/映射/哈希表数据结构（一般情况和 C++ 中）
好吧，我正在制作一个小型电话簿应用程序，我决定使用地图将是最好的数据结构，但我不知道从哪里开始。 （必须从头开始实现数据结构 - 学校作业）
Well I'm making a small phone book application and I've decided that using maps would be the best data structure to use but I don't know where to start. (Gotta implement the data structure from scratch - school work)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
Tries 对于实现键为短字符串的映射非常有效。维基百科的文章解释得很好。
要处理重复项，只需使树的每个节点存储重复匹配项的链接列表即可。
这是字母的 trie malloc(26*sizeof(struct Trie)) 的基本结构
，并且您有一个数组。如果您想支持标点符号，请将它们添加到字母数组的末尾。
matches 可以是匹配项的链接列表，可以按照您喜欢的方式实现，我不会为您定义 struct List。
Tries are quite efficient for implementing maps where the keys are short strings. The wikipedia article explains it pretty well.
To deal with duplicates, just make each node of the tree store a linked list of duplicate matches
Here's a basic structure for a trie
malloc(26*sizeof(struct Trie)) for letter and you have an array. if you want to support punctuations, add them at the end of the letter array.
matches can be a linked list of matches, implemented however you like, I won't define struct List for you.
最简单的解决方案：使用包含地址条目的向量并循环该向量进行搜索。
映射通常作为二叉树（寻找红/黑树以进行平衡）或哈希映射来实现。它们都不是微不足道的：树在组织、内存管理和平衡方面有一些开销，哈希图需要良好的哈希函数，这也不是微不足道的。但这两种结构都很有趣，并且通过实现其中一种（或者更好的是，两者都实现:-)），您将获得很多深入的理解。
还可以考虑将数据保留在向量列表中，并让映射包含向量的索引（或指向条目的指针）：然后您可以轻松地拥有多个索引，例如一个用于姓名，一个用于电话号码，这样您就可以查找两者的条目。
也就是说，我只是想强烈建议使用标准库提供的数据结构来完成实际任务:-)
Simplest solution: use a vector which contains your address entries and loop over the vector to search.
A map is usually implemented either as a binary tree (look for red/black trees for balancing) or as a hash map. Both of them are not trivial: Trees have some overhead for organisation, memory management and balancing, hash maps need good hash functions, which are also not trivial. But both structures are fun and you'll get a lot of insight understanding by implementing one of them (or better, both :-)).
Also consider to keep the data in the vector list and let the map contain indices to the vector (or pointers to the entries): then you can easily have multiple indices, say one for the name and one for the phone number, so you can look up entries by both.
That said I just want to strongly recommend using the data structures provided by the standard library for real-world-tasks :-)
一种简单的入门方法是创建一个使用两个向量的映射类 - 一个用于键，一个用于值。要添加一项，您需要在一项中插入一个键，在另一项中插入一个值。要找到一个值，只需循环所有键即可。一旦完成这项工作，您就可以考虑使用更复杂的数据结构。
A simple approach to get you started would be to create a map class that uses two vectors - one for the key and one for the value. To add an item, you insert a key in one and a value in another. To find a value, you just loop over all the keys. Once you have this working, you can think about using a more complex data structure.