现实世界中前端 JavaScript 的数据结构（附 React 代码示例）

数据结构可能令人望而生畏，尤其是对于我们这些自学成才的人来说。如果你已经尝试学习过 JavaScript 中的数据结构，你就会知道通常会发生什么：

一堆 CS 理论被抛给你。
您阅读了手动实现例如链接列表的代码页面。
所有示例都是使用foo和bar或cats和的抽象dogs。

除此之外，您还会遇到如下漂亮的图表：

但如果你已经在前端项目中工作了一段时间，你可能会说：“我从来没在我的前端项目中见过这种情况！” 你说得对，我也没有。

与此同时，你肯定已经使用过一些数据结构。它们不像new HashMap()简单的对象或数组那样显而易见，而是伪装成简单的对象或数组。如果你还没有使用过，那么这是一个很好的入门机会。

在此页面上，我们将

回答您是否应该学习数据结构以及它们何时有用。
查看在实际前端项目中可以找到的一些常见数据结构。

不用担心，你在这里找不到任何数据结构的完整实现。有很多资源涵盖这方面的内容。但你会看到一些你可能在自己的代码中见过，或者可以在你的项目或工作中使用的示例。

作为前端 JavaScript 开发人员，您必须学习数据结构吗？
地图
1. 描述
2. 真实示例：带有用户名的消息
放
1. 描述
2. 真实示例：跟踪选定项目
堆
1. 描述
2. 真实示例：撤消先前的操作
队列
1. 描述
2. 真实示例：通知
树
1. 描述
2. 真实世界的示例：嵌套菜单或注释。

作为前端 JavaScript 开发人员，您必须学习数据结构吗？

这个问题很可能引发争论。以下是两种极端观点：

是的。无论你的技术栈是什么，数据结构对于任何程序员来说都是必不可少的。
“对我来说，所有那些数据结构的东西都是理论垃圾，在我作为 Web 开发人员的 13 多年时间里，我从未真正见过需要这些东西的情况。”

对于很多开发者（尤其是我们当中的自学成才者）来说，第二个答案更令人欣慰。这确实没错，至少部分如此。以下是一些在 JavaScript 前端中找不到许多高级或正式数据结构的原因：

前端的数据集通常不够大，无法看到高级数据结构的好处。
JavaScript 本身甚至不支持许多数据结构。
React（作为最广泛使用的前端框架）无法很好地支持自定义数据结构，因为它需要不可变的状态更新。克隆自定义数据结构可能会抵消任何性能优势。

但正如我所说，“你不需要前端的数据结构”这个答案只是部分正确。

您可能需要了解技术面试的数据结构（重点是可能）。
更重要的是，初级前端开发人员经常犯的一个错误，就是选择了错误的数据结构，这会导致代码非常混乱。 以下是一个例子。

选择合适的数据结构可能会决定代码的质量。它决定了渲染逻辑的外观或数据更新的方式。因此，了解一些选项确实很有帮助。

地图

描述

哈希映射、哈希表或字典本质上是一种键值存储。在 JavaScript 中，我们实际上经常使用它们：

{
  key1: "value 1",
  key2: "value 2",
  key3: "value 3",
}

我们还有一个原生 JavaScript 替代方案，即Map。它有一些方便的方法和属性（例如Map.size），针对按键访问值进行了性能优化，并且允许任何类型作为键（甚至是对象）。

Map 的另一个优点是：对象类型的键会被转换为字符串，如下所示。而 Map 则保留了原始类型。

const numericKeys = {
  1: "value-1",
  2: "value-2",
}

console.log(Object.keys(numericKeys))
// ["1", "2"]

真实示例：带有用户名的消息

在野外，当两个数据集相互引用时，你就能找到地图。就像这个聊天组件一样。

我们有两个数组（消息和用户）。每条消息都通过其字段引用了作者userId。

const messages = [
  {
    id: "message-1",
    text: "Hey folks!",
    userId: "user-1"
  },
  {
    id: "message-2",
    text: "Hi",
    userId: "user-2"
  },
  ...
];

const users = [
  {
    id: "user-1",
    name: "Paul"
  },
  {
    id: "user-2",
    name: "Lisa"
  },
  ...
];

我们在渲染每条消息的时候，都能找到对应的用户。

messages.map(({ id, text, userId }) => {
  const name = users.find((user) => user.id === userId).name;
  return ... // return JSX
}

但从性能角度来看，这并不理想，因为我们必须迭代users每个消息的数组。我们可以使用 map 来代替。

让我们从一个简单的键值对象开始。目标是创建一个如下对象：

{
  "user-1": "Paul",
  "user-2": "Lisa",
  ...
}

我们可以通过Array.reduce()函数实现这一点（在此处找到完整的代码）。

const messages = [
  {
    id: "message-1",
    text: "Hey folks!",
    userId: "user-1"
  },
  ...
];

const users = [
  {
    id: "user-1",
    name: "Paul"
  },
  ...
];

function ChatUsingMap() {
  const namesById = users.reduce(
    (prev, user) => ({ ...prev, [user.id]: user.name }),
    {}
  );

  return messages.map(({ id, text, userId }) => (
    <div key={id}>
      <div>{text}</div>
      <div>{namesById[userId]}</div>
    </div>
  ));
}

或者，我们可以使用真正的 Map。它的构造函数接受一个键值对数组，这样我们就可以省去 reduce 函数（这是 CodeSandbox 上的代码）。

function ChatUsingMap() {
  const namesById = new Map(users.map(({ id, name }) => [id, name]));

  return messages.map(({ id, text, userId }) => (
    <div key={id}>
      <div>{text}</div>
      <div>{namesById.get(userId)}</div>
    </div>
  ));
}

为了清楚起见：我们将这样的数组数组传递给 Map 构造函数：

[
  ["user-1", "Paul"],
  ["user-2", "Lisa"],
  ...
]

放

描述

Set 也是JavaScript 原生支持的带键集合。虽然将 Map 视为对象更容易，但 Set 更像是一个数组。需要注意的是，Set 中的每个值都是唯一的。你不能重复添加一个值。这就是为什么你可能会看到 Set 被用来从数组中删除重复项。

const uniqueValues = [...new Set([1, 1, 2, 3, 3])];
// [1, 2, 3]

与数组相比，主要优点是您可以以高效的方式检查 Set 是否包含某个值。

真实示例：跟踪选定项目

在实际应用中，你可以在追踪用户选择的项目时找到一个集合。如下表所示：

当用户选择一个项目时，我们会将其 ID 添加到集合中来跟踪它。当用户取消选择时，我们会再次将其从集合中移除（代码在 CodeSandbox 上）。

import { useState } from "react";

const rows = [
  {
    id: "id-1",
    name: "Row 1",
  },
  {
    id: "id-2",
    name: "Row 2",
  },
  ...
];

function TableUsingSet() {
  const [selectedIds, setSelectedIds] = useState(new Set());

  const handleOnChange = (id) => {
    const updatedIdToSelected = new Set(selectedIds);
    if (updatedIdToSelected.has(id)) {
      updatedIdToSelected.delete(id);
    } else {
      updatedIdToSelected.add(id);
    }
    setSelectedIds(updatedIdToSelected);
  };

  return (
    <table>
      <tbody>
        {rows.map(({ id, name }) => (
          <tr key={id}>
            <td>
              <input
                type="checkbox"
                checked={selectedIds.has(id)}
                onChange={() => handleOnChange(id)}
              />
            </td>
            <td>{id}</td>
            <td>{name}</td>
          </tr>
        ))}
      </tbody>
    </table>
  );
}

最后说明一下：使用 Set 可以很好地替代数组。你经常会看到的“选择项”功能的一个有问题的实现如下所示：

const [selectedRows, setSelectedRows] = useState(
  rows.map((row) => ({ selected: false }))
);

const handleOnChange = (index) => {
  const updatedSelectedRows = [...selectedRows];
  updatedSelectedRows[index] = !updatedSelectedRows[index];
  setSelectedRows(updatedSelectedRows);
};

这乍一看可能很简单。但通过索引访问元素可能会出现问题。举个例子：如果行可以按不同的顺序排序会发生什么？我们必须保持数组selectedRows同步，并以相同的方式对其进行排序。

如果您想了解迁移到 Set 如何使代码更加清晰和精简，请查看此重构会话。

堆

描述

基本堆栈具有两个特征：

您可以将一个项目添加到堆栈顶部。
您可以从堆栈顶部移除一个项目。

这被称为“后进先出”（又称 LIFO）。听起来可能很复杂，但我们可以用一个简单的数组来实现（因为 JavaScript 原生不支持数组）。

const stack = [];

// add item to the "top"
stack.push("value");

// remove item from the "top"
const topItem = stack.pop();

真实示例：撤消先前的操作

在实际应用中，当你需要追踪用户交互的历史记录以构建撤销功能时，堆栈就派上用场了。就像这张表中，用户可以删除每一行。

每当用户从表中删除一行时，我们都会将其添加到history数组（堆栈）中。当用户想要撤消删除操作时，我们会从历史记录中获取最新行并将其重新添加到表中。部分函数未在下方显示，但您可以在 CodeSandbox 上找到完整代码。

注意，我们不能只使用Array.push()and Array.pop()，因为 React 需要不可变数据。相反，我们使用Array.concat()and ，Array.slice()因为它们都返回新的数组。

import { useReducer } from "react";

const rows = [
  {
    id: "id-1",
    name: "Row 1",
  },
  {
    id: "id-2",
    name: "Row 2",
  },
  ...
];

// "history" is our stack
const initialState = { rows, history: [] };

function reducer(state, action) {
  switch (action.type) {
    case "remove":
      return {
        rows: removeRow(state, action),
        // Array.concat() as immutable alternative to Array.push()
        history: state.history.concat({
          action,
          row: state.rows[action.index]
        })
      };
    case "undo":
      return {
        rows: addRowAtOriginalIndex(state),
        // Array.slice() as immutable alternative to Array.pope()
        history: state.history.slice(0, -1)
      };
    default:
      throw new Error();
  }
}

function TableUsingStack() {
  const [state, dispatch] = useReducer(reducer, initialState);

  return (
    <>
      <button
        onClick={() => dispatch({ type: "undo" })}
        disabled={state.history.length === 0}
      >
        Undo Last Action
      </button>

      <table>
        <thead>
          <tr>
            <th>ID</th>
            <th>Name</th>
            <th></th>
          </tr>
        </thead>

        <tbody>
          {state.rows.map(({ id, name }, index) => (
            <tr key={id}>
              <td>{id}</td>
              <td>{name}</td>
              <td>
                <button onClick={() => dispatch({ type: "remove", id, index })}>
                  Delete
                </button>
              </td>
            </tr>
          ))}
        </tbody>
      </table>
    </>
  );
}

正如评论中提到的，history这就是我们的堆栈。当用户点击“移除”按钮时，我们会将操作以及一些额外的数据添加到历史记录中。然后，“撤消上一个操作”按钮会从堆栈中移除最新的操作history，并将该行重新添加到数据中。

队列

描述

队列与堆栈非常相似。不同的是，我们移除的是第一个添加到队列的元素，而不是最后一个添加的元素。这被称为“先进先出”（又称 FIFO）。

就像超市里的排队一样。

我们可以使用一个简单的数组再次实现它，因为它在 JavaScript 中不受原生支持。

const queueu = [];

// add item to the "end"
queueu.push("value");

// remove item from the "beginning"
const firstItem = queueu.shift();

真实示例：通知

在现实生活中，当你看到一堆通知叠加在一起时，你就会发现它们之间形成了队列。你知道，就是那种从屏幕底部弹出，过一会儿就消失的通知。

在这种情况下，每当用户加入我们的虚拟社区时，就会弹出通知。

每当我们点击按钮时，就会有一条消息添加到notifications数组（我们的队列）中。此外，还会设置一个超时时间，用于再次移除队列中的第一个通知。你可以在 CodeSandbox 上找到完整的代码。

import { faker } from "@faker-js/faker";
import { useState } from "react";

function ButtonAddingNotifications() {
  const [notifications, setNotifications] = useState([]);

  const addNotification = () => {
    setNotifications((previous) => {
      // use Array.concat() as immutable alternative to Array.push()
      return previous.concat(`${faker.name.firstName()} joined!`);
    });
    setTimeout(() => {
      // use Array.slice() as immutable alternative to Array.shift()
      setNotifications((previous) => previous.slice(1));
    }, 1000);
  };

  return (
    <>
      <button onClick={() => addNotification()}>
        Invite User To Community
      </button>

      <aside>
        {notifications.map((message, index) => (
          <p key={index}>{message}</p>
        ))}
      </aside>
    </>
  );
}

树

描述

树是一种嵌套的数据结构。它始于一个父节点，父节点包含子节点。子节点又可以拥有自己的子节点，以此类推。在树中，你经常会发现递归函数。

下面是一个使用嵌套对象的示例：

{
  name: "Parent",
  children: [
    {
      name: "Child 1",
    },
    {
      name: "Child 2",
      children: [
        {
          name: "Grandchild 21",
        }
      ]
    }
  ]
}

定义树有很多不同的方法。除了上述结构之外，我们还可以使用平面数组。在这种情况下，所有元素都需要一个 ID 并相互引用。

[
  {
    id: "parent-1",
    name: "Parent",
    // references to children via their IDs
    children: ["child-1", "child-2"]
  },
  {
    id: "child-1",
    // reference to the parent vid its ID
    name: "Child 1",
    parent: "parent-1"
  },
  {
    id: "child-2",
    name: "Child 2",
    parent: "parent-1",
    children: ["grandchild-2"]
  },
  {
    id: "grandchild-21",
    name: "Grandchild 21",
    parent: "child-2"
  }
]

从人类的角度来看，奇怪的是每个子元素只能有一个父元素。正因如此，你经常会看到“节点”（即任意元素）、“子元素”和“边”（两个元素之间的连接）等术语。

真实世界的示例：嵌套菜单或注释。

如上所述，树是嵌套的数据结构。当您在后端（例如 CMS）中定义嵌套菜单时，您可以找到它们。

另一个常见的例子是嵌套评论，你可以在许多博客或 Reddit 上看到它们。此组件以递归方式渲染一个嵌套的树形结构，其中包含以下内容（完整代码在 CodeSandbox 上）。

const menuItems = [
  {
    text: "Menu 1",
    children: [
      {
        text: "Menu 1 1",
        href: "#11",
      },
      {
        text: "Menu 1 2",
        href: "#12",
      },
    ],
  },
  {
    text: "Menu 2",
    href: "#2",
  },
  {
    text: "Menu 3",
    children: [
      {
        text: "Menu 3 1",
        children: [
          {
            id: "311",
            text: "Menu 3 1 1",
            href: "#311",
          },
        ],
      },
    ],
  },
];

// Menu and MenuItem are recursively calling each other
function Menu({ items }) {
  return (
    <ul>
      {items.map((item, index) => (
        <MenuItem key={index} {...item} />
      ))}
    </ul>
  );
}

function MenuItem({ text, href, children }) {
  // the break condition: 
  // stop recursion if the item doesn't have children
  if (!children) {
    return (
      <li>
        <a href={href}>{text}</a>
      </li>
    );
  }

  // recursively create a submenu
  return (
    <li>
      {text}
      <Menu items={children} />
    </li>
  );
}

// the root component
function NestedMenu() {
  return <Menu items={menuItems} />;
}

上面的嵌套树结构对人类来说非常易于阅读，渲染也很简单。但如果我们需要更新数据，很快就会遇到问题。尤其是当我们需要以不可变的方式更改数据时（就像我们必须使用 React 状态一样）。

在这种情况下，一个很好的替代方案是使用扁平数组来代替上面的嵌套对象。这会给前端逻辑带来一些负担，因为我们必须解析 ID 引用。但它非常易于交互，并且后端可能也更容易处理。

const menuItems = [
  {
    id: "1",
    text: "Menu 1",
    children: ["11", "12"],
    isRoot: true,
  },
  {
    id: "11",
    text: "Menu 1 1",
    href: "#11",
  },
  {
    id: "12",
    text: "Menu 1 2",
    href: "#12",
  },
  {
    id: "2",
    text: "Menu 2",
    href: "#2",
    isRoot: true,
  },
  {
    id: "3",
    text: "Menu 3",
    children: ["31"],
    isRoot: true,
  },
  {
    id: "31",
    text: "Menu 3 1",
    children: ["311"],
  },
  {
    id: "311",
    text: "Menu 3 1 1",
    href: "#311",
  },
];

function Menu({ itemIds, itemsById }) {
  return (
    <ul>
      {itemIds.map((id) => (
        <MenuItem key={id} itemId={id} itemsById={itemsById} />
      ))}
    </ul>
  );
}

function MenuItem({ itemId, itemsById }) {
  const item = itemsById[itemId];
  if (!item.children) {
    return (
      <li>
        <a href={item.href}>{item.text}</a>
      </li>
    );
  }
  return (
    <li>
      {item.text}
      <Menu itemIds={item.children} itemsById={itemsById} />
    </li>
  );
}

function NestedMenu() {
  const itemsById = menuItems.reduce(
    (prev, item) => ({ ...prev, [item.id]: item }),
    {}
  );
  const rootIds = menuItems.filter(({ isRoot }) => isRoot).map(({ id }) => id);
  return <Menu itemIds={rootIds} itemsById={itemsById} />;
}

请注意，递归函数非常优雅，但对于非常深层的嵌套树，可能会超出 JavaScript 引擎的调用堆栈大小。以下示例在递归深度达到 10962 时抛出错误：

在我们的例子中，我们不会遇到这个问题，因为我们不会嵌套数千个菜单项。

链接：https://dev.to/jkettmann/data-structures-in-frontend-javascript-in-the-real-world-with-react-code-examples-3506

现实世界中前端 JavaScript 的数据结构（附 React 代码示例）

现实世界中前端 JavaScript 的数据结构（附 React 代码示例）

目录

作为前端 JavaScript 开发人员，您必须学习数据结构吗？

地图

描述

真实示例：带有用户名的消息

放

描述

真实示例：跟踪选定项目

堆

描述

真实示例：撤消先前的操作

队列

描述

真实示例：通知

树

描述

真实世界的示例：嵌套菜单或注释。