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

HashTable.js

/* 散列表*/
// 缺点：键的冲突度较高
class HashTable {

    constructor() {
        this.table = [];
    }

    /* 散列函数 */
    loseloseHashCode(key) {
        let hash = 0;
        for (let i = 0; i < key.length; i++) {
            hash += key.chartCodeAt(i);
        }

        return hash % 37;
    }


    put(key, value) {
        const position = this.loseloseHashCode(key);
        this.table[position] = value;
    }

    remove(key) {
        const position = this.loseloseHashCode(key);
        this.table[position] = undefined; // 设置为undefined，不删除，避免改变其他元素的位置
    }

    get(key) {
        const position = this.loseloseHashCode(key);
        return this.table[position];
    }

    print() {
        for (let i = 0; i < table.length; ++i) {
            if (table[i] !== undefined) {
                console.log(i + ": " + table[i]);
            }
        }
    }
}


class ValuePair {
    constructor(key, value) {
        this.key = key;
        this.value = value;
    }
    toString = function() {
        return '[' + this.key + ' - ' + this.value + ']';
    }
}


/* 散列表*/
//  分离链接法包括为散列表的每一个位置创建一个链表并将元素存储在里面
class HashTable1 {

    constructor() {
        this.table = [];
    }

    /* 散列函数(djb2) */
    djb2HashCode(key) {
        let hash = 5381;
        for (let i = 0; i < key.length; i++) {
            hash = hash * 33 + key.chartCodeAt(i);
        }

        return hash % 1013;
    }


    put(key, value) {
        const position = this.djb2HashCode(key);
        if (this.table[position] === undefined) {
            this.table[position] = new LinkedList();
        }
        this.table[position].append(new ValuePair(key, value));
    }

    get(key) {
        const position = this.djb2HashCode(key);
        if (this.table[position] !== undefined) {
            /// 遍历链表
            let current = this.table[position].getHead();
            while (current.next) {
                if (current.next.key === key) {
                    return current.next.element.value;
                }
                current = current.next;
            }

            if (current.element.key === key) {
                return current.element.value;
            }

        }
        return undefined
    }

    remove(key) {
        const position = this.djb2HashCode(key);

        if (this.table[position] !== undefined) {
            let current = this.table[position].getHead();
            while (current.next) {
                if (current.next.element.key === key) {
                    this.table[position].remove(current.element);
                    if (this.table[position].isEmpty()) {
                        this.table[position] = undefined;
                    }
                    return true;
                }
                current = current.next;
            }

            if (current.element.key === key) {
                this.table[position].remove(current.element);
                if (this.table[position].isEmpty()) {
                    this.table[position] = undefined;
                }
                return true;
            }
        }
        return false;
    }


    print() {
        for (let i = 0; i < table.length; ++i) {
            if (table[i] !== undefined) {
                console.log(i + ": " + table[i].toString());
            }
        }
    }
}


/* 线性探查 */
// 另一种解决冲突的方法是线性探查。当想向表中某个位置加入一个新元素的时候，如果索引
// 为index的位置已经被占据了，就尝试index+1的位置。如果index+1的位置也被占据了，就尝试
// index+2的位置，以此类推
class HashTable2 {

    constructor() {
        this.table = [];
    }

    /* 散列函数(djb2) */
    djb2HashCode(key) {
        let hash = 5381;
        for (let i = 0; i < key.length; i++) {
            hash = hash * 33 + key.chartCodeAt(i);
        }

        return hash % 1013;
    }


    put(key, value) {
        let position = this.djb2HashCode(key);
        if (this.table[position] === undefined) {
            this.table[position] = new ValuePair(key, value);
        } else {
            let index = ++position;
            while (this.table[index] !== undefined) {
                index++;
            }
            table[index] = new ValuePair(key, value);
        }
    }

    get(key) {
        let position = this.djb2HashCode(key);
        if (this.table[position] !== undefined) {
            if (this.table[position].key === key) {
                return this.table[position].value;
            } else {
                let index = ++position;
                while (this.table[index] === undefined || this.table[index].key !== key) {
                    index++;
                }

                if (this.table[index].key === key) {
                    return this.table[index].value;
                }
            }
        }
        return undefined;
    }

    remove(key) {
        let position = this.djb2HashCode(key);
        if (this.table[position] !== undefined) {
            if (this.table[position].key === key) {
                this.table[position] = undefined;
                return true;
            } else {
                let index = ++position;
                while (this.table[index] === undefined || this.table[index].key !== key) {
                    index++;
                }
                if (this.table[index].key === key) {
                    this.table[index] = undefined;
                    return true;
                }
            }
        }
        return false;
    }


    print() {
        for (let i = 0; i < table.length; ++i) {
            if (table[i] !== undefined) {
                console.log(i + ": " + table[i].toString());
            }
        }
    }
}

HashTable2 的 remove后会有空值，要循环处理下。