数据结构与算法-字典和散列表

发表于 更新于 分类于
本文字数： 16k 阅读时长 ≈ 27 分钟

《学习JavaScript数据结构与算法(第3版)》

在字典（或映射）中，我们用[键，值]对的形式来存储数据。在散列表中也是一样（也是以[键，值]对的形式来存储数据）。

字典数据结构

在字典中，存储的是[键，值]对，其中键名是用来查询特定元素的。字典和集合很相似，集合以[值，值]的形式存储元素，字典则是以[键，值]的形式来存储元素。字典也称作映射、符号表或关联数组。

字典经常用来保存对象的引用地址。

将在一个 Object 的实例而不是数组中存储字典中的元素。我们会将[键，值]对保存为 table[key] = {key, value}。

function defaultToString(item) {
    if (item === null) {
        return 'NULL';
    } else if (item === undefined) {
        return 'UNDEFINED';
    } else if (typeof item === 'string' || item instanceof String) {
        return `${item}`;
    }
    return item.toString(); // 如果item是对象的话，则需要实现toString方法，否则输出会导致出现异常输出结果
}

// 为了保存原始的key和value
export class ValuePair {
    constructor(key, value) {
        this.key = key;
        this.value = value;
    }
    toString() {
        return `[#${this.key}: ${this.value}]`;
    }
}

export default class Dictionary {
    constructor(toStrFn = defaultToString) {
        this.toStrFn = toStrFn; // 转换为字符串
        this.table = {};
    }

	// 向字典中添加新元素或更新元素的值。如果key已存在，则已存在的value会被新的值覆盖
    set(key, value) {
        if (key != null && value != null) { // 判断键和值的合法性
            const tableKey = this.toStrFn(key); // 将所有键名转换为字符串，使得从Dictionary类中搜索和获取值更简单
            this.table[tableKey] = new ValuePair(key, value); // 保存原始的key和value
            return true;
        }
        return false;
    }
    
    // 通过以键值作为参数查找特定的数值并返回
    get(key) {
        const valuePair = this.table[this.toStrFn(key)]; // 检索存储在给定key属性中的对象
        return valuePair == null ? undefined : valuePair.value;
    }
    
    // 如果某个键值存在于该字典中，返回true，否则返回false
    hasKey(key) {
        return this.table[this.toStrFn(key)] != null; // 统一键名格式
    }
    
    // 通过使用键值作为参数来从字典中移除键值对应的数据值
    remove(key) {
        if (this.hasKey(key)) { // 先判断是否存在待删除键值
            delete this.table[this.toStrFn(key)];
            return true;
        }
        return false;
    }
    
    // 将字段所包含的所有数值以数组形式返回
    values() {
        return this.keyValues().map(valuePair => valuePair.value);
    }
    
    // 将字典所包含的所有数值以数组形式返回
    keys() {
        return this.keyValues().map(valuePair => valuePair.key);
    }
    
    // 以数组的形式将字典中所有[键, 值]对返回
    keyValues() {
        return Object.values(this.table);
    }
    
    // 迭代字典中所有的键值对，可以再回调函数返回false时被终止
    forEach(callbackFn) {
        const valuePairs = this.keyValues(); // 获取所有键值构成的数组
        for (let i = 0; i < valuePairs.length; i++) {
            const result = callbackFn(valuePairs[i].key, valuePairs[i].value);
            if (result === false) {
                break;
            }
        }
    }
    
    // 判断当前字典是否为空
    isEmpty() {
        return this.size() === 0;
    }
    
    // 返回字典所包含值的数量
    size() {
        return Object.keys(this.table).length;
    }
    
    // 删除该字典中的所有值
    clear() {
        this.table = {};
    }
    
    // 输出字典
    toString() {
        if (this.isEmpty()) { // 如果字典为空，则返回空字符串
            return '';
        }
        const valuePairs = this.keyValues();
        let objString = `${valuePairs[0].toString()}`; // 初始值为第一个元素的值
        for (let i = 1; i < valuePairs.length; i++) { // 如果还有值，则继续加入后续元素的值
            objString = `${objString},${valuePairs[i].toString()}`;
        }
        return objString; // 返回最终字符串
    }
}

散列表数据结构

HashTable，也叫 HashMap，是 Dictionary 类的一种散列表实现方式。

散列算法的作用是尽可能快地在数据结构中找到一个值。

散列函数的作用是给定一个键值，然后返回值在表中的地址。

哈希函数时从关键字集合到地址集合的映像。

常见的应用是使用散列表来表示对象。 JavaScript 语言内部就是使用散列表来表示每个对象。

lose lose 散列函数，方法是简单地将每个键值中的每个字母的 ASCII 值相加后取余。

取余的基数选择很重要，如果选的不好，容易产生冲突。一般情况下，可以选基数为质数或不包含小于20的质因数的和数。

function defaultToString(item) {
    if (item === null) {
        return 'NULL';
    } else if (item === undefined) {
        return 'UNDEFINED';
    } else if (typeof item === 'string' || item instanceof String) {
        return `${item}`;
    }
    return item.toString(); // 如果item是对象的话，则需要实现toString方法，否则输出会导致出现异常输出结果
}

// 为了保存原始的key和value
export class ValuePair {
    constructor(key, value) {
        this.key = key;
        this.value = value;
    }
    toString() {
        return `[#${this.key}: ${this.value}]`;
    }
}

export default class HashTable {
    constructor(toStrFn = defaultToString) {
        this.toStrFn = toStrFn;
        this.table = {};
    }
    
    // 散列函数
    loseloseHashCode(key) {
        if (typeof key === 'number') { // 检查key值类型
            return key;
        }
        const tableKey = this.toStrFn(key); // 将key值转换为字符串，防止key是一个对象而不是字符串
        let hash = 0; // 使用hash变量来存储这个总和
        for (let i = 0; i < tableKey.length; i++) { // 遍历key的字符 获得每个字符的ASCII值总和
            hash += tableKey.charCodeAt(i); // 将从ASCII表中查到的每个字符对应的ASCII值加到hash变量中
        }
        // 为了得到比较小的数值，会使用hash值和一个任意数做除法的余数，可以规避操作数超过数值变量最大表示范围的风险
        return hash % 37;
    }
    
    /* djb2HashCode(key) {
        const tableKey = this.toStrFn(key);
        let hash = 5381;
        for (let i = 0; i < tableKey.length; i++) {
          hash = (hash * 33) + tableKey.charCodeAt(i);
        }
        return hash % 1013;
      } */
    
    // 通过散列函数计算出key对应的hash值
    hashCode(key) {
        return this.loseloseHashCode(key);
    }
    
    // 向散列表增加一个新的项（或更新散列表）
    put(key, value) {
        if (key != null && value != null) { // 检查key和value是否合法
            const position = this.hashCode(key); // 通过计算出key值找到位置
            this.table[position] = new ValuePair(key, value); // 保存或更新值 
            return true;
        }
        return false;
    }
    
    // 返回根据键值检索到的特定的值
    get(key) {
        const valuePair = this.table[this.hashCode(key)]; // 通过计算得出key值
        return valuePair == null ? undefined : valuePair.value;
    }
    
    // 根据键值从散列表中移除值
    remove(key) {
        const hash = this.hashCode(key); // 获取到hash值
        const valuePair = this.table[hash]; // 在hash位置获取到值
        if (valuePair != null) { // 如果存在则删除 并返回true
            delete this.table[hash];
            return true;
        }
        // 如果不存在返回false
        return false;
    }
    
    getTable() {
        return this.table;
    }
    
    isEmpty() {
        return this.size() === 0;
    }
    
    size() {
        return Object.keys(this.table).length;
    }
    
    clear() {
        this.table = {};
    }
    
    toString() {
        if (this.isEmpty()) {
            return '';
        }
        const keys = Object.keys(this.table);
        let objString = `{${keys[0]} => ${this.table[keys[0]].toString()}}`;
        for (let i = 1; i < keys.length; i++) {
            objString = `${objString},{${keys[i]} => ${this.table[keys[i]].toString()}}`;
        }
        return objString;
    }
}

散列表和散列映射是一样的。

散列集合由一个集合构成，但是插入、移除或获取元素时，使用的是 hashCode 函数。不同之处在于，不再添加键值对，而是只插入值而没有键。和集合相似，散列集合只存储不重复的唯一值。也就是说只存 key 转换的 hash 值的集合。

处理散列表中的冲突

有时候，一些键会有相同的散列值。不同的值在散列表中对应相同位置的时候，我们称其为冲突。

使用一个数据结构来保存数据的目的显然不是丢失这些数据，而是通过某种方法将它们全部保存起来。因此，当这种情况发生的时候就要去解决。处理冲突有几种方法：分离链接、线性探查和双散列法。

分离链接

分离链接法包括为散列表的每一个位置创建一个链表并将元素存储在里面。它是解决冲突的最简单的方法，但是在 HashTable 实例之外还需要额外的存储空间。

// 使用LinkedList数据结构，重写了 put、get、remove方法
import { defaultToString } from '../util';
import LinkedList from './linked-list'; // 使用链表数据结构
import { ValuePair } from './models/value-pair';

export default class HashTableSeparateChaining {
    constructor(toStrFn = defaultToString) {
        this.toStrFn = toStrFn;
        this.table = {};
    }
    loseloseHashCode(key) {
        if (typeof key === 'number') {
            return key;
        }
        const tableKey = this.toStrFn(key);
        let hash = 0;
        for (let i = 0; i < tableKey.length; i++) {
            hash += tableKey.charCodeAt(i);
        }
        return hash % 37;
    }
    hashCode(key) {
        return this.loseloseHashCode(key);
    }
    put(key, value) {
        if (key != null && value != null) {
            const position = this.hashCode(key);
            if (this.table[position] == null) { // 验证要加入新元素的位置是否已经被占据
                this.table[position] = new LinkedList(); // 第一次在该位置添加元素初始化一个LinkedList实例
            }
            this.table[position].push(new ValuePair(key, value)); // 将值添加到该位置的LinkedList中
            return true;
        }
        return false;
    }
    get(key) {
        const position = this.hashCode(key);
        const linkedList = this.table[position]; // 获取该位置上的LinkedList对象
        if (linkedList != null && !linkedList.isEmpty()) { // 如果该位置上的LinkedList对象有效
            let current = linkedList.getHead(); // 获取链表表头引用
            while (current != null) { // 迭代链表，链尾的next为null
                if (current.element.key === key) { // 对比key值，来确认是否是查找的元素
                    return current.element.value; // 如果是要找的元素，返回Node
                }
                // 比较方法二：在创建链表的时候传入自定义函数equalsFn，在对比的时候就可以直接调用indexOf查找位置
                current = current.next; // 如果不是要找的元素，继续迭代链表
            }
        }
        return undefined; // 获取的LinkedList对象是无效的
    }
    remove(key) {
        const position = this.hashCode(key);
        const linkedList = this.table[position];
        if (linkedList != null && !linkedList.isEmpty()) {
            let current = linkedList.getHead();
            while (current != null) {
                if (current.element.key === key) { // 找到链表后 删除链表当前位置
                    linkedList.remove(current.element);
                    if (linkedList.isEmpty()) { // 如果当前链表空了，就将散列表的该位置删除
                        delete this.table[position];
                    }
                    return true; // 删除成功
                }
                current = current.next; // 如果没有找到，继续下一个迭代
            }
        }
        return false; // 删除失败
    }
    isEmpty() {
        return this.size() === 0;
    }
    size() {
        let count = 0;
        Object.values(this.table).forEach(linkedList => {
            count += linkedList.size();
        });
        return count;
    }
    clear() {
        this.table = {};
    }
    getTable() {
        return this.table;
    }
    toString() {
        if (this.isEmpty()) {
            return '';
        }
        const keys = Object.keys(this.table);
        let objString = `{${keys[0]} => ${this.table[keys[0]].toString()}}`;
        for (let i = 1; i < keys.length; i++) {
            objString = `${objString},{${keys[i]} => ${this.table[
                keys[i]
            ].toString()}}`;
        }
        return objString;
    }
}
线性查探

线性探查，之所以称作线性，是因为它处理冲突的方法是将元素直接存储到表中，而不是在单独的数据结构中。

当想向表中某个位置添加一个新元素的时候，如果索引为position的位置已经被占据了，就尝试position+1的位置。如果position+1的位置也被占据了，就尝试position+2的位置，以此类推，直到在散列表中找到一个空闲的位置。想象一下，有一个已经包含一些元素的散列表，我们想要添加一个新的键和值。我们计算这个新键的hash，并检查散列表中对应的位置是否被占据。如果没有，我们就将该值添加到正确的位置。如果被占据了，我们就迭代散列表，直到找到一个空闲的位置。

线性探查技术分为两种。第一种是软删除方法。我们使用一个特殊的值（标记）来表示键值对被删除了（惰性删除或软删除），而不是真的删除它。经过一段时间，散列表被操作过后，我们会得到一个标记了若干删除位置的散列表。这会逐渐降低散列表的效率，因为搜索键值会随时间变得更慢。能快速访问并找到一个键是我们使用散列表的一个重要原因。

// 惰性删除的实现，重写put、get、remove
// 缺点：散列表会越来越大，查找效率会越来越低
import { defaultToString } from '../util';
import { ValuePair } from './value-pair';

export class ValuePairLazy extends ValuePair {
  constructor(key, value, isDeleted = false) {
    super(key, value);
    this.key = key;
    this.value = value;
    this.isDeleted = isDeleted; // 软删除，记录删除状态
  }
}

export default class HashTableLinearProbingLazy {
    constructor(toStrFn = defaultToString) {
        this.toStrFn = toStrFn;
        this.table = {};
    }
    loseloseHashCode(key) {
        if (typeof key === 'number') {
            return key;
        }
        const tableKey = this.toStrFn(key);
        let hash = 0;
        for (let i = 0; i < tableKey.length; i++) {
            hash += tableKey.charCodeAt(i);
        }
        return hash % 37;
    }
    hashCode(key) {
        return this.loseloseHashCode(key);
    }
    put(key, value) {
        if (key != null && value != null) { // 判断插入值的有效性
            const position = this.hashCode(key);
            if (
                this.table[position] == null ||
                (this.table[position] != null && this.table[position].isDeleted)
            ) { // 判断当前hash位置为空或有无效数据
                // 新增或替换为新元素
                this.table[position] = new ValuePairLazy(key, value);
            } else { // 如果当前hash位置有元素，则往下寻找新的hash空位
                let index = position + 1;
                // 直到找到空位或无效值为止
                while (this.table[index] != null && !this.table[position].isDeleted) {
                    index++;
                }
                // 新增或替换为新元素
                this.table[index] = new ValuePairLazy(key, value);
            }
            // 插入成功
            return true;
        }
        // 无效插入元素
        return false;
    }
    get(key) {
        const position = this.hashCode(key); // 计算出待获取元素的hash位置
        if (this.table[position] != null) { // 当前hash位置元素不为空
            // 当前hash位置元素为待查找元素，且不处于删除状态，则返回元素值
            if (this.table[position].key === key && !this.table[position].isDeleted) {
                return this.table[position].value;
            }
            // 如果当前hash位置不为带查找元素，则往后遍历查找
            let index = position + 1;
            // 一直循环到空位 或查找到未被删除的待查找元素
            while (
                this.table[index] != null &&
                (this.table[index].key !== key || this.table[index].isDeleted)
            ) {
                // 是待查元素但处于删除状态 返回undefined
                if (this.table[index].key === key && this.table[index].isDeleted) {
                    return undefined;
                }
                index++;
            }
            // 如果循环结果不为空 且 值等于待查找元素 且未为删除状态，则返回待查找元素的值
            if (
                this.table[index] != null &&
                this.table[index].key === key &&
                !this.table[index].isDeleted
            ) {
                return this.table[position].value;
            }
        }
        return undefined;
    }
    remove(key) {
        const position = this.hashCode(key);
        if (this.table[position] != null) {
            // 删除元素
            if (this.table[position].key === key && !this.table[position].isDeleted) {
                this.table[position].isDeleted = true;
                return true;
            }
            // 未查找到待删除元素，则需要进行迭代
            let index = position + 1;
            // 循环到空位 或找到未被删除的待删除元素
            while (
                this.table[index] != null &&
                (this.table[index].key !== key || this.table[index].isDeleted)
            ) {
                index++;
            }
            // 判断循环结果是否是有效的待删除元素，如果是则修改删除状态
            if (
                this.table[index] != null &&
                this.table[index].key === key &&
                !this.table[index].isDeleted
            ) {
                this.table[index].isDeleted = true;
                return true;
            }
        }
        return false;
    }
    isEmpty() {
        return this.size() === 0;
    }
    size() {
        let count = 0;
        Object.values(this.table).forEach(valuePair => {
            count += valuePair.isDeleted === true ? 0 : 1;
        });
        return count;
    }
    clear() {
        this.table = {};
    }
    getTable() {
        return this.table;
    }
    toString() {
        if (this.isEmpty()) {
            return '';
        }
        const keys = Object.keys(this.table);
        let objString = `{${keys[0]} => ${this.table[keys[0]].toString()}}`;
        for (let i = 1; i < keys.length; i++) {
            objString = `${objString},{${keys[i]} => ${this.table[
                keys[i]
            ].toString()}}`;
        }
        return objString;
    }
}

第二种方法需要检验是否有必要将一个或多个元素移动到之前的位置。当搜索一个键的时候，这种方法可以避免找到一个空位置。如果移动元素是必要的，我们就需要在散列表中挪动键值对。

// 重写put、get、remove
// 缺点：每次删除元素时，需要挪动之前存入元素的位置
import { defaultToString } from '../util';
import { ValuePair } from './value-pair';

export default class HashTableLinearProbing {
    constructor(toStrFn = defaultToString) {
        this.toStrFn = toStrFn;
        this.table = {};
    }
    loseloseHashCode(key) {
        if (typeof key === 'number') {
            return key;
        }
        const tableKey = this.toStrFn(key);
        let hash = 0;
        for (let i = 0; i < tableKey.length; i++) {
            hash += tableKey.charCodeAt(i);
        }
        return hash % 37;
    }
    hashCode(key) {
        return this.loseloseHashCode(key);
    }
    put(key, value) {
        if (key != null && value != null) {
            const position = this.hashCode(key);
            if (this.table[position] == null) { // 验证当前位置是否有元素存在
                this.table[position] = new ValuePair(key, value); // 如果为空，则在这个位置添加新元素
            } else {
                let index = position + 1; // 如果这个位置被占了，需要找到下一个没有被占据的位置
                while (this.table[index] != null) { // 验证该位置是否被占据，直到找到一个没有被占据的位置
                    index++; // 如果占据则继续往下找
                }
                this.table[index] = new ValuePair(key, value); // 将新元素分配到这个没有被占据的位置
            }
            return true;
        }
        return false;
    }
    get(key) {
        const position = this.hashCode(key);
        if (this.table[position] != null) { // 当前键是否存在
            if (this.table[position].key === key) { // 若存在，则检查是否是待取元素
                return this.table[position].value; // 如果是，则返回待取元素的值
            }
            // 不是待取元素，则继续下一个位置查找
            let index = position + 1;
            // 按位置递增的顺序查找散列表上的元素直到找到我们要找的元素或者空位置
            while (this.table[index] != null && this.table[index].key !== key) {
                index++;
            }
            // 验证循环跳出找到的位置，验证该位置元素是否是待取元素，如果是则返回值，如果不是则表示不存在
            if (this.table[index] != null && this.table[index].key === key) {
                return this.table[position].value;
            }
        }
        // 当前键不存在
        return undefined;
    }
    remove(key) {
        const position = this.hashCode(key);
        if (this.table[position] != null) {
            if (this.table[position].key === key) {
                delete this.table[position]; // 删除找到的元素值
                this.verifyRemoveSideEffect(key, position); // 验证是否有副作用
                return true;
            }
            let index = position + 1;
            while (this.table[index] != null && this.table[index].key !== key) {
                index++;
            }
            if (this.table[index] != null && this.table[index].key === key) {
                delete this.table[index]; // 如果有冲突被处理了，在另一个位置找到了该元素
                this.verifyRemoveSideEffect(key, index); // 验证是否有副作用
                return true;
            }
        }
        return false;
    }
    // 由于我们不知道在散列表的不同位置上是否存在具有相同hash的元素，需要验证删除操作是否有副作用。
    // 如果有，就需要将冲突的元素移动至一个之前的位置，这样就不会产生空位置，影响其他操作。
    verifyRemoveSideEffect(key, removedPosition) { // 接受参数：被删除的key和该key被删除的位置
        const hash = this.hashCode(key); // 获取被删除key的hash值
        let index = removedPosition + 1; // 从被删除位的下一个位置开始迭代
        // 迭代元素，直到找到空位。当空位被找到后，表示元素都在合适的位置上，不需要移动
        while (this.table[index] != null) {
            const posHash = this.hashCode(this.table[index].key); // 当前的元素值的hash
            // 如果当前元素的hash值小于等于原始的hash值 或小于等于被移除key的hash值
            if (posHash <= hash || posHash <= removedPosition) {
                this.table[removedPosition] = this.table[index]; // 需要将当前元素移动至被移除key的位置
                delete this.table[index]; // 移动完之后删除当前元素
                removedPosition = index; // 记录被移动位置
            }
            index++;
        }
    }
    isEmpty() {
        return this.size() === 0;
    }
    size() {
        return Object.keys(this.table).length;
    }
    clear() {
        this.table = {};
    }
    getTable() {
        return this.table;
    }
    toString() {
        if (this.isEmpty()) {
            return '';
        }
        const keys = Object.keys(this.table);
        let objString = `{${keys[0]} => ${this.table[keys[0]].toString()}}`;
        for (let i = 1; i < keys.length; i++) {
            objString = `${objString},{${keys[i]} => ${this.table[
                keys[i]
            ].toString()}}`;
        }
        return objString;
    }
}
减少冲突

一个表现良好的散列函数是由几个方面构成的：插入和检索元素的时间（即性能），以及较低的冲突可能性。

比 lose lose 更好的散列函数是 djb2

使用这种方法得到的散列表更大，减少了冲突。

djb2HashCode(key) {
    const tableKey = this.toStrFn(key); // 将键转换为字符串
    let hash = 5381; // 初始化一个hash变量为质数（大多数为5381）
    for (let i = 0; i < tableKey.length; i++) { // 迭代参数key
        // 33作为幻数（在编程中直接使用的常数）
        hash = (hash * 33) + tableKey.charCodeAt(i); // 将hash乘以33并和当前迭代到的字符ASCII码值相加
    }
    return hash % 1013; // 最后相加的和与另一个随机质数进行取余
}
散列函数
构造方法
  1. 直接定址法
  2. 数字分析法
  3. 平方取中法：取关键字平方后的中间几位为哈希地址。较为常用。
  4. 折叠法：将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这及部分的叠加和（舍去进位）作为哈希地址。
  5. 除留取余法：取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。这是最简单也是最常用的方法。
  6. 随机数法：选择一个随机函数，取关键字的随机函数值为它的哈希地址。通常，当关键字长度不等时采用此法构造哈希函数较恰当。

考虑因素：

  1. 计算哈希函数所需时间（包括硬件指令的因素）；
  2. 关键字的长度；
  3. 哈希表的大小；（JS不用过多考虑这个方面的问题）
  4. 关键字的分布情况；
  5. 记录的查找频率。