再次谈到我即将到来的大学项目......我今天有一堂课，在那里我们可以询问关于这个项目的东西，但我还没有决定采用这种方法。两个哈希表，带有双键或不同解决方案的哈希表？
基本上，我有一堆用户（一些结构与几个成员）必须快速搜索名称和SSN。由于我还需要在Graph上使用这些用户（用于其他操作），因此我将使用指针。
现在，我虽然有关使用两个哈希表。一个是密钥是名字，另一个是密钥是SSN。但我不喜欢有两个哈希表的想法，只是用不同的键和指向相同的地方。
它使用带有两个键的哈希表横过我的脑海，但我甚至不知道这是否可能，我相信它不是。我只是想不出一个办法，也许有一个，或者不是。
除了这两个解决方案，我想不出任何其他的选择......我可能不得不使用两个哈希表。
你们有没有其他的建议？
我会去两个哈希表。把它看作是一个数据库中的两个索引。数据库是您的用户，并且您提供了两个索引：一个ssn索引和一个名称索引。
这就是我的想法，但是搞砸我的是我总是浪费2个指针用于相同的用户结构，每个哈希表中有一个。也许有没有办法... – 2010-03-02 19:20:30
保留两个索引的额外空间不应该是一个问题，除非你打算存储大量的用户。问题在于添加，删除，重命名用户或您计划执行的任何操作时，索引保持最新的复杂性。如果你认为这很容易处理，那么我会说这是一条路。 – 2010-03-02 19:25:06
我认为两个哈希表都可以。也考虑二叉搜索树，它们可以更紧凑，但O（log n）搜索更难以实现。
从来没有听说过“两个键哈希表” ......
我也没有，我只是虽然它可能存在大声笑...我认为二元搜索树，但就像你说的，他们是O（日志n），散列表的方式更快（当然最好的情况下）。另外，如果我能够实现平衡搜索树，二叉搜索树可能是一种选择，但我遇到了麻烦，我只是略过它。 – 2010-03-02 19:11:11
当然你应该使用平衡树。你不应该跳过它，这是有用的知识/技能。只是谷歌“AVL树”或“红黑树”，有很多教程。 – Andrey 2010-03-02 19:16:07
我应该跳过它，因为我有截止日期，我现在没有时间学习新东西。我不会因为我想要更有知识或更熟练而失败。我有时间来完成这个项目？并非如此...... – 2010-03-03 12:40:41
我不认为这是建立支持两个按键一个哈希表的方式。
如果您希望SSN查找和名称查找都非常快，那么您需要两个哈希表。你必须记住添加到他们两个，或从他们两个中删除。否则，可以将更频繁的一个（例如SSN查找）作为基于哈希的查找，另一个作为从哈希表进行蛮力查找。
Naah ...如果我使用蛮力查找，我可能会有很低的等级。这个项目的重点在于它针对每种情况使用“最佳”数据结构（我们在前一学期学到的）。只要我们妥善地为他们辩护，我们就可以使用任何东西。正如我所看到的，哈希表是答案（当然我的项目）。 – 2010-03-02 19:16:33
@Nazgulled：谢谢你澄清上下文。似乎最小化时间复杂性是你的目标。但是，根据具体情况，最小化空间复杂性也是一个崇高的目标！ :-)确保你确定你的目标是什么。 – Arun 2010-03-02 19:32:53
像你说的两个哈希表。优点是对于RANDOM数据或甚至实际数据，查找速度非常快。缺点是你不知道你的教授会给你什么（或你呢？），他们可能会迫使最糟糕的情况。
均衡搜索树。我推荐treasures：http://en.wikipedia.org/wiki/Treap - 在我看来，它们是最容易实现的。
对您的用户和二进制搜索进行排序。每个搜索还有O（log N），甚至比treap更容易实现。
散列+排序用户/搜索树的组合，如果你能负担得起内存。这将使它成为O（1）最好的情况和O（log N）最坏的情况。如果H [i] =散列到i的对象列表，则为每个i保留一个计数，告诉您该列表中有多少个对象。如果该计数太大，请改为使用排序的用户列表/搜索树。
他们正在为我们测试我们的程序准备数据样本，但我们还没有访问它。但他们怎么能强迫最好/最坏的情况？这不取决于哈希函数？ – 2010-03-02 19:25:28
它取决于散列函数，但是如果他们有权访问你的散列函数，他们可能会想出测试数据，这将触发其最坏情况的行为。我不认为他们真的会去那些长度，但这是可能的。找到两个映射到散列表中相同位置的不同名称就足够了，然后为您提供100 000个用户的列表，这些用户都具有这两个不同的名称。然后搜索会很慢。为了获得最佳运行时间，您的最佳选择是列表中的＃4。唯一的缺点是使用了内存，但它确实避免了最坏的情况。 – IVlad 2010-03-02 19:34:17
我不认为他们会打扰那么远大声笑......感谢提示虽然:) – 2010-03-02 20:11:52
怎样连接两个键并用作键？
例子我有x，y，z。
Concatanete x和y使用字符串或char作为分隔符。这是一个简单的方法来做到这一点。
在本文中，我看到什么比这更有趣的这个解决方案： Multi-dimensional associative arrays in javascript
你所说的“在图表上使用这些用户”是什么意思？用户是否一次全部给予，然后你必须通过名称/ SSN搜索一堆用户，或者你给了一些用户，然后是一些搜索查询，然后是更多的用户，然后是更多的查询等。 – IVlad 2010-03-02 19:13:18
请永远不要永远使用SSN作为关键:-( – 2010-03-02 19:15:50
不要打扰图表部分，这只是意味着我需要用图表来表示其他的东西，但我无法向你解释什么， m还没有 @Steven为什么不呢？请注意为什么呢？也许，提供一个替代方案？你如何建议我快速查找SSN的用户？ – 2010-03-02 19:23:14