# 数据结构与算法(base on JavaScript)

# 一、链表结构

# 1】认识链表结构

链表和数组一样，可以用于存储一系列的元素，但是链表和数组的实现机制完全不同
这一章中，我们就来学习一下另外一种非常常见的用于存储数据的线性结构:链表

# ①数组：

要存储多个元素,数组(或称为列表)可能是最常用的数据结构。
我们之前说过，几乎每一种编程语言都有默认实现数组结构。
但是数组也有很多缺点:
- 数组的创建通常需要申请一段连续的内存空间(一整块的内存)，并且大小是固定的(大多数编程语言数组都是固定的)，所以当当前数组不能满足容量需求时，需要扩容. (一般情况下是申请一个更大的数组，比如2倍.然后将原数组中的元素复制过去)
- 而且在数组开头或中间位置插入数据的成本很高，需要进行大量元素的位移.
- 尽管我们已经学过的JavaScript的Array类方法可以帮我们做这些事，但背后的原理依然是这样。

# ②链表：

要储存多个元素，另外一个选择就是链表
但不同于数组，链表中的元素在内存中不必是连续的空间
链表的每个元素由一个储存元素本身的节点和一个指向下一个元素的引用（有些语言称为指针或者连接）组成
相对于数组，链表的优点：
- 内存空间不是必须连续的，可以充分利用计算机的内存，实现灵活的内存动态管理
- 链表不必在创建时就确定大小，并且大小可以无限的延伸下去
- 链表在插入和删除数据时，时间复杂度可以达到O(1)。相对数组效率高很多
相对于数组，链表有一些劣势：
- 链表访问任何一个位置的元素时，都需要从头开始访问。（无法跳过第一个元素访问任何一个元素）
- 无法通过下标直接访问元素，需要从头一个个访问，然后找到对应的元素

# 2】链表结构的封装

head属性会指向第一个节点；封装的节点类：给element属性传值，并且定义next属性（默认为空）

//封装链表的构造函数
function LinkedList(){
    //封装一个节点Node类，用于保存每个节点信息
    function Node(element){
        this.element=element
        this.next=null
    }
    //链表中的属性
    this.length=0	//链表的长度
    this.head=null	//指向第一个节点，默认为空
    
    //链表中的方法
}

# 3】链表常见操作

我们先来认识一下，链表中应该有哪些常见的操作

append(element) :向列表尾部添加一个新的项
insert(position, element) :向列表的特定位置插入一个新的项。
get(position) :获取对应位置的元素
indexOf(element) :返回元素在列表中的索引。如果列表中没有该元素则返回-1。
update(position) :修改某个位置的元素
removeAt(position) :从列表的特定位置移除一项。
remove(element) : 从列表中移除一项。
isEmpty() :如果链表中不包含任何元素，返回true ,如果链表长度大于0则返回false.
size() :返回链表包含的元素个数。与数组的length属性类似。
toString() :由于列表项使用了Node类，就需要重写继承自JavaScript对象默认的toString方法,让其只输出元素的值。

整体你会发现操作方法和数组非常类似，因为链表本身就是一种可以代替数组的结构.

# 4】append方法

向链表尾部追加数据可能有两种情况：
- 链表本身为空，新添加的数据是唯一的节点
- 链表不为空，需要向其他节点后面追加节点

    //1.追加方法
    LinkedList.prototype.append=function(element){
        //①创建新的节点
        var newNode=new Node(element)
        //②判断是否添加的是第一个节点
        if(this.length==0){//是第一个节点
            //var newNode=new Node(element)
            this.head=newNode//head是指向第一个节点
        }else{//不是第一个节点
            //var newNode=new Node(element)
            var current=this.head//指向第一个节点//current是个中间变量，指向head所指向的节点
            //③找到最后一个节点
            while(current.next!=null){
                current=current.next
            }
            current.next=newNode
        }
        //④增加链表长度
        this.length +=1
    }

# 5】toString方法

该方法比较简单，主要是获取每一个元素
还是从head头节点，因为获取链表的任何元素都必须从第一个节点开始
循环遍历每一个节点，并且取出其中的element，拼接成字符串
将最终字符串返回

//链表的toString方法
LinkedList.prototype.toString = function () {
    // 1.定义两个变量
    var current = this.head//current是个中间变量，指向head所指向的节点
    var listString = ""

    // 2.循环获取链表中所有的元素
    while (current!=null) {//current指向为空，跳出循环
        listString += "," + current.element
        current = current.next
    }

    // 3.返回最终结果
    return listString.slice(1)//返回去掉第一个","之后的字符串
}

# 7】使用toString方法测试append

var list = new LinkedList()
list.append('abc')
list.append('cba')
list.append('nba')
alert(list)//abc,cba,nba
//alert() 只能输出string，如果alert输出是对象会自动调用toString()方法，所有alert方法里面包含toString方法

# 8】insert方法

// 任意位置插入
LinkedList.prototype.insert = function (position, element) {
    // 1.检测越界问题: 越界插入失败
    if (position < 0 || position > this.length) return false//等于length是在最后插入

    // 2.找到正确的位置, 并且插入数据
    var newNode = new Node(element)
    var current = this.head//current是个中间变量，指向head所指向的节点
  
    // 3.判断是否列表是否在第一个位置插入
    if (position == 0) {
        newNode.next = current
        this.head = newNode	
    } else {
        	var index = 0//规定从0开始遍历
            var previous = null//记录遍历到的节点的前一个节点
        while (index++ < position) {
            previous = current//中间变量，记录遍历到的节点的前一个节点
            current = current.next//通过next的指向，来改变current的指向
        }
        newNode.next = current
        previous.next = newNode
    }
      // 4.length+1
    this.length++
    
    return true
}

# 9】get方法

//获取对应位置的元素
LinkedList.prototype.get = function (position) {
    //1.越界判断
    if(position < 0 || position >= this.length) return null
    //2.获取对应的element
    var current=this.head//中间变量保存head的指向
    var index=0//从下标为0开始遍历
    while(index++ < position){
        current=current.next
    }
    return current.element
}

# 10】indexOf方法

// 根据元素获取链表中的位置
LinkedList.prototype.indexOf = function (element) {
    // 1.定义变量, 保存信息
    var current = this.head
    index = 0
    
    // 2.找到元素所在的位置
    while (current!=null) {
        if (current.element === element) {
            return index
        }
        index++
        current = current.next
    }
    
    // 3.来到这个位置, 说明没有找到, 则返回-1
    return -1
}

# 11】update方法

//修改某个位置的元素
LinkedList.prototype.update = function (position,element) {
    //1.越界判断
    if(position < 0 || position >= this.length) return false
    //2.查找正确的节点
    var current= this.head
    var index=0
    while(index++ < position){
        current = current.next
    }
    //3.将传入的position位置的节点的element修改成新传入的element
    current.element=element
    return true
}

# 12】removeAt方法

// 根据位置移除节点
LinkedList.prototype.removeAt = function (position) {
    // 1.检测越界问题: 越界移除失败, 返回null
    if (position < 0 || position >= this.length) return null

    // 2.定义变量, 保存信息
    var current = this.head
    var previous = null
    var index = 0
    
    // 3.判断是否是移除第一项
    if (position === 0) {
        this.head = this.head.next//虽然没有直接移除当前节点，但是该节点会被浏览器回收
    } else {
        while (index++ < position) {
            previous = current//在current循环赋值之前，记录前一个节点
            current = current.next
        }
        
        previous.next = current.next
    }
    
    // 4.length-1
    this.length--
    
    // 5.返回移除的数据
    return current.element
}

# 13】remove方法

// 根据元素删除信息
LinkedList.prototype.remove = function (element) {
    var index = this.indexOf(element)
    return this.removeAt(index)
}

# 14】isEmpty方法

// 判断链表是否为空
LinkedList.prototype.isEmpty = function () {
    return this.length == 0
}

# 15】size方法

// 获取链表的长度
LinkedList.prototype.size = function () {
    return this.length
}

# 16】getFirst方法

// 获取第一个节点
LinkedList.prototype.getFirst = function () {
    return this.head.element
}

# 二、二叉树

# 1】二叉树有几个重要的特性

一个二叉树第i层的最大节点数为：2^(i-1),i>=1;
深度为k的二叉树有最大节点数总数为：2^k-1,k>=1
对任何非空二叉树T，若n0表示叶节点的个数、n2是度为2的非叶节点个数，那么两者满足关系n0=n2+1

# 2】二叉树最常见的方式使用双向链表来存储

# 3】二叉树的遍历

先序遍历：根左右，访问的每个节点都是根左右
中序遍历：左根右，访问的每个节点都是左根右
后序遍历：左右根，访问的每个节点都是左右根

# 4】二叉搜索树

二叉搜索树（BST，Binary Search Tree），也称二叉排序树或二叉查找树

二叉搜索树是一颗二叉树, 可以为空；如果不为空，满足以下性质：（二分查找的思想）

非空左子树的所有键值小于其根结点的键值。
非空右子树的所有键值大于其根结点的键值。
左、右子树本身也都是二叉搜索树。

# （1）二叉搜索树的操作

二叉搜索树有哪些常见的操作呢?
- insert(key)：向树中插入一个新的键。
- search(key)：在树中查找一个键，如果结点存在，则返回true；如果不存在，则返回false。
- inOrderTraverse：通过中序遍历方式遍历所有结点。
- preOrderTraverse：通过先序遍历方式遍历所有结点。
- postOrderTraverse：通过后序遍历方式遍历所有结点。
- min：返回树中最小的值/键。
- max：返回树中最大的值/键。
- remove(key)：从树中移除某个键。

# （2）二叉搜索树的实现

# ①创建二叉搜索树

我们像封装其他数据结构一样, 先来封装一个BinarySearchTree的类

// 创建BinarySearchTree
function BinarySerachTree() {
    // 创建结点构造函数
    function Node(key) {
        this.key = key
        this.left = null
        this.right = null
    }
    
    // 保存根的属性
    this.root = null
    
    // 二叉搜索树相关的操作方法
}

# ②向树中插入数据

我们两个部分来完成这个功能.

外界调用的insert方法

// 向树中插入数据
BinarySerachTree.prototype.insert = function (key) {
    // 1.根据key创建对应的node
    var newNode = new Node(key)
    
    // 2.判断根结点是否有值
    if (this.root === null) {
        this.root = newNode
    } else {
        this.insertNode(this.root, newNode)
    }
}

插入非根结点

BinarySerachTree.prototype.insertNode = function (node, newNode) {
    if (newNode.key < node.key) { // 1.准备向左子树插入数据
        if (node.left === null) { // 1.1.node的左子树上没有内容
            node.left = newNode
        } else { // 1.2.node的左子树上已经有了内容
            this.insertNode(node.left, newNode)
        }
    } else { // 2.准备向右子树插入数据
        if (node.right === null) { // 2.1.node的右子树上没有内容
            node.right = newNode
        } else { // 2.2.node的右子树上有内容
            this.insertNode(node.right, newNode)
        }
    }
}

# ③遍历二叉搜索树

先序遍历：根左右

// 前序遍历
BinarySerachTree.prototype.preOrderTraversal = function (handler) {
    this.preOrderTranversalNode(this.root, handler)
}

BinarySerachTree.prototype.preOrderTranversalNode = function (node, handler) {
    if (node !== null) {
        // 1.打印当前经过的节点
        handler(node.key)
        // 2.遍历所有的左子树
        this.preOrderTranversalNode(node.left, handler)
        // 3.遍历所有的右子树
        this.preOrderTranversalNode(node.right, handler)
    }
}

中序遍历：左根右

// 中序遍历
BinarySerachTree.prototype.inOrderTraversal = function (handler) {
    this.inOrderTraversalNode(this.root, handler)
}

BinarySerachTree.prototype.inOrderTraversalNode = function (node, handler) {
    if (node !== null) {
        this.inOrderTraversalNode(node.left, handler)
        handler(node.key)
        this.inOrderTraversalNode(node.right, handler)
    }
}

后序遍历：左右根

// 后续遍历
BinarySerachTree.prototype.postOrderTraversal = function (handler) {
    
}

BinarySerachTree.prototype.postOrderTraversalNode = function (node, handler) {
    if (node !== null) {
        this.postOrderTraversalNode(node.left, handler)
        this.postOrderTraversalNode(node.right, handler)
        handler(node.key)
    }
}

# ④最大值&最小值

// 获取最大值和最小值
BinarySerachTree.prototype.min = function () {
    var node = this.root
    while (node.left !== null) {
        node = node.left
    }
    return node.key
}

BinarySerachTree.prototype.max = function () {
    var node = this.root
    while (node.right !== null) {
        node = node.right
    }
    return node.key
}

# ⑤搜索特定的值

// 搜搜特定的值
BinarySerachTree.prototype.search = function (key) {
    return this.searchNode(this.root, key)
}

BinarySerachTree.prototype.searchNode = function (node, key) {
    // 1.如果传入的node为null那么, 那么就退出递归
    if (node === null) {
        return false
    }

    // 2.判断node节点的值和传入的key大小
    if (node.key > key) { // 2.1.传入的key较小, 向左边继续查找
        return this.searchNode(node.left, key)
    } else if (node.key < key) { // 2.2.传入的key较大, 向右边继续查找
        return this.searchNode(node.right, key)
    } else { // 2.3.相同, 说明找到了key
        return true
    }
}

非递归代码实现:

BinarySerachTree.prototype.search = function (key) {
    var node = this.root
    while (node !== null) {
        if (node.key > key) {
            node = node.left
        } else if (node.key < key) {
            node = node.right
        } else {
            return true
        }
    }
    return false
}

# 三、复杂度

# 1】时间复杂度：与代码的结构有密切的关系

# 2】空间复杂度：与数据结构的设计有关

O(n)表示：复杂度与计算实例的个数n线性相关

O(logn)表示：复杂度与计算实例的个数n对数相关

O(1)表示：数据量与复杂度无关，不管输入多少数据，使用使用一样的资源

# 3】一些经验性的结论：

一个顺序结构的代码，时间复杂度是O(1)
二分查找，或者更通用地说是采用分而治之的二分策略，时间复杂度都是O(logn)
一个简单的for循环，时间复杂度是O(n)
两个顺序执行的for循环，时间复杂度是O(n)+O(n)=O(2n)，也就是O(n)
两个嵌套的for循环，时间复杂度是O(n^2)

# 4】常见的降低复杂度的方法

降低时间复杂度：递归，二分法，排序算法，动态规划等

降低空间复杂度：能用低复杂度的数据结构解决问题，就千万不要用高复杂度的数据结构

(1)暴力解法：在没有任何时间、空间约束下，完成代码任务的开发
(2)无效操作处理：将代码中的无效计算、无效存储剔除，降低时间或空间复杂度
(3)时空转换：设计合理数据结构，完成时间复杂度向空间复杂度的转移

# 四、集合

# 1】集合的介绍

集合常见的实现方式是：哈希表。
集合通常是由一组无序的，不能重复的元素构成。
- 和数学中的集合名词比较相似，但是数学中的集合范围比较大一些，也允许集合中的元素重复。
- 在计算机中，集合通常表示的结构中元素时不允许重复的
字典map的主要特点是一一对应的关系，是使用键值对的形式存储数据，另外字典中的key是不可以重复的，而value可以重复，并且字典中的key是无序的。

# 2】操作的方法

add(value)：向集合添加一个新的项。

remove(value)：从集合移除一个值。

has(value)：如果值在集合中，返回true，否则返回false。

clear()：移除集合中的所有项。

size()：返回集合所包含元素的数量。与数组的length属性类似。

values()：返回一个包含集合中所有值的数组。

# 3】集合的封装和集合间的操作

//封装集合类
function Set(){
    //属性
    this.items={}
    
    //方法
    //add方法
    Set.prototype.add = function(value){
       	//判断当前集合中是否已经包含了该元素
        if(this.has(value)){
            return false
        }
        //将元素添加到集合中
        this.items[value] = value
        return true       
    }
    
    //has方法
    Set.prototype.has = function (value){
        return this.items.hasOwnProperty(value)//如果有了重复的，就返回true，否则返回false
    }
    
    //remove方法
    Set.prototype.remove = function (value){
        //1.该集合中是否包含改元素
        if(!this.has(value)){
            return false
        }
        //2，将元素从属性中删除
        delete this.items[value]
        return true
    }
    
    //clear方法
    Set.prototype.clear = function (){
        this.items = {}   
    }
    
    //size方法
    Set.prototype.size = function (){
        return Object.keys(this.items).length
    }
    
    //获取集合中所有的值
    Set.prototype.values = function (){
        return Object.keys(this.items)//数组形式
    }
    
    
    //集合间的操作
    //并集
    Set.prototype.union = function (otherSet){
        //this：集合对象A
        //otherSet：集合对象B
        //1.创建新的集合
        var unionSet = new Set()
        //2.将A集合中所有的元素添加到新集合中
        var values = this.values()
        for(let i =0;i<values.length;i++){
            unionSet.add(values[i])
        }
        //3.取出B集合中的元素，判断是否需要加到新集合
        values = otherSet.values()
        for(let i =0;i<values.length;i++){
            unionSet.add(values[i])
        }
        return unionSet
    }
    
    //交集
    Set.prototype.intersection = function (otherSet){
        //this：集合对象A
        //otherSet：集合对象B
        //1.创建新的集合
        var intersectionSet = new Set()
        //2.从A中取出一个个元素，判断是否同时存在于集合B中，存在放入新集合中
        var values = this.values()
        for(let i=0;i<values.length;i++){
            var item = values[i]
            if(otherSet.has(item)){
                intersectionSet.add(item)
            }
        }
        return intersectionSet
    }
    
    //差集
    Set.prototype.difference = function (otherSet){
        //this：集合对象A
        //otherSet：集合对象B
        //1.创建新的集合
        var differenceSet = new Set()
        //2.取出A集合一个个元素，判断是否同时存在于B中，不存在B中，则添加到新集合中
        var values = this.values()
        for(let i=0;i<values.length;i++){
            var item = values[i]
            if(!otherSet.has(item)){
                differenceSet.add(item)
            }
        }
        return differenceSet
    }
    
    //子集
    Set.prototype.subset = function (otherSet){
        //B集合是否是A集合的子集
        //this：集合对象A
        //otherSet：集合对象B
        //遍历集合A中所有的元素，如果发现，集合A中的元素，在集合B中不存在，那么返回false
        //如果遍历完了整个集合，依然没有返回false，那么返回true即可
        var values = this.values()
        for(let i=0;i<values.length;i++){
            var item = values[i]
            if(!otherSet.has(item)){
                return false
            }
        }
        return true
    }
    
    
}

# 4】测试Set类

//1.常见Set类对象
var set = new Set()

//2.添加元素
alert(set.add('abc'))//true
alert(set.add('abc'))//false
alert(set.add('cba'))//true
alert(set.add('nba'))//true
alert(set.add('mba'))//true
alert(set.values())//abc,cba,nba,mba

# 五、字典

# 1】字典的介绍

字典的主要特点是一一对应的关系，是使用键值对的形式存储数据，另外字典中的key是不可以重复的，而value可以重复，并且字典中的key是无序的。

# 字典的映射关系:

有些编程语言中称这种映射关系为字典, 因为它确实和生活中的字典比较相似. (比如Swift中Dictionary, Python中的dict)
有些编程语言中称这种映射关系为Map, 注意Map在这里不要翻译成地图, 而是翻译成映射. (比如Java中就有HashMap&TreeMap等)

# 字典和数组:

字典和数组对比的话, 字典可以非常方便的通过key来搜索对应的value, key可以包含特殊含义, 也更容易被人们记住.

# 字典和对象:

很多编程语言(比如Java)中对字典和对象区分比较明显, 对象通常是一种在编译期就确定下来的结构, 不可以动态的添加或者删除属性. 而字典通常会使用类似于哈希表的数据结构去实现一种可以动态的添加数据的结构.
但是在JavaScript中, 似乎对象本身就是一种字典. 所有在早期的JavaScript中, 没有字典这种数据类型, 因为你完全可以使用对象去代替.

# 六、哈希表

怎么根据数据值使用一系列函数插入到哈希表中，后面就怎么使用数据值配合这个函数到哈希表中查找，效率非常高

# 1】哈希表介绍

哈希表通常是基于数组进行实现的, 但是相对于数组, 它也很多的优势：

它可以提供非常快速的插入-删除-查找操作
无论多少数据, 插入和删除值需要接近常量的时间：即O(1)的时间级. 实际上, 只需要几个机器指令即可完成
哈希表的速度比树还要快，基本可以瞬间查找到想要的元素
哈希表相对于树来说编码要容易很多

哈希表相对于数组的一些不足：

哈希表中的数据是没有顺序的，所以不能以一种固定的方式（比如从小到大）来遍历其中的元素。
通常情况下，哈希表中的key是不允许重复的，不能放置相同的key，用于保存不同的元素。

# 2】哈希化

哈希化：将大数字转化成数组范围内下标的过程。

哈希函数：通常我们会将单词转成大数字，大数字在进行哈希化的代码实现放在一个函数中

哈希表：最终将数据插入到的这个数组，对整个结构的封装

通过哈希化后的下标值可能出现重复，虽然几率很小但是也无法避免这种冲突。

冲突：解决这种冲突的两种方案；（链地址法和开放地址法）

# 3】链地址法（开发过程用的更多）

链地址法是一种比较常见的解决冲突的方案(也称为拉链法)
其实，如果你理解了为什么产生冲突，看到图后就可以立马理解链地址法是什么含义了。

# 4】开放地址法

开放地址法的主要工作方式是：寻找空白的单元格来添加重复的数据

从图片的文字中我们可以了解到, 开放地址法其实就是要寻找空白的位置来放置冲突的数据项.
但是探索这个位置的方式不同, 有三种方法:
- 线性探测
- 二次探测
- 再哈希法

# ①线性探测

线性探测非常好理解: 线性的查找空白的单元.
插入的32:（依次对比判断，下标+1，再依次插入，第一次哈希化直到成功插入之间不留空）
- 经过哈希化得到的index=2, 但是在插入的时候, 发现该位置已经有了82. 怎么办呢?
- 线性探测就是从index位置+1开始一点点查找合适的位置来放置32, 什么是合适的位置呢?
- 空的位置就是合适的位置, 在我们上面的例子中就是index=3的位置, 这个时候32就会放在该位置.
查询32呢?
- 查询32和插入32比较相似.
- 首先经过哈希化得到index=2, 比如2的位置结果和查询的数值是否相同, 相同那么就直接返回.
- 不相同呢? 线性查找, 从index位置+1开始查找和32一样的.
- 这里有一个特别需要注意的地方: 如果32的位置我们之前没有插入, 是否将整个哈希表查询一遍来确定32存不存在吗?
- 当然不是, 查询过程有一个约定, 就是查询到空位置, 就停止. (因为查询到这里有空位置, 32之前不可能跳过空位置去其他的位置.)
删除32呢?
- 删除操作和插入查询比较类似, 但是也有一个特别注意点.
- 注意: 删除操作一个数据项时, 不可以将这个位置下标的内容设置为null, 为什么呢?
- 因为将它设置为null可能会影响我们之后查询其他操作, 所以通常删除一个位置的数据项时, 我们可以将它进行特殊处理(比如设置为-1).
- 当我们之后看到-1位置的数据项时, 就知道查询时要继续查询, 但是插入时这个位置可以放置数据.
线性探测的问题:
- 线性探测有一个比较严重的问题, 就是聚集. 什么是聚集呢?
- 比如我在没有任何数据的时候, 插入的是22-23-24-25-26, 那么意味着下标值:2-3-4-5-6的位置都有元素. 这种一连串填充单元就叫做聚集.
- 聚集会影响哈希表的性能, 无论是插入/查询/删除都会影响.
- 比如我们插入一个32, 会发现连续的单元都不允许我们放置数据, 并且在这个过程中我们需要探索多次.
- 二次探测可以解决一部分这个问题, 我们一起来看一看.

# ②二次探测

我们刚才谈到, 线性探测存在的问题: 就是如果之前的数据时连续插入的, 那么新插入的一个数据可能需要探测很长的距离.
二次探测在线性探测的基础上进行了优化:
- 二次探测主要优化的是探测时的步长, 什么意思呢?
- 线性探测, 我们可以看成是步长为1的探测, 比如从下标值x开始, 那么线性测试就是x+1, x+2, x+3依次探测.
- 二次探测, 对步长做了优化, 比如从下标值x开始, x+1², x+2², x+3².
- 这样就可以一次性探测比较常的距离, 比避免那些聚集带来的影响.
二次探测的问题:
- 但是二次探测依然存在问题, 比如我们连续插入的是32-112-82-2-192, 那么它们依次累加的时候步长的相同的.
- 也就是这种情况下会造成步长不一的一种聚集. 还是会影响效率.
- 怎么根本解决这个问题呢? 让每个人的步长不一样, 一起来看看再哈希法吧.

# ③再哈希法

为了消除线性探测和二次探测中无论步长+1还是步长+平法中存在的问题, 还有一种最常用的解决方案: 再哈希法.
再哈希法:
- 二次探测的算法产生的探测序列步长是固定的: 1, 4, 9, 16, 依次类推.
- 现在需要一种方法: 产生一种依赖关键字的探测序列, 而不是每个关键字都一样.
- 那么, 不同的关键字即使映射到相同的数组下标, 也可以使用不同的探测序列.
- 再哈希法的做法就是: 把关键字用另外一个哈希函数, 再做一次哈希化, 用这次哈希化的结果作为步长.
- 对于指定的关键字, 步长在整个探测中是不变的, 不过不同的关键字使用不同的步长.
第二次哈希化需要具备如下特点:
- 和第一个哈希函数不同. (不要再使用上一次的哈希函数了, 不然结果还是原来的位置)
- 不能输出为0(否则, 将没有步长. 每次探测都是原地踏步, 算法就进入了死循环)
其实, 我们不用费脑细胞来设计了, 计算机专家已经设计出一种工作很好的哈希函数:
- stepSize = constant - (key % constant)
- 其中constant是质数, 且小于数组的容量.
- 例如: stepSize = 5 - (key % 5), 满足需求, 并且结果不可能为0.

# 5】采用链地址法来实现哈希表

实现的哈希表(基于storage的数组)每个index对应的是一个数组(bucket).(当然基于链表也可以.)

bucket中存放什么呢? 我们最好将key和value都放进去, 我们继续使用一个数组.(其实其他语言使用元组更好)

最终我们的哈希表的数据格式是这样: [[ [k,v], [k,v], [k,v] ] , [ [k,v], [k,v] ], [ [k,v] ] ]

# ①创建哈希表

我们像封装其他数据结构一样, 先来创建一个哈希表的类: HashTable

// 创建HashTable构造函数
function HashTable() {
    // 定义属性
    this.storage = []
    this.count = 0
    this.limit = 8

    // 定义相关方法
    // 哈希函数
    HashTable.prototype.hashFunc = function(str, max) {
        // 1.初始化hashCode的值
        var hashCode = 0

        // 2.霍纳算法, 来计算hashCode的数值
        for (var i = 0; i < str.length; i++) {
            hashCode = 37 * hashCode + str.charCodeAt(i)
        }
      
        // 3.取模运算
        hashCode = hashCode % max
        return hashCode
    }
}

代码解析:

我们定义了三个属性:
storage作为我们的数组, 数组中存放相关的元素.
count表示当前已经存在了多少数据.
limit用于标记数组中一共可以存放多少个元素.
另外, 我们直接将哈希函数定义在了HashTable中.

# ②插入&修改数据

现在, 我们来做向哈希表中插入数据

// 插入数据方法
HashTable.prototype.put = function (key, value) {
    // 1.获取key对应的index
    var index = this.hashFunc(key, this.limit)

    // 2.取出数组(也可以使用链表)
    var bucket = this.storage[index]

    // 3.判断这个数组是否存在
    if (bucket === undefined) {
        // 3.1创建桶
        bucket = []
        this.storage[index] = bucket
    }
    alert(bucket)
    
    // 4.判断是新增还是修改原来的值.
    var override = false
    for (var i = 0; i < bucket.length; i++) {
        var tuple = bucket[i]
        if (tuple[0] === key) {
            tuple[1] = value
            override = true
        }
    }
    
    // 5.如果是新增, 前一步没有覆盖
    if (!override) {
        bucket.push([key, value])
        this.count++
    }
}

代码解析:

步骤1: 根据传入的key获取对应的hashCode, 也就是数组的index
步骤2: 从哈希表的index位置中取出桶(另外一个数组)
步骤3: 查看上一步的bucket是否为null
- 为null, 表示之前在该位置没有放置过任何的内容, 那么就新建一个数组[]
步骤4: 查看是否之前已经放置过key对应的value
- 如果放置过, 那么就是依次替换操作, 而不是插入新的数据.
- 我们使用一个变量override来记录是否是修改操作
步骤5: 如果不是修改操作, 那么插入新的数据.
- 在bucket中push新的[key, value]即可.
- 注意: 这里需要将count+1, 因为数据增加了一项.

# ③获取数据

有插入和修改数据, 就应该有根据key获取value

// 获取存放的数据
HashTable.prototype.get = function (key) {
    // 1.获取key对应的index
    var index = this.hashFunc(key, this.limit)

    // 2.获取对应的bucket
    var bucket = this.storage[index]

    // 3.如果bucket为null, 那么说明这个位置没有数据
    if (bucket == null) {
        return null
    }

    // 4.有bucket, 判断是否有对应的key
    for (var i = 0; i < bucket.length; i++) {
        var tuple = bucket[i]
        if (tuple[0] === key) {
            return tuple[1]
        }
    }
    
    // 5.没有找到, return null
    return null
}

代码解析:
- 步骤1: 根据key获取hashCode(也就是index)
- 步骤2: 根据index取出bucket.
- 步骤3: 因为如果bucket都是null, 那么说明这个位置之前并没有插入过数据.
- 步骤4: 有了bucket, 就遍历, 并且如果找到, 就将对应的value返回即可.
- 步骤5: 没有找到, 返回null

# ④删除数据

我们根据对应的key, 删除对应的key/value

// 删除数据
HashTable.prototype.remove = function (key) {
    // 1.获取key对应的index
    var index = this.hashFunc(key, this.limit)
    
    // 2.获取对应的bucket
    var bucket = this.storage[index]
    
    // 3.判断同是否为null, 为null则说明没有对应的数据
    if (bucket == null) {
        return null
    }
    
    // 4.遍历bucket, 寻找对应的数据
    for (var i = 0; i < bucket.length; i++) {
        var tuple = bucket[i]
        if (tuple[0] === key) {
            bucket.splice(i, 1)
            this.count--
            return tuple[1]
        }
    }
    
    // 5.来到该位置, 说明没有对应的数据, 那么返回null
    return null
}

代码解析:
- 代码思路和查询基本一致, 不再给出解析过程. 也可以查看注释.

# ⑤其他方法

判断哈希表是否为空: isEmpty

// isEmpty方法
HashTable.prototype.isEmpty = function () {
    return this.count == 0
}

获取哈希表中数据的个数

// size方法
HashTable.prototype.size = function () {
    return this.count
}