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设备模型（中）之上层容器