javascript 數(shù)據(jù)結(jié)構(gòu)系列

tianhang 發(fā)布于2019-08-21 10:50 / 2899人閱讀

摘要：也就是說(shuō)，它通過(guò)計(jì)算一個(gè)關(guān)于鍵值的函數(shù)，將所需查詢(xún)的數(shù)據(jù)映射到表中一個(gè)位置來(lái)訪問(wèn)記錄，這加快了查找速度。這個(gè)映射函數(shù)稱(chēng)做散列函數(shù)，存放記錄的數(shù)組稱(chēng)做散列表。如果對(duì)象沒(méi)有該實(shí)例化該處為一對(duì)象如果該不存在就增加一個(gè)數(shù)量

本系列一系列文章的收集關(guān)于javascript中的數(shù)據(jù)結(jié)構(gòu)

如果你對(duì)數(shù)據(jù)結(jié)構(gòu)不太熟悉可以看這篇文章
如果你只想看代碼可以看這篇文章
如果你只想star 可以去這里

什么是數(shù)據(jù)結(jié)構(gòu)

在計(jì)算機(jī)科學(xué)或信息學(xué)中，數(shù)據(jù)結(jié)構(gòu)（英語(yǔ)：data structure）是計(jì)算機(jī)中存儲(chǔ)、組織數(shù)據(jù)的方式 From Wikipedia

完整wiki解釋地址

沒(méi)有一種數(shù)據(jù)結(jié)構(gòu)是完美的你需要了解所有數(shù)據(jù)結(jié)構(gòu)的優(yōu)勢(shì)和劣勢(shì) 合理的運(yùn)用數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)自己目標(biāo)

復(fù)雜性

算法的復(fù)雜性是算法優(yōu)勢(shì)和劣勢(shì)的一種體現(xiàn) 算法復(fù)雜性包括空間復(fù)雜性和時(shí)間復(fù)雜性

空間復(fù)雜性大概或許就是數(shù)據(jù)結(jié)構(gòu)所需要使用的內(nèi)存數(shù)量
時(shí)間復(fù)雜性大概或許就是時(shí)間啦

如何選擇合適的算法

依賴(lài)選擇的數(shù)據(jù)

array

An Array data structure, or simply an Array, is a data structure consisting of a collection of elements (values or variables), each identified by at least one array index or key. The simplest type of data structure is a linear array, also called one-dimensional array. From Wikipedia

js 有array結(jié)構(gòu)不過(guò)不是很強(qiáng)大我們可以自定義一下一個(gè)加強(qiáng)版

class MyArray {
    constructor() {
        this.array = [];
    }

    add(data) {
        return this.array.push(data);
    }

    remove(data) {
        // 如果找到數(shù)據(jù)就刪除
        if(~this.array.indexOf(data)) {
            this.array.splice(this.array.indexOf(data), 1);
        }
    }

    search(data) {
        // 如果找打數(shù)據(jù)就返回
        if(~this.array.indexOf(data)) {
            return this.array.indexOf(data);
        } else {
            return null;
        }
    }

    getAtIndex(index) {
        return this.array[index];
    }

    length() {
        return this.array.length;
    }

    print() {
        console.log(this.array.reduce(function(prev, curr) {
            return prev + curr + " ";
        }, "").trim());
    }
}

hashtable

散列表（Hash table，也叫哈希表），是根據(jù)關(guān)鍵字（Key value）而直接訪問(wèn)在內(nèi)存存儲(chǔ)位置的數(shù)據(jù)結(jié)構(gòu)。也就是說(shuō)，它通過(guò)計(jì)算一個(gè)關(guān)于鍵值的函數(shù)，將所需查詢(xún)的數(shù)據(jù)映射到表中一個(gè)位置來(lái)訪問(wèn)記錄，這加快了查找速度。這個(gè)映射函數(shù)稱(chēng)做散列函數(shù)，存放記錄的數(shù)組稱(chēng)做散列表。

class HashTable {
    constructor(size) {
        this.values = {};
        this.numberOfValues = 0;
        this.size = size;
    }
    add(key, value) {
        var hash = this.calculateHash(key);
        // 如果對(duì)象沒(méi)有該key  實(shí)例化該key處為一對(duì)象
        if(!this.values.hasOwnProperty(hash)) {
            this.values[hash] = {};
        }
        // 如果該key不存在 就增加一個(gè)數(shù)量
        if(!this.values[hash].hasOwnProperty(key)) {
            this.numberOfValues++;
        }
        this.values[hash][key] = value;
    }
    remove(key) {
        var hash = this.calculateHash(key);
        if(this.values.hasOwnProperty(hash) &&  this.values[hash].hasOwnProperty(key)) {
            delete this.values[hash][key];
            this.numberOfValues--;
        }
    }
    calculateHash(key) {
        return key.toString().length % this.size;
    }
    search(key) {
        var hash = this.calculateHash(key);
        if(this.values.hasOwnProperty(hash) &&  this.values[hash].hasOwnProperty(key)) {
            return this.values[hash][key];
        } else {
            return null;
        }
    }
    length() {
        return this.numberOfValues;
    }
    print() {
        var string = "";
        for(var value in this.values) {
            for(var key in this.values[value]) {
                string += this.values[value][key] + " ";
            }
        }
        console.log(string.trim());
    }
}