已经提出了排序解决方案，但是 排序有点过多 ：我们不需要订单； 我们只需要平等团体 。

因此 散列 就足够了（并且更快）。

1. 对于每种颜色的袜子， 形成一堆 。遍历输入筐中的所有袜子 并将它们分配到颜色堆上 。
2. 遍历每个桩， 并通过其他度量 （例如图案）将其 分配 到第二组桩中
3. 递归应用此方案， 直到将所有袜子分配到 很小的绒头上，然后即可立即进行视觉处理

这种递归哈希分区实际上是由SQL
Server在需要对大型数据集进行哈希联接或哈希聚合时完成的。它将其构建输入流分配到许多独立的分区中。该方案可线性扩展到任意数量的数据和多个CPU。

如果您可以找到一个 提供足够存储桶
的分发密钥（哈希密钥），而每个存储桶足够小，可以非常快速地进行处理，则不需要递归分区。不幸的是，我认为袜子没有这种特性。

如果每个袜子都有一个称为“ PairID”的整数，则可以根据PairID % 10（最后一位）轻松地将它们分配到10个存储桶中。

我能想到的最好的现实分区是创建一个 矩形的桩 ：一个维是颜色，另一个维是图案。为什么是矩形？因为我们需要O（1）对堆的随机访问。（3D
长方体也可以，但这不是很实际。）

更新：

那么 并行性 呢？可以让多个人更快地匹配袜子吗？

1. 最简单的并行化策略是让多名工人从输入筐中取出并将袜子放在堆上。这只会如此之大-想象一下有100个人在10堆土地上进行战斗。 同步成本 （表现为手工冲突和人际交流） 破坏了效率和速度 （请参阅《通用可扩展性法则》！）。这容易造成 僵局 吗？否，因为每个工人一次只需要访问一堆。只有一个“锁”就不会出现死锁。取决于人类如何协调对堆的访问，可能会出现 活锁 。他们可能只是使用随机退避就像网卡在物理级别上所做的那样，以确定哪些卡可以独占访问网络线路。如果它适用于NIC，它也应适用于人类。
2. 如果 每个工人都有自己的桩， 它几乎可以无限扩展。然后，工人可以从输入筐中取出大块的袜子（很少有竞争，因为他们很少这样做），并且在分配袜子时根本不需要同步（因为他们有局部线程堆）。最后，所有工人都需要结合他们的桩组。我相信，如果工人形成一个 聚集树 ，可以用O（log（工人数*每个工人的堆数））来完成。

怎么样的元素明显的问题？如文章所述，可以在中解决元素差异性问题O(N)。袜子问题也是O(N)如此（同样，如果只需要一个分配步骤（我提议多个步骤只是因为人类在计算上很差-
如果分配在一个步骤上就足够了md5(color, length, pattern, ...)，即所有属性的 完美哈希 ））。

显然，没有人能比O(N)这快，所以我们已经达到了 最佳下限 。

尽管输出并不完全相同（在一种情况下，只是布尔值。在另一种情况下，是成对的袜子），则渐进复杂度是相同的。