《数据结构》

程序设计 = 数据结构 + 算法。

数据结构是为算法服务的，算法要作用在特定的数据结构之上。

绪

基本概念和术语

数据（data）：数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素（data element）：数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
数据项（data item）：有时一个数据元素由若干个数据项组成，数据项是数据的不可分割的最小单位。
数据对象（data object）：数据对象是性质相同的数据元素的集合，是数据的一个子集。
数据结构（data structure）：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
结构（structure）：数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构。

data item

四种数据结构：

集合结构：集合中的数据元素除了属于同一个类型外，没有其他关系。（散列表）
线性结构：线性结构中元素之间存在一对一关系。（数组，堆栈，队列，链表）
树形结构：树形结构中元素之间存在一对多关系。（树，字典树）
图状结构（网状结构）：网状结构中元素之间存在多对多关系。（图）

树形结构和网状结构统称为非线性结构。

datastructures

数据结构的形式定义为：数据结构是一个二元组

1	Data Structure = (D, S)

其中D是数据元素的有限集，S是D上关系的有限集。

逻辑结构：结构定义中的”关系“描述的是数据元素之间的逻辑关系，因此又称为数据的逻辑结构。
物理结构（存储结构）：数据结构在计算机中的表示（又称映像），它包括数据元素的表示和关系的表示。
元素（element）/节点（node）：在计算机中，我们可以用一个若干位组合起来形成的一个位串表示一个数据元素（如用一个字长的位串表示一个整数，用8位二进制数表示一个字符），通常称这个位串为元素或节点。
数据域（data field）：当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串称为数据域。

数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。

顺序映像的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。
非顺序映像的特点是借助指示元素存储地址的指针（pointer）表示数据元素之间的逻辑关系。

顺序存储结构和链式存储结构的区别

链表存储结构的内存地址不一定是连续的，但顺序存储结构的内存地址一定是连续的；
链式存储适用于在较频繁地插入、删除、更新元素时，而顺序存储结构适用于频繁查询时使用。

顺序存储结构：
serial structure

链式存储结构：
link structure

数组需要一块连续的内存空间来存储，对内存的要求比较高。如果我们申请一个100MB大小的数组，当内存中没有连续的、足够大的存储空间时，即便内存的剩余总可用空间大于100MB，仍然会申请失败。
而链表恰恰相反，它不需要连续的内存空间，而是通过“指针”将一组零散的内存块串联起来。不过，链表仍会受到可用内存总量和节点额外开销的限制。

顺序存储结构和链式存储结构的优缺点：

空间上：顺序比链式节约空间。是因为链式结构每一个节点都有一个指针存储域。
存储操作上：顺序支持随机存取，方便操作。
插入和删除上：链式的要比顺序的方便（因为插入的话顺序表也很方便，问题是顺序表的插入要执行更大的空间复杂度，包括一个从表头索引以及索引后的元素后移，而链表是索引后，插入就完成了）。

任何一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采用的存储结构。

如C语言中一维数组类型来描述顺序存储结构，指针来描述链式存储结构。

**数据类型（data type）**是一个值的集合和定义在这个值集上的一组操作的总称。如 C 语言中的整型变量，其值集为某个区间上的整数，定义在其上的操作为加、减、乘、除和取模等算术运算。

**抽象数据类型（Abstract Data Type，简称ADT）**是指一个数学模型以及定义在该模型上的一组操作。

抽象数据类型的软件模块通常应包含定义、表示和实现3个部分。若按其值的不同特性，可细分为下列3种类型：

原子类型（atomic data type）：属原子类型的变量的值是不可分解的。
固定聚合类型（fixed-aggregate data type）：属该类型的变量，其值由确定数目的成分按某种结构组成。
可变聚合类型（variable-aggregate data type）：该类型值的成分的数目不确定。

抽象数据类型可用以下三元组表示

(D, S, P)

其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。

抽象数据类型的标准格式：

ADT 抽象数据类型名
Data
	数据元素之间逻辑关系的定义

Operation
	操作 1
		初始条件
		操作结果描述
	操作 2
		...
	操作 n
		...

**多形数据类型（polymorphic data type）**是指其值的成分不确定的数据类型。

算法和算法分析

**算法（algorithm）**是对特定问题求解步骤的一种描述，它是指令的有限序列。一个算法具有下列5个重要特性：

有穷性
确定性
可行性
输入
输出

一个好的算法要求

正确性
可读性
健壮性
效率与低存储量需求

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作

1	T(n) = O(f(n))

它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称做算法的渐进时间复杂度（asymptotic time complexity），简称时间复杂度。
语句的频度（frequency count）指的是该语句重复执行的次数。O(1)、O(n)、O(n^2)、O(log n)、O(2^n)分别称为常量阶、线性阶、平方阶、对数阶和指数阶。

类似于算法的时间复杂度，空间复杂度（space complexity）是算法所需存储空间的量度，记作

1	S(n) = O(f(n))

数据结构

数据结构是在计算机中组织和存储数据的一种特殊方式，使得数据可以高效地被访问和修改。也就是说，数据结构是数据值的集合，表示数据之间的关系，也包括了作用在数据上的函数或操作。

八大常见的数据结构

数组：Array
堆栈：Stack
队列：Queue
链表：Linked Lists
树：Trees
图：Graphs
字典树：Trie
散列表（哈希表）：Hash Tables

在较高的层次上，基本上有三种类型的数据结构:

堆栈和队列是类似于数组的结构，仅在项目的插入和删除方式上有所不同。
链表，树，和图结构的节点是引用到其他节点。
散列表依赖于散列函数来保存和定位数据。

在复杂性方面：

堆栈和队列是最简单的，并且可以从中构建链表。
树和图是最复杂的，因为它们扩展了链表的概念。
散列表和字典树需要利用这些数据结构来可靠地执行。

就效率而言：

链表是记录和存储数据的最佳选择
而哈希表和字典树在搜索和检索数据方面效果最佳。

数组：Array

最简单的数据结构，如

[1, 'a']

堆栈：Stack

stack LIFO

堆栈是元素的集合，可以在顶部添加项目，我们有几个实际的堆栈示例：

浏览器历史记录
撤消操作
递归以及其它。

解释堆栈：

两个主要操作：push 和 pop。push 将元素添加到栈顶，而 pop 从栈顶删除元素。
遵循”Last In，First Out”，即：LIFO，后进先出。

堆栈的实现

class Stack {
    constructor(...items) {
        this.reverse = false;
        this.stack = [...items];
    }

    push(...items) {
        return this.reverse
            ? this.stack.unshift(...items)
            : this.stack.push(...items);
    }
    
    pop() {
        return this.reverse ? this.stack.shift() : this.stack.pop();
    }
}

const stack = new Stack(4, 5);
stack.reverse = true;
console.log(stack.push(1, 2, 3) === 5) // true
console.log(JSON.stringify(stack.stack) === JSON.stringify([1, 2, 3, 4, 5])) // true

队列：Queue

在计算机科学中，一个队列(queue)是一种特殊类型的抽象数据类型或集合。集合中的实体按顺序保存。

quene FIFO

在前端开发中，最常见的队列应用当属浏览器和 Node.js 中的宏任务、微任务及任务队列。这里不再赘述。在后端领域，消息队列也应用广泛，如 RabbitMQ、ActiveMQ 等。

以编程思想而言，Queue可以用两句话描述：

只是具有两个主要操作的数组：unshift和pop。
遵循 “First In, First Out”，即 FIFO（先进先出）。

quene FIFO

队列的实现

class Queue {
    constructor(...items) {
        this.reverse = false;
        this.queue = [...items];
    }

    enqueue(...items) {
        return this.reverse
            ? this.queue.push(...items)
            : this.queue.unshift(...items);
    }

    dequeue() {
        return this.reverse ? this.queue.shift() : this.queue.pop();
    }
}

链表：Linked Lists

与数组一样，链表是按顺序存储数据元素。

链表不是保留索引，而是指向其他元素。
linkedLists

第一个节点称为头部(head)，而最后一个节点称为尾部(tail)。

单链表与双向链表：

单链表是表示一系列节点的数据结构，其中每个节点指向列表中的下一个节点。
链表通常需要遍历整个操作列表，因此性能较差。
提高链表性能的一种方法是在每个节点上添加指向列表中上一个节点的第二个指针。
双向链表具有指向其前后元素的节点。

链表的优点：

链接具有常量时间插入和删除，因为我们可以只更改指针。
与数组一样，链表可以作为堆栈运行。

链表的应用场景：

链接列表在客户端和服务器上都很有用。

在客户端上，像Redux就以链表方式构建其中的逻辑。
在服务器上，像Express这样的Web框架也以类似的方式构建其中间件逻辑。当请求被接收时，它从一个中间件管道输送到下一个，直到响应被发出。
React 核心算法 React Fiber的实现就是链表。(React 16)。React Fiber之前的Stack Reconciler，是自顶向下的递归mount/update，无法中断(持续占用主线程)，这样主线程上的布局、动画等周期性任务以及交互响应就无法立即得到处理，影响体验；React Fiber解决过去Reconciler存在的问题的思路是把渲染/更新过程(递归diff)拆分成一系列小任务，每次检查树上的一小部分，做完看是否还有时间继续下一个任务，有的话继续，没有的话把自己挂起，主线程不忙的时候再继续。

reactFiber

单链表实现

push(value) - 在链表的末尾/头部添加一个节点
pop() - 从链表的末尾/头部删除一个节点
get(index) - 返回指定索引处的节点
delete(index) - 删除指定索引处的节点
isEmpty() - 根据列表长度返回true或false
print() - 返回链表的可见表示

class Node {
  constructor(data) {
    this.data = data
    this.next = null
  }
}

class LinkedList {
  constructor() {
    this.head = null
    this.tail = null
    // 长度非必要
    this.length = 0
  }
  push(data) {
    // 创建一个新节点
    const node = new Node(data)
    // 检查头部是否为空
    if (this.head === null) {
      this.head = node
      this.tail = node
    } 
    this.tail.next = node
    this.tail = node
    this.length++
  }
  pop(){
    // 先检查链表是否为空
    if(this.isEmpty()) {
      return null
    } 
    // 如果长度为1
    if (this.head === this.tail) {
      this.head = null
      this.tail = null
      this.length--
      return this.tail
    }
    let node = this.tail
    let currentNode = this.head
    let penultimate
    
    while (currentNode) {
      if (currentNode.next === this.tail) {
        penultimate = currentNode
        break
      }
      currentNode = currentNode.next
    }
    
    penultimate.next = null
    this.tail = penultimate
    this.length --
    return node
  }
  
  get(index){
    // 处理边界条件
    if (index === 0) {
      return this.head
    }
    if (index < 0 || index > this.length) {
      return null
    }
    
    let currentNode = this.head
    let i = 0
    while(i < index) {
      i++
      currentNode = currentNode.next
    }
    return currentNode
    
  }
  delete(index){
    let currentNode = this.head
    
    if (index === 0) {
      let deletedNode
      currentNode.next = this.head
      deletedNode = currentNode
      this.length--
      
      return deletedNode
    }
    
    if (index < 0 || index > this.length) {
      return null
    }
    
    let i = 0
    let previous
    
    while(i < index) {
      i++
      previous = currentNode
      currentNode = currentNode.next
    }
    previous.next = currentNode.next
    this.length--
    return currentNode
  }
  
  isEmpty() {
    return this.length === 0
  }
  print() {
    const list = []
    let currentNode = this.head
    while(currentNode){
      list.push(currentNode.data)
      currentNode = currentNode.next
    }
    return list.join(' => ')
  }
}

双向链表实现

类似于单链表，双向链表由一系列节点组成。每个节点包含一些数据以及指向列表中下一个节点的指针和指向前一个节点的指针。这是JavaScript中的简单表示：

class Node {
    constructor(data) {
        // data 包含链表项应存储的值
        this.data = data;
        // next 是指向列表中下一项的指针
        this.next = null;
        // prev 是指向列表中上一项的指针
        this.prev = null;
    }
}

doublelinkedLists

树：Trees

计算机中经常用到的一种非线性的数据结构——树（Tree），由于其存储的所有元素之间具有明显的层次特性，因此常被用来存储具有层级关系的数据，比如文件系统中的文件；也会被用来存储有序列表等。

在树结构中，每一个结点只有一个父结点，若一个结点无父节点，则称为树的根结点，简称树的根（root）。
每一个结点可以有多个子结点。
没有子结点的结点称为叶子结点。
一个结点所拥有的子结点的个数称为该结点的度。
所有结点中最大的度称为树的度。树的最大层次称为树的深度。

树的分类

常见的树分类如下，其中我们掌握二叉搜索树即可。

二叉树：Binary Tree
AVL树：AVL Tree
红黑树：Red-Black Tree
线段树： Segment Tree - with min/max/sum range queries examples
芬威克树：Fenwick Tree (Binary Indexed Tree)

树的应用

DOM树。每个网页都有一个树数据结构。
Vue和React的Virtual DOM也是树。

二叉树：Binary Tree

二叉树是一种特殊的树，它的子节点个数不超过两个。
且分别称为该结点的左子树（left subtree）与右子树（right subtree）。
二叉搜索树（Binary Search Tree，BST）是二叉树的一种，也称二叉查找树或二叉排序树。

binarytree

二叉树的遍历

按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次，这个操作被称为树的遍历，是对树的一种最基本的运算。
由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。
按照根节点访问的顺序不同，二叉树的遍历分为以下三种：前序遍历，中序遍历，后序遍历；

前序遍历：Pre-Order

根节点->左子树->右子树

pre-binarytree

中序遍历：In-Order

左子树->根节点->右子树

in-binarytree

后序遍历：Post-Order

左子树->右子树->根节点

post-binarytree

因此可以得出上面二叉树的遍历结果如下：

前序遍历：ABDEFGC
中序遍历：DEBGFAC
后序遍历：EDGFBCA

二叉树的实现

class Node { 
  constructor(data) { 
    this.left = null
    this.right = null
    this.value = data
  } 
} 

class BST {
    constructor() {
        this.root = null
    }
    // 二叉树的各种操作
    // insert(value) {...}
    // insertNode(root, newNode) {...}
    // ...

insertNode& insert：插入新子节点/节点

  insertNode(root, newNode) {
    if (newNode.value < root.value) {
      // 先执行无左节点操作
      (!root.left) ? root.left = newNode : this.insertNode(root.left, newNode)
    } else {
      (!root.right) ? root.right = newNode : this.insertNode(root.right, newNode)
    }
  }
  
insert(value) {
    let newNode = new Node(value)
    // 如果没有根节点
    if (!this.root) {
      this.root = newNode
    } else {
      this.insertNode(this.root, newNode)
    }
}

removeNode& remove：移除子节点/节点

  removeNode(root, value) {
    if (!root) {
      return null
    }
    
    // 从该值小于根节点开始判断
    if (value < root.value) {
      root.left = this.removeNode(root.left, value)
      return root
    } else if (value > root.value) {
      root.right = tis.removeNode(root.right, value)
      return root
    } else {
      // 如果没有左右节点
      if (!root.left && !root.right) {
        root = null
        return root
      }
      
      // 存在左节点
      if (root.left) {
        root = root.left
        return root
      // 存在右节点
      } else if (root.right) {
        root = root.right
        return root
      }
      
      // 获取正确子节点的最小值以确保我们有有效的替换
      let minRight = this.findMinNode(root.right)
      root.value = minRight.value
      // 确保删除已替换的节点
      root.right = this.removeNode(root.right, minRight.value)
      return root
    }
  }
  
remove(value) {
    if (!this.root) {
      return 'Tree is empty!'
    } else {
      this.removeNode(this.root, value)
    }
}

findMinNode:获取子节点的最小值

findMinNode(root) {
    if (!root.left) {
      return root
    } else {
      return this.findMinNode(root.left)
    }
}

searchNode & search：查找子节点/节点

searchNode(root, value) {
    if (!root) {
      return null
    }
    
    if (value < root.value) {
      return this.searchNode(root.left, value)
    } else if (value > root.value) {
      return this.searchNode(root.right, value)
    }
    
    return root
}

search(value) {
    if (!this.root) {
      return 'Tree is empty'
    } else {
      return Boolean(this.searchNode(this.root, value))
    }
}

Pre-Order：前序遍历

preOrder(root) {
    if (!root) {
      return 'Tree is empty'
    } else {
      console.log(root.value)
      this.preOrder(root.left)
      this.preOrder(root.right)
    }
  }

In-Order：中序遍历

inOrder(root) {
    if (!root) {
      return 'Tree is empty'
    } else {
      this.inOrder(root.left)
      console.log(root.value)
      this.inOrder(root.right)
    }
  }

Post-Order：后序遍历

postOrder(root) {
    if (!root) {
      return 'Tree is empty'
    } else {
      this.postOrder(root.left)
      this.postOrder(root.right)
      console.log(root.value)
    }
}

图：Graph

图是由具有边的节点集合组成的数据结构。图可以是定向的或不定向的。

图的介绍

Graph

图的应用

在以下场景中，你都使用到了图：

使用搜索服务，如Google，百度。
使用LBS地图服务，如高德，谷歌地图。
使用社交媒体网站，如微博，Facebook。

图用于不同的行业和领域：

GPS系统和谷歌地图使用图表来查找从一个目的地到另一个目的地的最短路径。
社交网络使用图表来表示用户之间的连接。
Google搜索算法使用图来确定搜索结果的相关性。
运营研究是一个使用图来寻找降低运输和交付货物和服务成本的最佳途径的领域。
甚至化学使用图来表示分子！

图，可以说是应用最广泛的数据结构之一，真实场景中处处有图。

图的构成

图表用于表示，查找，分析和优化元素（房屋，机场，位置，用户，文章等）之间的连接。

图的基本元素

节点：Node，比如地铁站中某个站/多个村庄中的某个村庄/互联网中的某台主机/人际关系中的人.
边：Edge，比如地铁站中两个站点之间的直接连线, 就是一个边。

GraphElement

符号和术语

|V|=图中顶点（节点）的总数。
|E|=图中的连接总数（边）。

GraphVal

有向图与无向图

图根据其边（连接）的特征进行分类。

有向图
在有向图中，边具有方向。它们从一个节点转到另一个节点，并且无法通过该边返回到初始节点。
如下图所示，边（连接）现在具有指向特定方向的箭头。将这些边视为单行道。您可以向一个方向前进并到达目的地，但是你无法通过同一条街道返回，因此您需要找到另一条路径。

dir-Graph

无向图
在这种类型的图中，边是无向的（它们没有特定的方向）。将无向边视为双向街道。您可以从一个节点转到另一个节点并返回相同的“路径”。

nodir-Graph

加权图
在加权图中，每条边都有一个与之相关的值（称为权重）。该值用于表示它们连接的节点之间的某种可量化关系。例如：

权重可以表示距离，时间，社交网络中两个用户之间共享的连接数。
或者可以用于描述您正在使用的上下文中的节点之间的连接的任何内容。

power-Graph

著名的Dijkstra算法，就是使用这些权重通过查找网络中节点之间的最短或最优的路径来优化路由。

稀疏图与密集图
当图中的边数接近最大边数时，图是密集的。

multi-Graph

当图中的边数明显少于最大边数时，图是稀疏的。

low-Graph

5 循环图
如果你按照图中的一系列连接，可能会找到一条路径，将你带回到同一节点。这就像“走在圈子里”，就像你在城市周围开车一样，你走的路可以带你回到你的初始位置。🚗
在图中，这些“圆形”路径称为“循环”。它们是在同一节点上开始和结束的有效路径。例如，在下图中，您可以看到，如果从任何节点开始，您可以通过跟随边缘返回到同一节点。

circle-Graph

循环并不总是“孤立的”，因为它们可以是较大图的一部分。可以通过在特定节点上开始搜索并找到将你带回同一节点的路径来检测它们。

图的实现

class Graph {
  constructor() {
    this.AdjList = new Map();
  }
  
  // 基础操作方法
  // addVertex(vertex) {}
  // addEdge(vertex, node) {}
  // print() {}
}

addVertex：添加顶点

addVertex(vertex) {
  if (!this.AdjList.has(vertex)) {
    this.AdjList.set(vertex, []);
  } else {
    throw 'Already Exist!!!';
  }
}

addEdge：添加边(Edge)

 addEdge(vertex, node) {
    // 向顶点添加边之前，必须验证该顶点是否存在。
    if (this.AdjList.has(vertex)) {
      // 确保添加的边尚不存在。
      if (this.AdjList.has(node)){
        let arr = this.AdjList.get(vertex);
        // 如果都通过，那么可以将边添加到顶点。
        if(!arr.includes(node)){
          arr.push(node);
        }
      }else {
        throw `Can't add non-existing vertex ->'${node}'`;
      }
    } else {
      throw `You should add '${vertex}' first`;
    }
}

print：打印图(Graph)

print() {
  for (let [key, value] of this.AdjList) {
    console.log(key, value);
  }
}

到目前为止，这就是创建图所需的。但是，99％的情况下，会要求你实现另外两种方法：

广度优先算法，BFS。
深度优先算法，DFS
BFS 的重点在于队列，而 DFS 的重点在于递归。这是它们的本质区别。

广度优先算法实现

广度优先算法（Breadth-First Search），同广度优先搜索。

是一种利用队列实现的搜索算法。简单来说，其搜索过程和 “湖面丢进一块石头激起层层涟漪” 类似。

16a9816362ebd72c

如上图所示，从起点出发，先把一个方向的点都遍历完才会改变方向…… 所以说，DFS 的搜索过程和 “不撞南墙不回头” 很相似，此即 “深度优先搜索算法” 中“深度”的由来。
该算法的前期步骤和BFS相似，接受起始节点并跟踪受访节点，最后执行递归的辅助函数。
具体步骤：

接受起点作为参数dfs(startingNode) 。
创建访问对象let visited = this.createVisitedObject()。
调用辅助函数递归起始节点和访问对象this.dfsHelper(startingNode, visited)。
dfsHelper 将其标记为已访问并打印出来。

createVisitedObject(){
  let arr = {};
  for(let key of this.AdjList.keys()){
    arr[key] = false;
  }
  return arr;
}

 dfs(startingNode){
    console.log('\nDFS')
    let visited = this.createVisitedObject();
    this.dfsHelper(startingNode, visited);
  }

  dfsHelper(startingNode, visited){
    visited[startingNode] = true;
    console.log(startingNode);

    let arr = this.AdjList.get(startingNode);

    for(let elem of arr){
      if(!visited[elem]){
        this.dfsHelper(elem, visited);
      }
    }
  }

  doesPathExist(firstNode, secondNode){
    let path = [];
    let visited = this.createVisitedObject();
    let q = [];
    visited[firstNode] = true;
    q.push(firstNode);
    while(q.length){
      let node = q.pop();
      path.push(node);
      let elements = this.AdjList.get(node);
      if(elements.includes(secondNode)){
        console.log(path.join('->'))
        return true;
      }else{
        for(let elem of elements){
          if(!visited[elem]){
            visited[elem] = true;
            q.unshift(elem);
          }
        }
      }
    }
    return false;
  }
}

字典树：Trie

Trie

Trie，是一种搜索树，也称字典树或单词查找树，此外也称前缀树，因为某节点的后代存在共同的前缀。

它的特点：

key都为字符串，能做到高效查询和插入，时间复杂度为O(k)，k为字符串长度
缺点是如果大量字符串没有共同前缀时很耗内存。
它的核心思想就是减少没必要的字符比较，使查询高效率。
即用空间换时间，再利用共同前缀来提高查询效率。

TrieSearch

字典树的应用

只要你想要将前缀与可能的完整值匹配，就可以使用Trie。

现实中多运用在：

自动填充/预先输入
搜索
输入法选项
分类

也可以运用在：

IP地址检索
电话号码
…

字典树的实现

class PrefixTreeNode {
  constructor(value) {
    this.children = {};
    this.endWord = null;
    this.value = value;
  }
}
class PrefixTree extends PrefixTreeNode {
  constructor() {
    super(null);
  }
  // 基础操作方法
  // addWord(string) {}
  // predictWord(string) {}
  // logAllWords() {}
}

addWord: 创建一个节点

addWord(string) {
    const addWordHelper = (node, str) => {
        if (!node.children[str[0]]) {
            node.children[str[0]] = new PrefixTreeNode(str[0]);
            if (str.length === 1) {
                node.children[str[0]].endWord = 1;
            } else if (str.length > 1) {
                addWordHelper(node.children[str[0]], str.slice(1));
        }
    };
    addWordHelper(this, string);
}

predictWord：预测单词。即：给定一个字符串，返回树中以该字符串开头的所有单词。

predictWord(string) {
    let getRemainingTree = function(string, tree) {
      let node = tree;
      while (string) {
        node = node.children[string[0]];
        string = string.substr(1);
      }
      return node;
    };

    let allWords = [];
    
    let allWordsHelper = function(stringSoFar, tree) {
      for (let k in tree.children) {
        const child = tree.children[k]
        let newString = stringSoFar + child.value;
        if (child.endWord) {
          allWords.push(newString);
        }
        allWordsHelper(newString, child);
      }
    };

    let remainingTree = getRemainingTree(string, this);
    if (remainingTree) {
      allWordsHelper(string, remainingTree);
    }

    return allWords;
  }

logAllWords：打印所有的节点

logAllWords() {
  console.log('------ 所有在字典树中的节点 -----------')
  console.log(this.predictWord(''));
}

logAllWords，通过在空字符串上调用predictWord来打印Trie中的所有节点。

散列表（哈希表）：Hash Tables

散列（hashing）是电脑科学中一种对资料的处理方法，通过某种特定的函数/算法（称为散列函数/算法）将要检索的项与用来检索的索引（称为散列，或者散列值）关联起来，生成一种便于搜索的数据结构（称为散列表）。也译为散列。旧译哈希（误以为是人名而采用了音译）。

它也常用作一种资讯安全的实作方法，由一串资料中经过散列算法（Hashing algorithms）计算出来的资料指纹（data fingerprint），经常用来识别档案与资料是否有被窜改，以保证档案与资料确实是由原创者所提供。 —-Wikipedia

哈希表的构成

Hash Tables优化了键值对的存储。在最佳情况下，哈希表的插入，检索和删除是恒定时间。哈希表用于存储大量快速访问的信息，如密码。
哈希表可以概念化为一个数组，其中包含一系列存储在对象内部子数组中的元组：

1	{[[['a'，9]，['b'，88]]，[['e'，7]，['q'，8]]，[['j'，7]，['l '，8]]]};

外部数组有多个等于数组最大长度的桶（子数组）。
在桶内，元组或两个元素数组保持键值对。

哈希表的基础知识

这里我就尝试以大白话形式讲清楚基础的哈希表知识：

散列是一种用于从一组相似对象中唯一标识特定对象的技术。我们生活中如何使用散列的一些例子包括：

在大学中，每个学生都会被分配一个唯一的卷号，可用于检索有关它们的信息。
在图书馆中，每本书都被分配了一个唯一的编号，可用于确定有关图书的信息，例如图书馆中的确切位置或已发给图书的用户等。

在这两个例子中，学生和书籍都被分成了一个唯一的数字。

思考一个问题
假设有一个对象，你想为其分配一个键以便于搜索。要存储键/值对，您可以使用一个简单的数组，如数据结构，其中键（整数）可以直接用作存储值的索引。

但是，如果密钥很大并且无法直接用作索引，此时就应该使用散列。

2, 一个哈希表的诞生
具体步骤如下：

在散列中，通过使用散列函数将大键转换为小键。
然后将这些值存储在称为哈希表的数据结构中。
散列的想法是在数组中统一分配条目（键/值对）。为每个元素分配一个键（转换键）。
通过使用该键，您可以在O(1)时间内访问该元素。
使用密钥，算法（散列函数）计算一个索引，可以找到或插入条目的位置。

具体执行分两步：

通过使用散列函数将元素转换为整数。此元素可用作存储原始元素的索引，该元素属于哈希表。
该元素存储在哈希表中，可以使用散列键快速检索它。

1 2	hash = hashfunc（key） index = hash ％ array_size

在此方法中，散列与数组大小无关，然后通过使用运算符（％）将其缩减为索引（介于0和array_size之间的数字 - 1）。

哈希函数

哈希函数是可用于将任意大小的数据集映射到固定大小的数据集的任何函数，该数据集属于散列表
哈希函数返回的值称为哈希值，哈希码，哈希值或简单哈希值。

要实现良好的散列机制，需要具有以下基本要求：

易于计算：它应该易于计算，并且不能成为算法本身。
统一分布：它应该在哈希表中提供统一分布，不应导致群集。
较少的冲突：当元素对映射到相同的哈希值时发生冲突。应该避免这些。

注意：无论散列函数有多健壮，都必然会发生冲突。因此，为了保持哈希表的性能，通过各种冲突解决技术来管理冲突是很重要的。

良好的哈希函数
假设您必须使用散列技术{“abcdef”，“bcdefa”，“cdefab”，“defabc”}等字符串存储在散列表中。
首先是建立索引：

a，b，c，d，e和f的ASCII值分别为97,98,99,100,101和102，总和为：597
597不是素数，取其附近的素数599，来减少索引不同字符串（冲突）的可能性。

哈希函数将为所有字符串计算相同的索引，并且字符串将以下格式存储在哈希表中。
hashTable

由于所有字符串的索引都相同，此时所有字符串都在同一个“桶”中。

这里，访问特定字符串需要O(n)时间（其中n是字符串数）。
这表明该哈希函数不是一个好的哈希函数。

如何优化这个哈希函数？
注意观察这些字符串的异同

1	{“abcdef”，“bcdefa”，“cdefab”，“defabc”}

都是由a，b，c，d，e和f组成
不同点在于组成顺序。

来尝试不同的哈希函数。

特定字符串的索引将等于字符的ASCII值之和乘以字符串中它们各自的顺序
之后将它与2069（素数）取余。

哈希表的实现

hash_js

class Node {
	constructor( data ){
		this.data = data;
		this.next = null;
	}
}

class HashTableWithChaining {
	constructor( size = 10 ) {
		this.table = new Array( size );
	}
	
    // 操作方法
    // computeHash( string ) {...}
    // ...
}

isPrime：素数判断

isPrime( num ) {
	for(let i = 2, s = Math.sqrt(num); i <= s; i++)
        if(num % i === 0) return false; 
    return num !== 1;
}

computeHash|findPrime：哈希函数生成

computeHash( string ) {
	let H = this.findPrime( this.table.length );
	let total = 0;
	for (let i = 0; i < string.length; ++i) {
      	total += H * total + string.charCodeAt(i);
   	}
	return total % this.table.length;
}
// 取模
findPrime( num ) {
	while(true) {
		if( this.isPrime(num) ){ break; }
		num += 1
	}
	return num;
}

Put：插入值

put( item ) {
	let key = this.computeHash( item );
	let node = new Node(item)
	if ( this.table[key] ) {
		node.next = this.table[key]
	}
	this.table[key] = node
}

Remove：删除值

remove( item ) {
	let key = this.computeHash( item );
	if( this.table[key] ) {
		if( this.table[key].data === item ) {
			this.table[key] = this.table[key].next
		} else {
			let current = this.table[key].next;
			let prev = this.table[key];
			while( current ) {
				if( current.data === item ) {
					prev.next = current.next
				}
				prev = current
				current = current.next;
			}
		}
	}
}

contains：判断包含

contains(item) {
    for (let i = 0; i < this.table.length; i++) {
        if (this.table[i]) {
            let current = this.table[i];
            while (current) {
                if (current.data === item) {
                    return true;
                }
                current = current.next;
            }
        }
    }
    return false;
}

Size & IsEmpty：判断长度或空

size( item ) {
  let counter = 0
  for(let i=0; i<this.table.length; i++){
    if( this.table[i] ) {
      let current = this.table[i]
      while( current ) {
        counter++
        current = current.next
      }
    }
  }
  return counter
}
isEmpty() {
  return this.size() < 1
}

Traverse：遍历

traverse( fn ) {
  for(let i=0; i<this.table.length; i++){
    if( this.table[i] ) {
      let current = this.table[i];
      while( current ) {
        fn( current );
        current = current.next;
      }
    }
  }
}

【笔记】《数据结构》