散列的实现

// 散列类 - 线性探测法

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

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