通过小项目重新审视 DSA #1：使用 HashMap 优化电话簿

Source: Dev.to

Introduction

我正在通过为每个主题创建一个小项目来重新学习数据结构与算法（DSA）。这种方法帮助我看到 DSA 概念在实际应用中的运用，并且还能提供可展示的作品。

本系列的第一个项目是 电话簿应用——你可以在这里尝试： https://hashphonebook.netlify.app/

Initial Implementation (Array + Linear Search)

当我第一次构建该应用时，我把联系人存放在一个简单的 JavaScript 数组中，并使用线性搜索：

// Sample data
let userArray = [
    { userName: "Jane", number: "1237893457" },
    { userName: "Oscar", number: "4562317895" }
];

// Linear search (O(n))
const result = userArray.find(contact => contact.userName === "Oscar");

对于只有少量条目的演示来说，这样完全可行，但其时间复杂度是 O(n)。如果电话簿增长到比如 100 000 条联系人，最坏情况下的查找将在真实场景中变得代价高昂。

Why Performance Matters

在紧急情况下，等待一次需要扫描成千上万条记录的搜索是不可接受的。我们需要一种能够提供更快查找的数据结构。

Optimized Implementation (HashMap / Object)

哈希表（或普通的 JavaScript 对象）提供 O(1) 的平均查找时间。通过使用联系人的姓名作为键，我们可以瞬间获取电话号码，无论条目总数多少。

// HashMap representation
let contactMap = {
    "Jane": "1237893457",
    "Oscar": "4562317895"
};

// Constant‑time lookup (O(1))
const number = contactMap["Jane"];

无论我们拥有 5 条联系人还是 50 亿条，查找速度始终保持不变。

Code Changes

Adding a Contact

Before (Array.push):

userArray.push({ userName, contactNumber });

After (Map key‑value):

// Store as a key‑value pair; make the search case‑insensitive
contactMap[userName.toLowerCase()] = {
    originalName: userName,
    number: contactNumber
};

Searching

Before (Array.find):

const result = userArray.find(contact => contact.userName === searchName);

After (Object lookup):

const entry = contactMap[searchName.toLowerCase()];

Takeaway

一段“可运行的代码”并不一定是“好代码”。线性搜索对小型演示足够，但它无法扩展。切换到哈希表使电话簿变得高效，并且能够应对真实世界的使用需求。

这只是我 DSA 复习之旅的第一步，我将继续构建小项目，以巩固每个概念。