哈希表会是一个很好的解决方案吗?
判断工厂中的两个工人是否有相同的名字，假设我们有一个未排序的列表，其中包含他们的名字。该列表将包含n个worker。
获取一个有序的列表，假设我们得到一个未排序且包含所有工人姓名的列表。该列表将包含n个worker。
首先，我试着用最坏、最好和平均的情况来对两个陈述进行推理。对于第一个选项，我注意到我们可以有一个使用线性探测实现的哈希表。在这种情况下，我们必须遍历工作者列表，将它们添加到散列表中，如果遇到冲突，就立即停止迭代。这让我声明，最坏的情况将是O(n)和平均情况，最好的情况将是O(1)。
对于第二个选项，我想不出一种方法来完成它，这使我认为哈希表对这个问题没有意义。
因此，我得出结论，第一个问题完全可以使用哈希表来解决，而另一个问题则不行。这听起来对吗?
我可以回答你问题的第一部分:
对于这个问题，哈希表是一个很好的解决方案。但是，您需要一个好的散列函数。你可以用确定工厂中的两个工人是否有相同的名字，假设给定一个未排序的列表，其中包含它们的的名字。该列表将包含n个worker。
polynomial rolling hash function。这里有一个关于散列字符串的更多信息的链接。 https://cp-algorithms.com/string/string-hashing.html
散列的问题在于需要和检查哈希冲突。我建议你遵循Tony在测试哈希函数的评论中给出的建议。
是的，你是对的。在这两种情况下，您的输入都是一个未排序的工人姓名列表，如果您的哈希函数是模糊合理的，则可以将其逐个插入哈希表，平均效率为0(1)。然后，哈希表可以合理地支持哪些函数:
判断工厂中的两个工人是否有相同的名字
这在插入时是很明显的:你会发现这个名字已经在哈希表中了。如果您只需要知道是否存在一个case，您甚至不需要继续插入更多的名称。
获取一个有序的列表
无法按排序顺序遍历哈希表，因此必须从哈希表中提取值。合理的选择包括将它们复制到一个数组中，然后就地排序，并将它们复制到一个平衡的二叉树中——这将使它们在插入和重新平衡树时保持有序。如果要使用数组或平衡二叉树，还不如直接将名称插入该容器中:哈希表步骤将是浪费时间。