字典
字典数据结构
- 在字典(或映射)中,我们用[键,值]对的形式来存储数据,其中键用来查询特定的元素
- 在字典中的每个键只能有一个值
帮助方法或类
- 判断元素是否存在
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; } }