data-structures - 您将如何设计 MAC 地址表(本质上是快速查找表)？

Question

这是一道与计算机网络相关的编程问题。本质上，每个路由器/交换机都有一个 MAC 地址表，它会查找该表以获取必须在其上转发数据包的接口(interface)端口。该表本身如下所示:

所以基本上给定两个键，vlan 和 mac 地址，在表上进行查找并查找端口的值(最后一列)。在实践中，表可能有数千行，并且需要尽快返回值。所以我的问题是设计这个查找表的最佳方法是什么？面试的时候被问到这个问题，我想到了用哈希表，以vlan和mac地址的组合作为key。但这没有说服力。请为此提出一个好的设计。

Answer 1

对于纯软件解决方案，我也会选择哈希表。但交换机是一种专门的硬件，而且是大批量生产的。因此为它们开发专门的存储硬件是合理的。接下来的事情是，您需要一个类似的 CPU 缓存硬件，因为当您需要从 RAM 中获取某些内容时，您首先需要查明缓存行是否已加载到缓存中。

有了这些知识，您就可以继续wikipedia或发送至this article .

更新:除了搜索 MAC 地址之外，您还必须删除旧条目以防止表变得太大。可能你还没有描述如何做到这一点，并且你期望像 LRU 缓存之类的东西。 LRU可以通过哈希表实现，只需为删除队列添加额外的链表即可。或者，您可以使用棘手的冲突解决策略来创建哈希表，而不是 LRU:具有固定数量的存储桶并限制存储桶大小。如果桶已满，请从桶中扔一些东西。