天天看点

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;
        }
    }
               

继续阅读