第4章 哈希表

哈希表

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

//ValuePair类用于存储原始的key和value
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;
    }

    hashCode(key) {
        return this.loseloseHashCode(key);
    }

    //1.向哈希表添加一个新的项
    put(key, value) {
        if (key != null && value != null) {
            const position = this.hashCode(key);
            this.table[position] = new ValuePair(key, value);
            return true;
        }
        return false;
    }

    //2.返回根据键值检索到的特定的值
    get(key) {
        const ValuePair = this.table[this.hashCode(key)];
        return ValuePair == null ? undefined : ValuePair.value;
    }

    //3.根据键值从哈希表中移除值
    remove(key) {
        const hash = this.hashCode(key);
        const valuePair = this.table(hash);
        if (valuePair != null) {
            delete this.table(hash);
            return true;
        }
        return false;
    }

    //4.返回字典中值的个数
    size() {
        return Object.keys(this.table).length;
    }

    //5.判空
    isEmpty() {
        return this.size() === 0;
    }

    //6.转换为字符串
    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;
    }
}

解决冲突（链地址法）

class HashTableSeparateChaining {
    constructor(toStrFn = defaultToString) {
        this.toStrFn = toStrFn;
        this.table = {};
    }

    //loseloseHashCode(key) {} 同上

    //hashCode(key) {} 同上

    //1.向哈希表添加一个新的项
    put(key, value) {
        if (key != null && value != null) {
            const position = this.hashCode(key);
            if (this.table[position] == null) {
                this.table[position] = new LinkedList();
            }
            this.table[position].push(new ValuePair(key, value));
            return true;
        }
        return false;
    }

    //2.返回根据键值检索到的特定的值
    get(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) {
                    return current.element.value;
                }
                current = current.next;
            }
        }
        return undefined;
    }

    //3.根据键值从哈希表中移除值
    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;
    }
}