什么是不可变数据结构

不可变数据结构指的是一个变量，其引用的数据不会发生改变。一旦 a = { count: 1} 这个引用关系确立，在任何时候 a 恒等于 { count: 1}， 不允许修改 a 引用的数据结构，例如禁止 a.count = 2 这种操作。

一、什么是不可变数据结构

不可变数据结构指的是一个变量，其引用的数据不会发生改变。一旦 a = { count: 1} 这个引用关系确立，在任何时候 a 恒等于 { count: 1}， 不允许修改 a 引用的数据结构，例如禁止 a.count = 2 这种操作。在计算机科学中，不可变数据结构是指一旦创建后就不能被更改的数据结构。也就是说，不可变对象具有固定的值和状态，任何修改都会生成一个新的对象，而不是在原有对象上直接进行修改。例如，Python 中的元组（tuple）即为不可变对象，一旦创建后就不能再添加、删除、修改元素。类似地，Java 中的字符串（String）也是不可变的，一旦创建后就不能再改变其内容。不可变数据结构相对于可变数据结构，具有以下一些优点：

1. 线程安全：由于不可变对象不可被修改，因此可以保证在多线程环境下的线程安全性。
2. 简化代码：不可变数据结构可以避免程序中的副作用，从而简化代码设计和实现。
3. 缓存友好：由于不可变对象的值不会发生改变，因此可以方便地缓存其 hash 值，提高查找效率。
4. 适合函数式编程：函数式编程中不可变数据结构被广泛使用，因为它们可以使得函数更加纯粹、无副作用。

需要注意的是，不可变数据结构并不适合所有的场景，例如需要频繁添加、删除、修改元素的场景，使用不可变数据结构会造成大量的内存分配和对象复制，从而影响性能。在实际应用中需要根据具体情况选择使用可变或不可变数据结构。

二、实现不可变数据结构

不可变数据结构有三种实现思路:

1、靠约定实现

也是目前React中常见的编码方式，约定所有修改操作都不会改动原始对象。例如下面的操作：

const state = { count: 1 }
const newState = { ...state, count: 2 };

在 React 中我们每次 setState 都是使用 this.setState(newState) ，每次修改state都是创建了一个新对象，而不是在原始对象上修改，所以达到了对象不可变的目的。

2、强制实现，借助第三方库 immutable.js

靠约定实现的优点是只是编码思想的转变，并没有外来的侵入。但是无法保证所有人严格遵守，容易出bug。所以有一些强制方案。以 immutable.js 为例：

// 我们规定，所有的 object 都使用 immutable.js 提供的 Map 对象
import { Map } from 'immutable.js'

const map = Map({ a: 1, b: 2 });
const newMap = map.set('a', 3);

3、强制实现，借助 immer

在 immutable.js 中修改数据只能通过 set 方法来更改，更改之后会返回一个新的引用对象，指向修改后的对象，以此达到强制数据不可变的效果。但是这种风格强制性较强，一开始使用很容易不适应，而且不仅仅是修改数据，就算取数据也变得很繁琐。

所以后来又出现了 immer，一款自由style的不可变工具库，代码风格如下：

import produce from "immer"

const baseState = [
    {
        todo: "Learn typescript",
        done: true
    },
    {
        todo: "Try immer",
        done: false
    }
]

const nextState = produce(baseState, draftState => {
    draftState.push({todo: "Tweet about it"})
    draftState[1].done = true
})

在支持Proxy的浏览器上 immer 使用 Proxy 实现修改的拦截，而不是简单的深拷贝，所以性能优于普通对象深拷贝，使用上比 immutable.js 更方便。

三、数据结构

1、简介

数据结构是一种具有一定逻辑关系，在计算机中应用某种存储结构，并且封装了相应操作的数据元素集合。它包含三方面的内容，逻辑关系、存储关系及操作。不同种类的数据结构适合于不同种类的应用，而部分甚至专门用于特定的作业任务。例如，计算机网络依赖于路由表运作，B 树高度适用于数据库的封装。随着应用程序变得越来越复杂和数据越来越丰富，几百万、几十亿甚至几百亿的数据就会出现，而对这么大对数据进行搜索、插入或者排序等的操作就越来越慢，数据结构就是用来解决这些问题的。

2、常见的数据结构

• 栈（Stack）：栈是一种特殊的线性表，它只能在一个表的一个固定端进行数据结点的插入和删除操作。
• 队列（Queue）：队列和栈类似，也是一种特殊的线性表。和栈不同的是，队列只允许在表的一端进行插入操作，而在另一端进行删除操作。
• 数组（Array）：数组是一种聚合数据类型，它是将具有相同类型的若干变量有序地组织在一起的集合。
• 链表（Linked List）：链表是一种数据元素按照链式存储结构进行存储的数据结构，这种存储结构具有在物理上存在非连续的特点。
• 树（Tree）：树是典型的非线性结构，它是包括，2 个结点的有穷集合 K。
• 图（Graph）：图是另一种非线性数据结构。在图结构中，数据结点一般称为顶点，而边是顶点的有序偶对。
• 堆（Heap）：堆是一种特殊的树形数据结构，一般讨论的堆都是二叉堆。
• 散列表（Hash table）：散列表源自于散列函数(Hash function)，其思想是如果在结构中存在关键字和T相等的记录，那么必定在F(T)的存储位置可以找到该记录，这样就可以不用进行比较操作而直接取得所查记录。

3、常用算法

数据结构研究的内容：就是如何按一定的逻辑结构，把数据组织起来，并选择适当的存储表示方法把逻辑结构组织好的数据存储到计算机的存储器里。算法研究的目的是为了更有效的处理数据，提高数据运算效率。数据的运算是定义在数据的逻辑结构上，但运算的具体实现要在存储结构上进行。一般有以下几种常用运算：

• 检索：检索就是在数据结构里查找满足一定条件的节点。一般是给定一个某字段的值，找具有该字段值的节点。
• 插入：往数据结构中增加新的节点。
• 删除：把指定的结点从数据结构中去掉。
• 更新：改变指定节点的一个或多个字段的值。
• 排序：把节点按某种指定的顺序重新排列，例如递增或递减。

延伸阅读1：编程语言简介

和我们日常使用的中文、英语一样，编程语言也是一门用于沟通的语言。只不过“编程语言”是和计算机沟通的语言。而“程序”， 就是使用计算机能够理解的语言书写的一连串命令。而“编程”就是我们为了完成某项任务，将解决问题的步骤，用计算机能够理解的语言写成指令，这就是“编程”。而后，计算机会根据这些指令一步步执行，最后完成任务。