学习js数据结构与算法5—字典和散列表

字典和散列表

• 集合、字典和散列表可以存储不重复的值
• 集合以[值，值]的形式存储元素，字典和散列表以[键，值]的形式存储

7.1 字典

    // 创建一个字典
    function Map() {
        var items = {};
        /*
            set(key, val): 向字典中添加新元素
            remove(key): 通过键值从字典中移除对应的数据
            has(key):如果键存在字典中返回true,否则false
            get(key):通过键值查找特定的数值并返回
            clear():将这个字典中的所有元素删除
            size():返回字典所包含的元素个数
            keys():将字典中包含的所有键名以数组形式返回
            values():将字典中包含的所有数值以数组形式返回
         */
    
        // has(key)方法
        this.has = function (key) {
            return items.hasOwnProperty(keys);
        };
        // set(key, val)方法
        this.set = function (key, val) {
            items[key] = val;
        };
    
        // remove(key)方法
        this.remove = function (key) {
            if (this.has(key)) {
                delete items[key];
                return true;
            }
            return false;
        };
        // get(key)方法
        this.get = function (key) {
            return this.has(key) ? items[key] : undefined;
        };
        // values()方法
        this.values = function () {
            return Object.values(items);
        };
        // keys()方法
        this.keys = function () {
            return Object.keys(items);
        };
        // clear()方法
        this.clear = function () {
            items = {};
        };
        // size()方法
        this.size = function () {
            return Object.keys(items).length;
        };
        // getItems()方法
        this.getItems = function () {
            return items;
        };
    }
    // 使用Map类
    var m = new Map();
    m.set('Gandalf', 'gmail@email.com');
    m.set('John', 'john@gmail.com');
    m.set('TFBoys', 'tfboys@360.cn');
    console.log(m.has('Gandalf'));  // true
    console.log(m.size());
    console.log(m.keys());
    console.log(m.values());
    console.log(m.get('jay'));
    
    m.remove("John");
    console.log(m.keys());
    console.log(m.values());
    console.log(m.getItems());

7.2 散列表

    散列算法的作用是尽可能快地在数据结构里找到一个值
        散列函数的作用是给定一个键值，然后返回值在表中的位置
        
    // 创建一个散列表
    function HashTable() {
        var table = [];
    
        // 良好的散列函数
        var hashPosCode = function (key) {
            var hash = 5381;
            for (var i = 0; i < key.length; i++) {
                hash = hash * 33 + key.charCodeAt(i);
            }
            return hash % 1013;
        };
    
        // put方法，向散列表增加一项
        this.put = function (key, val) {
            var pos = hashPosCode(key);
            table[pos] = val;
        };
    
        // remove方法，根据键值删除值
        this.remove = function (key) {
            table[hashPosCode(key)] = undefined;
        };
    
        // get方法，返回根据键值找到的值
        this.get = function (key) {
            return table[hashPosCode(key)];
        };
    
        this.print = function () {
            for (var i = 0; i < table.length; i++) {
                if (table[i] !== undefined) {
                    console.log(i + ':' + table[i]);
                }
            }
        };
    }
    
    var hash = new HashTable();
    hash.put('Gandalf', 'g@email.com');
    hash.put('Sue', 'sue@360.cn');
    hash.put('Donnie', 'Donnie@fox.me');
    hash.put('Ana', 'Ana@gmail.com');
    hash.put('Jonathan', 'Jonathan@baidu.com');
    hash.print();