散列表

散列表

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

HashTable类的模拟实现

下面我们来模拟实现自己的HashTable类，也叫HashMap类。

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();
}
class ValuePair {
    constructor(key, value) {
        this.key = key;
        this.value = value;
    }
    toString() {
        return `[#${this.key}: ${this.value}}]`;
    }
}
class HashTable {
    // 构造函数
    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;
    }
    // 获取某一个键的hash值
    HashCode(key) {
        return this.loseloseHashCode(key);
    }
    // 将键和值加入散列表
    put(key, value) {
        if (key != null && value != null) {
            const position = this.HashCode(key);
            this.table[position] = new ValuePair(key, value);
            return true;
        }
        return false;
    }
    // 从散列表中获取一个值
    get(key) {
        const valuePair = this.table[this.HashCode(key)];
        return valuePair == null ? undefined : valuePair.value;
    }
    // 从散列表移除一个值
    remove(key) {
        const hash = this.HashCode(key);
        const valuePair = this.table[hash];
        if (valuePair != null) {
            delete this.table[hash];
            return true;
        }
        return false;
    }
}

这里就不再演示HashTable类中方法的使用了，有兴趣的可以自己做个demo测试一下，如果有任何的问题，欢迎评论区留言。

Donate