JavaScript数据结构与算法-散列练习

散列的实现

// 散列类 - 线性探测法
function HashTable () {
    this.table = new Array(137);
    this.values = [];
    this.simpleHash = simpleHash;
    this.betterHash = betterHash;
    this.showDistro = showDistro;
    this.put = put;
    this.get = get;
}
function put (key, data) {
    let pos = this.betterHash(key);
    // this.table[pos] = data;
    if (this.table[pos] === undefined) {
        this.table[pos] = key;
        this.values[pos] = data;
    } else {
        while (this.table[pos] !== undefined) {
            ++pos;
        }
        this.table[pos] = key;
        this.values[pos] = data;
    }
}
function get (key) {
    // return this.table[this.betterHash(key)];
    let hash = -1;
    hash = this.betterHash(key);
    if (hash > -1) {
        for (let i = hash; this.table[hash] !== undefined; ++i) {
            if (this.table[hash] === key) {
                return this.values[hash];
            }
        }
    }
    return undefined;
}
function simpleHash (data) {
    let total = 0;
    for (let i = 0; i < data.length; ++i) {
        total += data.charCodeAt(i);
    }
    return total % this.table.length;
}
function showDistro () {
    let n = 0;
    for (let i = 0; i < this.table.length; ++i) {
        if (this.table[i] !== undefined) {
            console.log(`${i}: ${this.table[i]}`);
        }
    }
}
function betterHash (string) {
    const H = 7;
    let total = 0;
    for (let i = 0; i < string.length; ++i) {
        total += H * total + string.charCodeAt(i);
    }
    total = total % this.table.length;
    if (total < 0) {
        total += this.table.length -1;
    }
    return parseInt(total, 10);
}

练习

使用线性探测法创建一个字典，用来保存单词的定义。该程序需要包含两个部分：第一部分将一组单词和它们的定义存储进散列表；第二部分让用户输入单词，程序给出该单词的定义。

// 字典类
function Dict () {
    this.hashTable = new HashTable();
    this.save = save;
    this.find = find;
}
function save (word, description) {
    this.hashTable.put(word, description);
}
function find (word) {
    return this.hashTable.get(word);
}
// 示例
let d = new Dict();
d.save('Mazey', 'a strong man.');
d.save('Cherrie', 'a beautiful girl.');
d.save('John', 'unknown.');
console.log(d.find('John')); // unknown.
console.log(d.find('Mazey')); // a strong man.
console.log(d.find('Ada')); // undefined