JavaScript資料結構與算法之 "字典和散清單"

字典

字典資料結構

在字典(或映射)中，我們用[鍵,值]對的形式來存儲資料，其中鍵用來查詢特定的元素
在字典中的每個鍵隻能有一個值

幫助方法或類

判斷元素是否存在

const isExist = (element) => {
    return element !== undefined && element !== null;
};

字元串轉換函數

/*将傳入的參數轉換為字元串*/
const toStr = (param) => {
    if (param === null) {
        return 'NULL';
    } else if (param === undefined) {
        return 'UNDEFINED';
    } else if (typeof param === 'number' || param instanceof Number) {
        return `${param}`;
    } else if (typeof param === 'string' || param instanceof String) {
        return `${param}`;
    } else if (typeof param === 'symbol') {
        return param;
    } else {
        return JSON.stringify(param);
    }
};

建立存儲鍵值對對象的類

/*建立存儲鍵值對對象的類*/
class KeyValuePair {
    constructor(key, value) {
        this.key = key;
        this.value = value;
    }

    toString() {
        return `[${this.key}:${this.value}]`;
    }
}

建立字典資料結構

字典的方法
- set(key,value)：向字典中添加新元素，如果key已經存在那麼新的值會覆寫舊的值
- hasKey(key)：判斷某個key是否存在于字典中，存在傳回true，否則傳回false
- get(key)：通過特定的key查找值并傳回
- clear()：删除字典中的所有的值
- size()：傳回字典中所包含值的數量。與數組的length屬性類似
- isEmpty()：判斷字典中是否有值，有傳回true，否則傳回false
- keys()：将字典中所有的鍵以數組的形式傳回
- values()：将字典中所有的值以數組的形式傳回
- keyValues()：将字典中所有的[鍵,值]以數組的形式傳回
- forEach(callback)：将函數callback用于字典中的每個鍵值對。callback有兩個參數：key和value
- toString()

代碼

/*建立字典的類*/
class Dictionary {
    constructor() {
        this.table = {}; //存儲字典中元素的table對象
    }

    //  set(key,value)：向字典中添加新元素，如果key已經存在那麼新的值會覆寫舊的值
    set(key, value) {
        if (isExist(key) && isExist(value)) {
            const name = toStr(key);
            this.table[name] = new KeyValuePair(key, value);
            return true;
        }

        return false;
    }

    //  hasKey(key)：判斷某個key是否存在于字典中，存在傳回true，否則傳回false
    hasKey(key) {
        const name = toStr(key);
        return Object.prototype.hasOwnProperty.call(this.table, name);
    }

    //  get(key)：通過特定的key查找值并傳回
    get(key) {
        const name = toStr(key);
        const result = this.table[name];
        return isExist(result) ? result.value : undefined;
    }

    //  clear()：删除字典中的所有的值
    clear() {
        this.table = {};
    }

    //  size()：傳回字典中所包含值的數量。與數組的length屬性類似
    size() {
        return Object.keys(this.table).length;
    }

    //  isEmpty()：判斷字典中是否有值，有傳回true，否則傳回false
    isEmpty() {
        return this.size() === 0;
    }

    //  keys()：将字典中所有的鍵以數組的形式傳回
    keys() {
        return this.keyValues().map(v => v.key);
    }

    //  values()：将字典中所有的值以數組的形式傳回
    values() {
        return this.keyValues().map(v => v.value);
    }

    //  keyValues()：将字典中所有的[鍵,值]以數組的形式傳回
    keyValues() {
        return Object.values(this.table);
    }

    //  forEach(callback)：将函數callback用于字典中的每個鍵值對。callback有兩個參數：key和value
    forEach(callback) {
        const kvs = this.keyValues();
        const len = kvs.length;
        for (let i = 0; i < len; i += 1) {
            callback(kvs[i].key, kvs[i].value);
        }
    }

    // toString()
    toString() {
        if (this.isEmpty()) {
            return '';
        }

        const kvs = this.keyValues();
        const len = kvs.length;
        let str = `${kvs[0].toString()}`;

        for (let i = 1; i < len; i += 1) {
            str = `${str},${kvs[i].toString()}`;
        }

        return str;
    }
}

散清單

散清單是字典的一種實作。
散列清單可以用作關聯數組，也可以用來對資料庫進行索引。另一個很常見的應用是使用散清單來表示對象，JavaScript内部就是使用散清單來表示每個對象。
散清單算法的作用是盡可能快的在資料結構中找到一個值。散列函數的作用是給定一個鍵值，然後傳回值在表中的位址。

散清單資料結構的實作

散列函數

作用：散列函數的作用是将傳入的鍵轉換為數值的方法
一個良好的散列函數由幾個方面構成：
- 插入和檢索元素的時間（即性能）
- 較低的沖突性

djb2散列函數

djb2散列函數是社群最受推崇的散列函數之一

實作

_djb2HashCode(key) {
        const tableKey = toStr(key);
        let hash = 5381;

        for (let i = 0, len = tableKey.length; i < len; i += 1) {
            hash = (hash * 33) + tableKey.charCodeAt(i)
        }
        
        //tableSize：散清單的大小，是一個整數，預設是 1013
        return hash % this.tableSize;
    }

處理散清單中的沖突
- 有時一些鍵會有相同的散列值。不同的值在散清單中對應相同位置的時候，我們稱其為沖突。
- 解決散列沖突的辦法：
  - 分離連結
  - 線性探查
  - 雙散列法
  - 我們采用線性探查來解決散列沖突的問題
- 線性探查
  - 之是以稱做線性，是因為它處理沖突的方法是将元素直接存儲到表中，而不是在單獨的資料結構中
  - 如果向表中某個位置添加一個新元素，如果目前位置被占據了就嘗試使用下一個位置，如果下一個位置也被占據了就嘗試使用下下個位置，直到在散清單中找到一個空閑位置。
方法
- _djb2HashCode(key)：将傳入的key轉換為哈希值
- _clearDeleteSideEffect(key, removedPosition)：清除删除元素的副作用
- put(key,value)：向散清單中增加一個新的項，該方法也能用于更新散清單
- remove(key)：根據key從散清單中移除值
- get(key)：根據key檢索到特定的值
- isEmpty()：判斷散清單是否為空，為空傳回true，否則傳回false
- size()：傳回散清單的大小，類似數組的length屬性
- clear()：清空散清單
- getTable()：擷取散清單中的表
- toString()：

代碼

class HashTable {
    /**
     * @param tableSize {number} 散清單的大小，預設是 1013
     */
    constructor(tableSize) {
        this.table = {};  // 存儲散清單元素的對象
        this.tableSize = (tableSize && typeof tableSize === 'number') ? tableSize : 1013;
    }

    // _djb2HashCode(key)：将傳入的key轉換為哈希值
    _djb2HashCode(key) {
        const tableKey = toStr(key);
        let hash = 5381;

        for (let i = 0, len = tableKey.length; i < len; i += 1) {
            hash = (hash * 33) + tableKey.charCodeAt(i)
        }

        return hash % this.tableSize;
    }

    // 清除删除元素的副作用
    _clearDeleteSideEffect(key, removedPosition) {
        const hash = this._djb2HashCode(key);
        let index = removedPosition + 1;  // 散清單中被删除元素的哈希位置的下一個位置

        while (isExist(this.table[index])) {
            const currentHash = this._djb2HashCode(this.table[index].key);  // 目前元素key的hash
            // 如果目前元素key的hash小于等于原始的hash值或小于等于上一個被移除元素的hash值(removePosition)
            if (currentHash <= hash || currentHash < removedPosition) {
                this.table[removedPosition] = this.table[index];
                delete this.table[index];
                removedPosition = index;
            }

            // index移到下一個位置
            index += 1;
        }
    }

    // put(key,value)：向散清單中增加一個新的項，該方法也能用于更新散清單
    put(key, value) {
        if (isExist(key) && isExist(value)) { // key 和value都存在
            const position = this._djb2HashCode(key); // 擷取key在散清單中的哈希位置

            if (!isExist(this.table[position])) { // 目前位置沒有元素
                this.table[position] = new KeyValuePair(key, value);
            } else { // 目前位置沒有元素
                let index = position + 1;
                while (isExist(this.table[index])) {
                    index += 1;
                }
                this.table[index] = new KeyValuePair(key, value);
            }
            return true;
        }

        // key 或value不存在
        return false;
    }

    // remove(key)：根據key從散清單中移除值
    remove(key) {
        const position = this._djb2HashCode(key);
        console.log(position);
        // 散清單 position位置不存在元素
        if (!isExist(this.table[position])) {
            return false;
        }

        // 散清單 position位置存在元素且key等于傳入的key
        if (this.table[position].key === key) {
            delete this.table[position];  // 移除元素
            this._clearDeleteSideEffect(key, position);  // 清除删除元素的副作用
            return true;
        }

        let index = position + 1;
        while (isExist(this.table[index]) && this.table[index].key !== key) {
            index += 1;
        }

        if (isExist(this.table[index]) && this.table[index].key === key) {
            delete this.table[index];  // 移除元素
            this._clearDeleteSideEffect(key, index);  // 清除删除元素的副作用
            return true;
        }
    }

    // get(key)：根據key檢索到特定的值
    get(key) {
        const position = this._djb2HashCode(key);
        if (!isExist(this.table[position])) { // 散清單 position位置不存在元素
            return undefined;
        }

        if (this.table[position].key === key) { // 散清單 position位置存在元素且key等于傳入的key
            return this.table[position].value;
        }

        let index = position + 1;
        while (isExist(this.table[index]) && this.table[index].key !== key) {
            index += 1;
        }

        if (isExist(this.table[index]) && this.table[index].key === key) {
            return this.table[index].value;
        }
    }

    // isEmpty()：判斷散清單是否為空，為空傳回true，否則傳回false
    isEmpty() {
        return this.size() === 0;
    }

    // size()：傳回散清單的大小，類似數組的length屬性
    size() {
        return Object.keys(this.table).length;
    }

    // clear()：清空散清單
    clear() {
        this.table = {};
    }

    // getTable()：擷取散清單中的表
    getTable() {
        return this.table;
    }

    // toString()：
    toString() {
        if (this.isEmpty()) {
            return '';
        }

        const positions = Object.keys(this.table);
        let str = `${positions[0]} -> ${this.table[positions[0]].toString()}`;
        for (let i = 1, len = positions.length; i < len; i += 1) {
            str = `${str} , ${positions[i]} -> ${this.table[positions[i]].toString()}`;
        }
        return str;
    }
}

JavaScript資料結構與算法之 "字典和散清單"

字典

字典資料結構

幫助方法或類

建立字典資料結構

散清單

散清單資料結構的實作

繼續閱讀

Javascript建構Bingo卡片遊戲

JavaScript的那些坑之事件代理事件代理事件階段

javascript的for (var i in data)慎用javascript中的for (var i in data)謹慎用

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

tab滑鼠經過菜單切換

vue （vue2.0）使用總結(從大體結構總結)

vue搭建過程及出現問題

/\B(?=(?:\d{3})+$)/g 一條令人費解的正規表達式

适用于JavaScript的ECMAScript 2020規範向前發展

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

JS生成uuid的四種方法

layui多任務上傳添加進度條

Linux裝置模型（中）之上層容器