学习JavaScript数据结构与算法（七）——散列表（一）

散列技术是在记录的存储位置和它的关键字之间建立一个确立的对应关系f，使得每个关键字key对应一个存储位置f(key)。查找时，根据这个确定的对应关系找到给定值key的映射f(key)，若查找集合中存在这个记录，则必定在f(key)的位置上。其中，对应关系f成为散列函数，又称为哈希函数。

采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表。关键字对应的记录存储位置称为散列地址。

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

一、创建一个散列表

function HashTable () {

    var table = [];

    /*
    散列函数，是HashTable类中的一个私有方法。
    给定一个参数key，根据组成key的每个字符的ASCII码值得和得到一个数字。
     */
    var loseloseHashCode = function(key){
        var hash = ;//存储总和
        //遍历key并将ASCII表查到的每个字符对应的ASCII值加到hash变量中
        for (var i = ; i < key.length; i++) {
            hash += key.charCodeAt(i);
        }
        //为了得到比较小的数值，会使用hash值和一个任意数做除数的余数
        return hash % ;
    };

    /*
    put(key,value)
    向散列表增加一个新的项（也能更新散列表）。
     */
    this.put = function(key, value){
        var position = loseloseHashCode(key);
        console.log(position + ' - ' + key);
        table[position] = value;
    };

    /*
    remove(key)
    根据键值从散列表中移除值。
     */
    this.remove = function(key){
        table[loseloseHashCode(key)] = undefined;
    };

    /*
    get(key)
    返回根据键值检索到的特定的值。
     */
    this.get = function(key){
        return table[loseloseHashCode(key)];
    };

}
           

二、使用HashTable类

var hash = new HashTable();

hash.put('Jack', '[email protected]');
hash.put('John', '[email protected]');
hash.put('Ben', '[email protected]');

console.log(hash.get('Jack'));
console.log(hash.get('Lily'));

hash.remove('Ben');
console.log(hash.get('Ben'));
           

测试结果如下：

三、散列集合

散列集合由一个集合构成，但是插入、移除或获取元素时，使用的是散列函数。

散列集合只存储唯一的不重复的值。