数据结构篇

❝

js篇没有结束喔，只不过先复习一下数据结构吧

前两天看到一个大佬发的关于数据结构的博客，满满的字一个代码没有，众人都说太干了。然后小白就写一个只实现的吧

注意只是实现只是实现喔，因为这几个简单的数据结构说实话好像也没有什么值得解释的，不像平衡树大小堆那种

希望你有一些数据结构的基础，了解他们的基本结构

图中的图片，一部分是自己画的，一部分是百度图片找的。原来在某c开头的博客上记录笔记故有了上面的水印。此篇是先实现简单的数据结构

函数式编程的下篇毁于掘金更新那段时间了，很痛心，希望后面忍着泪补上

希望与大家共同进步，代码过多难免有疏漏。如有误，望指教，感恩，如若嫌弃本文同样太干，可翻阅一下小白之间的笔记（上半年纯小白时写的放到文章最后了）

额，可能代码太长排不了版

❞

下篇链接

一、栈

一个栈的数据结构应实现一下功能

• push 出栈
• pop 入栈
• peek 返回栈顶元素
• isEmpty 判空
• clear 清除栈中元素
• size 返回栈中元素个数

实现及部分测试代码

 class Stack {
            constructor() {
                this._count = 0 //可记录栈内元素长度也可以当做栈内指针
                this._data = {} //用于存储栈内数据
            }
            isEmpty() {
                return this._count === 0
            }
            push(value) {
                this._data[this._count++] = value
            }
            pop() {
                if (this.isEmpty()) {
                    return undefined
                }
                this._count--;

                let res = this._data[this._count]
                delete this._data[this._count]

                return res
            }
            peek() {
                return this._data[this._count - 1]
            }
            size() {
                return this._count
            }
            clean() {
                this._data = {}
                this._count = 0
            }

        }

        const stack = new Stack()
        stack.push(5)
        stack.push(8)
        stack.push(10)

        console.log(stack.peek())
        console.log(stack.pop())
        console.log(stack)
        console.log(stack.size())

二、队列

2.1 普通队列

一个队列的数据结构要实现以下方法

• enqueue（e）向队尾添加元素
• dequeue() 从对头出去一个元素
• peek（）返回队列中的第一个元素，也即：返回对头元素
• isEmpty（）判空
• size（）返回队列中元素的个数
• clear() 清空

实现及部分测试代码

        class Queue {
            constructor() {
                this._data = {}
                this._count = 0
                this._first = 0 //队头指针
            }
            isEmpty() {
                return this._count === this._first
            }
            enqueue(value) {
                this._data[this._count++] = value
            }
            dequeue() {
                if (this.isEmpty()) {
                    return undefined
                }
                let res = this._data[this._first]
                delete this._data[this._first]
                this._first++;
                return res

            }
            peek() {
                if (this.isEmpty()) {
                    return undefined
                }
                return this._data[this._first]
            }
            size() {
                return this._count - this._first
            }
            clean() {
                this._data = {}
                this._count = 0
                this._first = 0
            }
        }
        const q = new Queue()
        q.enqueue(1)
        q.enqueue(2)
        q.enqueue(3)
        q.enqueue(4)
        console.log(q)
        console.log(q.dequeue())
        console.log(q.peek())
        console.log(q.size())

2.2 双端队列

一个双端队列的数据结构要实现以下功能

双端队列

• isEmpty
• clear
• size
• addFront（e） 队头添加元素
• addBack(e) 队尾添加元素
• removeFront 队头移出元素
• removeBack 队尾移出元素
• peekFront 取队头元素
• peekBack 取队尾元素

实现及部分测试代码

        class Deque {
            constructor() {
                this._data = {}
                this._count = 0
                this._first = 0
            }
            isEmpty() {
                    return this._count === this._first
                }
                //队尾进
            enqueue(value) {
                    this._data[this._count++] = value
                }
                //队头出
            dequeue() {
                    if (this.isEmpty()) {
                        return undefined
                    }
                    let res = this._data[this._first]
                    delete this._data[this._first]
                    this._first++;
                    return res

                }
                //队头进
            addFront(value) {
                    if (this.isEmpty()) {
                        this.enqueue(value)
                    }
                    this._data[--this._first] = value
                }
                //队尾出
            removeBack() {
                if (this.isEmpty()) {
                    return undefined
                }
                this._count--
                    let res = this._data[this._count]
                delete this._data[this._count]
                return res
            }
        }

        const d = new Deque()
        d.enqueue(1)
        d.enqueue(2)
        d.addFront(3)

        //    此时队列的数据从头到尾应是3,1,2
        //    调用队头出应是3
        console.log(d.dequeue())

        // 再掉队尾出应是2
        console.log(d.removeBack())

其他比较简单上面已有实现思路，就不一一重复了

2.3 循环队列

我们在这个循环队列数据结构中实现以下功能

• isEmpty 判空
• isFull 判满
• put（e）队尾插
• poll（）队头取

实现及部分测试代码

        class SqQueue {
            constructor() {
                this._data = {}
                this._front = 1 //头部指针
                this._rear = 1 //尾部指针
                this.MAX = 5
            }
            isEmpty() {
                return this._front === this._rear
            }
            isFull() {
                return (this._rear + 1) % this.MAX === this._front
            }
            put(value) {
                if (this.isFull()) {
                    return 'FULL'
                }
                this._data[this._rear] = value

                // 指针后移的同时也要考虑它是个环不能允许它超过最大值
                //即如果此时它在5的位置，假设此时头在2或3等位置未满，那么尾指针后移应该1而不能是6
                this._rear = (this._rear + 1) % this.MAX
            }
            poll() {
                if (this.isEmpty()) {
                    return undefined
                }
                let res = this._data[this._front]
                delete this._data[this._front]
                this._front = (this._front + 1) % this.MAX
                return res
            }
        }
        let sq = new SqQueue()
        sq.put(1)
        sq.put(2)
        sq.put(3)
        sq.put(4)
        console.log(sq.poll()) //1
        console.log(sq.poll()) //2
        console.log(sq.poll()) //3
        sq.put(2)
        sq.put(3)
        sq.put(4)

        // 此时从队尾 - > 队头应是4, 3, 2, 4
        console.log(sq.poll()) //4
        console.log(sq.poll()) //2
        console.log(sq.poll()) //3
        console.log(sq.poll()) //4

三、链表

3.1 单链表

节点类

  class LNode {
            constructor(value) {
                this._value = value
                this._next = null //指针域
            }
        }

链表类

  //单链表类
        class LinkList {
            constructor() {
                this._head = null //头节点
                this._count = 0
            }
        }

我们接下来实现以下方法

• push(element) 向尾部插一个
• insert(element, position) 向指定位置插一个
• getElementAt(index) 获取指定位置的元素
• remove(element) 移出元素
• indexOf(element) 返回该元素的位置
• removeAt(position) 移出指定位置的元素
• isEmpty() 判空
• size() 链表长度

push

 push(value) {
                const node = new LNode(value)
                let current = this._head

                if (current === null) {
                    this._head = node
                } else {
                    // 不是空，顺着链条向下找,最后一个节点的指针域为空
                    while (current._next) {
                        current = current._next
                    }
                    current._next = node
                }

                this._count++
            }



//最后的测试代码

      const l = new LinkList()
        l.push(1)
        l.push(2)
        l.push(3)
        l.push(4)
        console.log(l)

getElementAt及insert

这俩在一起写的是因为，我们可以在insert方法中借用一下getElementAt

  // 获取指定位置的节点
            getElementAt(index) {
                if (!(index >= 0 && index < this._count)) return undefined
                let current = this._head
                for (let i = 0; i < index; i++) {
                    current = current._next
                }
                return current

            }

            // 在任意位置插入
            insert(value, index) {
                if (!(index >= 0 && index <= this._count)) return undefined

                const node = new LNode(value)
                    // index==0
                if (index === 0) {
                    let current = this._head
                    this._head = node
                    this._head._next = current
                } else {
                    // 还是先找要操作的前一位置
                    let pre = this.getElementAt(index - 1)
                    let current = pre._next

                    pre._next = node
                    node._next = current

                }
                this._count++;

            }


//最后的测试代码
       l.push(1)
        l.push(2)
        l.push(3)
        l.push(4)
        l.insert(5, 1)
        console.log(l)

可以看到5被查到index=1的位置了（从0开始的）

removeAt

// 移出指定位置的节点
                      removeAt(index) {
                if (!(index >= 0 && index < this._count)) return undefined
                let current = this._head
                if (index === 0) {
                    this._head = current._next
                } else {
                    let previous;
                    for (let i = 0; i < index - 1; i++) {
                        current = current._next
                    }
                    previous = current //指向要删除节点的前一个
                    current = current._next //指向当前要删除节点
                    previous._next = current._next


                    return current._value
                }
                this._count--


            }
//最后的测试代码
        const l = new LinkList()
        l.push(1)
        l.push(2)
        l.push(3)
        l.push(4)
        l.insert(5, 1)
        l.removeAt(1)
        console.log(l)

可以看到上面刚插入的5又被移出了

indexOf

 //返回指定节点元素的位置
            indexOf(value) {
                let current = this._head
                    //遍历一下链表即可
                for (let i = 0; i < this._count && current != null; i++) {
                    if (current._value === value) {
                        return i
                    } else {
                        current = current._next
                    }
                }
            }

//最后的测试代码
const l = new LinkList()
        l.push(1)
        l.push(2)
        l.push(3)
        l.push(4)
        l.insert(5, 1)
        l.removeAt(1)
        console.log(l.indexOf(3));
        console.log(l)

remove

  // 移出一个指定元素的节点
            remove(value) {
                let index = this.indexOf(value)
                this.removeAt(index)
            }

isEmpty及size()

 //链表长度
            size() {
                return this._count
            }

            // 判空
            isEmpty() {
                return this.size() === 0
            }

3.2 双向链表

         class Node {
            constructor(value) {
                this.value = value
                this.pre = null //前驱指针
                this.next = null //后继指针
            }
        }

        class DoubleLinkedList {
            constructor() {
                this.count = 0
                this.head = null
                this.q = null //指向尾节点
            }

            //根据位置返节点
            getElementAt(index) {
                if (index < 0 || index >= this.count) return undefined
                let current = this.head
                for (let i = 0; i < index; i++) {
                    current = current.next
                }
                return current
            }

            //指定位置插入
            insert(value, index) {
                if (index < 0 || index > this.count) return false
                const node = new Node(value)

                // 解析考虑三种情况，在头、在尾、在中间

                //头
                if (index === 0) {
                    // 又分为链表开始为空与不空
                    if (this.head === null) {
                        this.head = node
                        this.q = node
                    } else {
                        node.next = this.head
                        this.head.pre = node
                        this.head = node
                    }

                }

                // 尾部
                else if (index === this.count) {
                    this.q.next = node
                    node.pre = this.q

                    // 再让q指回尾部
                    this.q = node
                }
                // 中间
                else {
                    // 和单链表的操作一样，找到要操作的前一个
                    let pre = this.getElementAt(index - 1)
                    let current = pre.next

                    pre.next = node
                    node.next = current

                    node.pre = pre
                    current.pre = node
                }
                this.count++

            }

            // 指定位置移出
            removeAt(index) {
                if (index < 0 || index >= this.count)
                    return false

                // 处理情况也分为在头在尾在中间

                // 头
                if (index === 0) {
                    this.head = this.head.next

                    // 不能马上将前驱指针设为null，不能保证有没有第二个节点
                    if (this.count === 1) {
                        this.q = null
                    } else {

                        this.head.pre = null
                    }
                }

                //尾
                else if (index == this.count - 1) {
                    let current = this.q.pre
                    current.next = null
                    this.q = current
                }

                // 中间
                else {
                    // 还是先找它的前一个
                    let preNode = getElementAt(index - 1)
                    let current = preNode.next

                    preNode.next = current.next
                    current.next.pre = preNode
                }

                this.count--

            }
        }

        const test = new DoubleLinkedList();
        test.insert(1, 0)
        test.insert(2, 1)
        test.insert(3, 2)
        test.insert(4, 3)
        test.removeAt(3)
        console.log(test)

3.3 循环链表

上面实现了双向链表，而循环链表则是对链表的进一步改进。使得它们可以头连尾，尾连头。构成一个闭环。

同样，它的很多操作是和单链表是一样的。在这我们只看它们任意位置插入和任意位置删除两个方法

insert

 class Node {
            constructor(value) {
                this.value = value
                this.pre = null //前驱指针
                this.next = null //后继指针
            }
        }

        class LinkedList {
            constructor() {
                    this.count = 0
                    this.head = null
                    this.q = null //指向尾节点
                }
                //根据位置返节点
            getElementAt(index) {
                if (index < 0 || index >= this.count) return undefined
                let current = this.head
                for (let i = 0; i < index; i++) {
                    current = current.next
                }
                return current
            }

            insert(value, index) {
                if (index < 0 || index > this.count) return false
                const node = new Node(value)

                // 头
                if (index === 0) {
                    if (this.head === null) {
                        this.head = node
                        this.q = node

                        node.pre = node
                        node.next = node
                    } else {
                        node.next = this.head
                        this.head.pre = node
                        this.head = node

                        this.head.pre = this.q
                        this.q.next = this.head
                    }
                }
                // 尾
                else if (index == this.count) {
                    this.q.next = node
                    node.pre = this.q
                    this.q = node
                    this.q.next = this.head
                    this.head.pre = this.q
                }
                // 中间
                else {
                    // 和原来一样
                    let preNode = this.getElementAt(index - 1)
                    let current = preNode.next

                    preNode.next = node
                    node.pre = preNode
                    current.pre = node
                    node.next = current

                }
                this.count++

            }
        }
const test = new LinkedList()
        test.insert(1, 0)
        test.insert(2, 1)
        test.insert(3, 2)

        console.log(test)

1-2-3-1-2-3，最后的指针又指回了第一个节点实现循环

removeAt

remove(index) {
                if (index < 0 || index > this.count - 1) return false

                // 头
                if (index === 0) {

                    // 又分只有一个元素和多个
                    if (this.count === 1) {
                        this.head = null
                        this.q = null
                    } else {
                        this.head = this.head.next
                        this.head.pre = this.q
                        this.q.next = this.head
                    }

                }
                // 尾
                else if (index === this.count - 1) {
                    let current = this.q.pre
                    this.q = current
                    this.q.next = this.head
                    this.head.pre = this.q
                }
                // 中间
                else {
                    // 和原来一样，取到前一个
                    let preNode = this.getElementAt(index - 1)
                    let current = preNode.next

                    preNode.next = current.next
                    current.next.pre = preNode

                }
                this.count--

            }


//最后的测试

看图删掉之后上一个是3，下个也是3

四、集合、字典、哈希表

4.1 集合

这里的集合基本和数学中的集合一致

可这么理解：它就由一组无序其唯一的项组成（这不就是set吗？）

集合的实现

开始实现，还是用对象作为存储数据的容器（容易保证唯一）

一个集合的数据结构通常有以下方法

• add(element)：向集合添加一个新元素。
• delete(element)：从集合移除一个元素。
• has(element)：如果元素在集合中，返回 true，否则返回 false。
• clear()：移除集合中的所有元素。
• size()：返回集合所包含元素的数量。它与数组的 length 属性类似。
• values()：返回一个包含集合中所有值（元素）的数组

比较简单直接看实现代码

 class Set {
            constructor() {
                this.container = {}
            }
            has(value) {
                return value in this.container
            }
            add(value) {
                if (this.has(value)) return false
                this.container[value] = value
            }
            delete(value) {
                if (!this.has(value)) return false
                delete this.container[value]
            }
            clear() {
                this.container = {}
            }
            size() {
                return Object.keys(this.container).length
            }
            value(){
                return Object.values(this.container)
            }
        }

集合的运算

我们要实现以下运算

• 并集
• 交集
• 差集
• 子集

并集

实现思路：把创建一个新集合，将集合a和集合b的数据放进去

        function union(set01, set02) {
            const newSet = new Set()
            set01.value().forEach(item => newSet.add(item))
            set02.value().forEach(item => newSet.add(item))
            return newSet
        }

交集

实现思路，还是借用一个新集合。然后随便拿一个a或b的数据进行操作，遍历操作时发现对方也有此数据就放到新集合

function intersection(set01, set02) {
            const newSet = new Set()
            set01.value().forEach(item => {
                if (set02.has(item)) {
                    newSet.add(item)
                }
            })
            return newSet
        }

差集A-B

实现思路：借助一个新集合，遍历a集合数据时，判断b中有无，有就剔除

        function difference(set01, set02) {
            const newSet = new Set()
            set01.value().forEach(item => {
                if (!set02.has(item)) {
                    newSet.add(item)
                }
            })
        }

子集

我们主要实现的方法是判断一个集合是否是另一个集合的子集

实现思路：如判断a集合是否是b集合的子集，我们要做的就是看a集合的所有元素是不是b中都有

       function isSubsetOf(a, b) {
            if (a.size() > b.size()) return false

            let flag = a.value().every(item => {
                return b.has(item)
            })

            return flag
        }

4.2 字典

上面我们实现了集合，知道集合就是存放了一组互不重复的元素。字典和它相差不多，只不过集合里面只是保存了值，而在这里是以键值对的方式保存的

我们接下来要实现以下功能

• set(key,value)：向字典中添加新元素。如果 key 已经存在，那么已存在的 value 会被新的值覆盖
• remove(key)：通过使用键作为参数来从字典中移除键值对应的数据值。
• hasKey(key)：如果某个键值存在于该字典中，返回 true，否则返回 false。
• get(key)：通过以键值作为参数查找特定的数值并返回。
• clear()：删除该字典中的所有值。
• isEmpty()：在 size 等于零的时候返回 true，否则返回 false。
• keys()：将字典所包含的所有键名以数组形式返回。
• values()：将字典所包含的所有数值以数组形式返回。
• keyValues()：将字典中所有[键，值]对返回。
• forEach(callbackFn)：迭代字典中所有的键值对。 callbackFn 有两个参数： key 和value。

这里都比较简单就直接上代码吧(简单的自己也没有怎么写测试代码，看思路就完事了)

        class Dictionary {
            constructor() {
                this.container = {}
            }

            // 根据指定键，判字典中有无
            hasKey(key) {
                return key in this.container
            }
            set(key, value) {
                if (key !== null && value !== null) {
                    this.container[key] = value
                }
            }
            remove(key) {
                if (this.hasKey(key)) {
                    delete this.container[key]

                }
            }
            get(key) {
                if (this.hasKey(key)) {
                    return this.container[key]
                } else {
                    return undefined
                }
            }
            keys() {
                return Object.keys(this.container)
            }
            values() {
                return Object.values(this.container)
            }
            keyValues() {
                return Object.entries(this.container)
            }
            size() {
                return this.keys().length
            }
            isEmpty() {
                return this.size() === 0
            }
            clear() {
                this.container = {}
            }

            forEach(fn) {
                const keys = this.keys()

                keys.forEach(item => fn(item, this.container[item]))
            }
        }

        const dic = new Dictionary();
        dic.set(1, "a");
        dic.set(2, "b");
        dic.set(3, "c");
        dic.set(4, "d");
        dic.set(5, "e");
        console.log(dic.hasKey(1));
        dic.remove(2);
        console.log(dic.get(3));
        console.log(dic.keyValues());
        console.log(dic.keys());
        dic.forEach((key, val) => {
            console.log(`key:${key} val:${val}`);

        })

4.3 哈希表

散列表的实现，拿获取值来说。它需要我们提供一个哈希哈数处理我们的key。使其能够快速定位到我们存储数据的存储单元。

这里我们会介绍两种哈希函数，当然好理解的有缺陷，不好理解的最好用。

djb2HashCode(目前最好用的哈希函数)

      function djb2HashCode(key) {
            const tableKey = this.toStrFn(key);
            let hash = 5381;
            for (let i = 0; i < tableKey.length; i++) {
                hash = (hash * 33) + tableKey.charCodeAt(i);
            }
            return hash % 1013;
        }

loseloseHashCode(好理解，它只是将字符串的ascii码与37取余)

        function loseloseHashCode(key) {
            if (typeof key === 'number') {
                return key;
            }
            let hash = 0;
            for (let i = 0; i < key.length; i++) {
                hash += tableKey.charCodeAt(i);
            }
            return hash % 37;
        }

哈希表的基本实现

 class HashTable {
            constructor() {
                this.table = {}
            }

            // 要使用的散列函数
            _loseloseHashCode(key) {
                if (typeof key === "number") {
                    return key
                } else {
                    let hash = 0;
                    for (let i = 0; i < key.length; i++) {
                        hash = hash + key.charCodeAt(i);
                    }
                    return hash % 37;
                }
            }
            put(key, value) {
                if (key != null && value != null) {
                    let position = this._loseloseHashCode(key)
                    this.table[position] = value
                }
            }
            get(key) {
                let position = this._loseloseHashCode(key)
                if (this.table[position]) {
                    return this.table[position]
                } else {
                    return undefined
                }
            }
            remove(key) {
                let position = this._loseloseHashCode(key)
                if (this.table[position]) {
                    delete this.table[position]
                    return true
                } else {
                    return false
                }
            }
        }

hash表完善之分离链接

如上丑图，键key1key2经过loseloseHashCode处理之后定位到的资源空间是同一块，为了防止数据覆盖的问题，我们将使用链表存放它们。虽然这里在链表中查找key1或key2时还是使用了线性查找。但是在这里也是没有法子的我们只能牺牲一下。不过注意的是我们这是在链表中保存的不止是val了。为了方便定位之后的线性查询我们要连key，val一块存在链表中。

实现

先拿过一个单链表来

        // 节点类
        class LNode {
            constructor(value) {
                this._value = value
                this._next = null //指针域
            }
        }

        //单链表类
        class LinkList {
            constructor() {
                this._head = null //头节点
                this._count = 0
            }
            push(value) {
                const node = new LNode(value)
                let current = this._head

                if (current === null) {
                    this._head = node
                } else {
                    // 不是空，顺着链条向下找,最后一个节点的指针域为空
                    while (current._next) {
                        current = current._next
                    }
                    current._next = node
                }

                this._count++
            }

            // 移出指定位置的节点
            removeAt(index) {
                if (!(index >= 0 && index < this._count)) return undefined
                let current = this._head
                if (index === 0) {
                    this._head = current._next
                }
                let previous;
                for (let i = 0; i < index - 1; i++) {
                    current = current._next
                }
                previous = current //指向要删除节点的前一个
                current = current._next //指向当前要删除节点
                previous._next = current._next

                this._count--;
                return current._value


            }

            // 获取指定位置的节点
            getElementAt(index) {
                if (!(index >= 0 && index < this._count)) return undefined
                let current = this._head
                for (let i = 0; i < index; i++) {
                    current = current._next
                }
                return current

            }

            // 在任意位置插入
            insert(value, index) {
                if (!(index >= 0 && index < this._count)) return undefined

                const node = new LNode(value)
                    // index==0
                if (index === 0) {
                    let current = this._head
                    this._head = node
                    this._head._next = current
                } else {
                    // 还是先找要操作的前一位置
                    let pre = this.getElementAt(index - 1)
                    let current = pre._next

                    pre._next = node
                    node._next = current

                }
                this._count++;

            }

            //返回指定节点元素的位置
            indexOf(value) {
                let current = this._head
                    //遍历一下链表即可
                for (let i = 0; i < this._count && current != null; i++) {
                    if (current._value === value) {
                        return i
                    } else {
                        current = current._next
                    }
                }
            }

            // 移出一个指定元素的节点
            remove(value) {
                let index = this.indexOf(value)
                this.removeAt(index)
            }

            //链表长度
            size() {
                return this._count
            }

            // 判空
            isEmpty() {
                return this.size === 0
            }

        }

改造哈希表,在借一个类用来存数据的key和value

  class Node {
            constructor(key, value) {
                this.key = key
                this.value = value
            }
        }
        class HashTable {
            constructor() {
                this.table = {}
            }

            // 要使用的散列函数
            _loseloseHashCode(key) {
                if (typeof key === "number") {
                    return key
                } else {
                    let hash = 0;
                    for (let i = 0; i < key.length; i++) {
                        hash = hash + key.charCodeAt(i);
                    }
                    return hash % 37;
                }
            }
            put(key, value) {
                if (key != null && value != null) {
                    let position = this._loseloseHashCode(key)
                        // 事先判断一下此位置是否有数据
                    if (!this.table[position]) {
                        this.table[position] = new LinkList()
                    }
                    this.table[position].push(new Node(key, value))
                }
            }
            get(key) {
                let position = this._loseloseHashCode(key)
                if (this.table[position]) {

                    let current = this.table[position].getHead()
                    while (current) {
                        if (current._value.key === key) {
                            return current._value.value
                        }
                        current = current.next
                    }
                    //没找到
                    return undefined
                } else {
                    return undefined
                }
            }
            remove(key) {
                let position = this._loseloseHashCode(key)
                if (this.table[position]) {
                    let current = this.table[position].getHead()

                    while (current) {
                        if (current._value.key === key) {
                            this.table[position].remove(current._value)

                            // 删除完如此时链表空了则删除它
                            if (this.table[position].isEmpty()) {
                                delete this.table[position]
                            }
                            return true
                        }
                        current = current._next
                    }
                    // 在链表中没有找到
                    return false

                } else {
                    return false
                }
            }
        }

        const h = new HashTable()
        h.put('name', 'gongxiaobai')
        h.put('name', 'zhangsan')
        h.put('age', '18')
        h.remove('age')
        console.log(h)
        console.log(h.get('name'))

如上的测试代码，用两个key一样的测试一下

hash表完善之线性探查

这个比分离链表还要简单一些，它是key定位到15的位置时发现为空就把它的信息节点保存到这，key也是定位15的，但是它来的晚一看已经被人占了。就向下找，找到一个空地就把自己的信息节点保存下来。

信息节点中的东西还是key和val。（方便查询）

逻辑实现还是很顺的，只不过有一个新的点要考虑。就是在节点删除的时候，比如上图我把key1删掉了。那么key2就会很尴尬。因为我们定位都是定位到key1的位置的，一判断key1的位置是空那我们下面实现的get和remove还怎么玩。我们连key2的信息都拿不到。因此在数据移出的时候我们要对它下面的元素位置进行修复(难点)

这里的难点就是移出节点还得修复

其实仔细想一下也不能，也就是把下面的经过哈希函数处理之后key相同的那些东西往上移动位置。

具体什么意思呢？就是这个线性探查首先是个数组一样，如上图左边的key是从上往下一次增大的（或者相等）。移出一个节点之后，我们要看看下面是否有与当前key的哈希值相同或者小于它的，有则需要向上一个坑一个坑的移动

  class Node {
            constructor(key, val) {
                this.key = key
                this.val = val
            }
        }
        class LineHashTable {
            constructor() {
                this.table = {}
            }

            // 先创建散列函数
            _loseloseHashCode(key) {
                if (typeof key === "number") {
                    return key
                } else {
                    let hash = 0
                    for (let i = 0; i < key.length; i++) {
                        hash = hash + key.charCodeAt(i)
                    }
                    return hash % 37
                }
            }

            // 新增一条到散列表
            put(key, val) {
                    if (key != null && val != null) {
                        const position = this._loseloseHashCode(key);
                        if (this.table[position] == null) {
                            // 为空放入节点
                            this.table[position] = new Node(key, val);
                        } else {
                            // 向下找空的储存空间
                            let index = position + 1;
                            while (this.table[index]) {
                                index++;
                            }
                            this.table[index] = new Node(key, val)
                        }
                        return true
                    }
                    return false
                }
                // 取值
            get(key) {
                let position = this._loseloseHashCode(key)

                //    先直接到lost函数所能快速定位的地方
                if (this.table[position] != null) {
                    // 再判是不是我们要的值
                    if (this.table[position].key === key) {
                        return this.table[position].val
                    }
                    // 不是则需要在此地的基础上向下寻找了
                    let index = position + 1
                    while (this.table[index] != null && this.table[index].key != key) {
                        index++
                    }
                    // 上面出来了有两种可能
                    // 1.找到目标
                    // 2.有一个空的地址
                    if (this.table[index].key === key) {
                        return this.table[index].val
                    } else {
                        return undefined
                    }

                }
                return undefined
            }

            // 移出值
            remove(key) {
                const position = this._loseloseHashCode(key);
                if (this.table[position] != null) {
                    // 判此时这个位置上的使我们要的吗
                    if (this.table[position].key === key) {
                        delete this.table[position]
                            // 修复下面的位置
                        this._move(key, position)
                        return true
                    } else {
                        let index = position + 1
                        while (this.table[index] != null && this.table[index].key !== key) {
                            index++
                        }
                        if (this.table[index].key === key) {
                            delete this.table[index]

                            // 修复下面的位置
                            this._move(key, index)
                            return true
                        } else {
                            return false
                        }
                    }

                }
                return false

            }

            //难点
            _move(key, removedPosition) {
                let hash = this._loseloseHashCode(key)
                let index = removedPosition + 1
                while (this.table[index] != null) {

                    let posHash = this._loseloseHashCode(this.table[index].key)
                        // 如果当前元素的 hash 值小于或等于原始的 hash 值（行{5}）或者当前元素的 hash 值小于或等于 removedPosition（也就是上一个被移除 key 的 hash 值），表示我们需要将当前元素移动至 removedPosition 的位置
                    if (posHash <= hash || posHash <= removedPosition) {
                        this.table[removedPosition] = this.table[index]
                        delete this.table[index]
                        removedPosition = index
                    }
                    index++
                }
            }
        }
        const h = new LineHashTable()
        h.put('name', 'gongxiaobai')
        h.put('name', 'zhangsan')
        h.put('age', '18')
        h.remove('age')
        console.log(h)
        console.log(h.get('name'))

参考书籍：

王道考研数据结构

严奶奶的那本（数据结构(C语言版) 第2版 (严蔚敏等)）

学习js数据结构与算法

写到最后

小白原来的笔记链接（有一些错误没有进行更改）

星光不问赶路人，时光不负有心人 期待着我们的下一次邂逅