language-agnostic - 实现电话地址簿 - 反向索引

Question

现在我正试图想出一个数据结构来实现电话地址簿。假设有两个信息:姓名、电话号码。同一个名字可以有多个号码。现在我想提出一个数据结构，它可以帮助我获取给定名称的数字并获取名称和给定的数字。我必须在尽可能短的时间内完成这项工作。我正在考虑维护一个映射(名称到数字)，然后对于给定的数字以某种方式将索引反向索引到该映射中，然后找到名称。我不太确定最好的方法是什么。你能建议一个理想的数据结构吗？将使用一些反向索引帮助。如果是，那么我如何在这种情况下使用它。

Answer 1

我会维护两个(哈希)映射。

第一个映射将以名称作为键，将集合(或列表或向量)作为值，该列表将包含特定人员的所有电话号码。

Map<String,Set<String>> NamesToNumbers;

第二张 map 将电话号码作为键，姓名作为值。

Map<String,String> NumbersToNames;

此外，我将创建一个简单的类，将这两个映射作为私有(private)成员，该类的目的是使两个映射保持同步，并将所有 put()、remove() 等调用传递给两个映射采用正确的键/值格式。

如何在简单类中编写 put() 方法的伪代码:

public void put(String Name,String PhoneNumber)
{

Set NumbersForName = NamesToNumbers.get(Name);
if (NumbersForName == null)
  {
    NumbersForName = new Set();
    NamesToNumbers.put(Name,NumbersForName);
  }

NumbersForName.put(PhoneNumber);
NumbersToNames.put(PhoneNumber,Name);  

}

查找的成本将是 O(1)，插入的成本将是 O(1)，除非存在哈希冲突。

如果您使用的是 Java 5+，您应该查看 Google Collections ，他们有一个漂亮的 Bi-map 类，这基本上就是我想要描述的。