2.js-集合、字典和散列表

集合和字典基本相同，唯一的区别，就是集合没有键和值的配对，是一系列无序的、唯一的元素组合（js中集合的实现Set、WeakSet,字典的实现Map、WeakMap）
1.集合是一种不允许值重复的顺序数据结构

//代码实现
// 我们使用对象而不是数组来表示集合 js对象不允许一个键指向两个不同的属性，集合里的元素都是唯一的
function Set(){
    let items = {}
    this.has = function(key){
        return key in items
        // return items.hasOwnProperty(key)
    }
    this.add = function(val){
        if(!this.has(val)){
            items[val]=val
            return true
        }
        return false;
    }
    this.delete = function(val){
        if(this.has(val)){
            delete items[val]
            return true
        }
        return false
    }
    this.clear = function(){
        items = {}
    }
    this.size = function(){
        return Object.keys(items).length
    }
    this.values = function(){
        let values = [];
        for(let i in items){
            values.push(items[i])
        }
        return values
    }
}

let set = new Set()
set.add("1")
console.log(
    set.add("2"),
    set.has("1"),
    set.delete("1"),
    set.clear(),
    set.has("2"),
    set.add("3"),
    set.size(),
    set.values())
let set1 = new Set(), set2 = new Set();
set1.add(1);
set1.add(2);
set2.add(2);
set2.add(3);
//并集
let values1 = set1.values(),values2 = set2.values();
let values3 = [...values1];
values2.forEach(item => {
    if(!set1.has(item)) values3.push(item)
});
//交集
values3 = values1.filter(item=>set2.has(item))
//差集
values3 = values1.filter(item=>!set2.has(item))
console.log(values3)

es6中set

image.png
2.字典和散列表
2.1 字典（在集合中我们感兴趣的是每个值本身，集合以[值：值]形式存储）在字典中存储的是[键：值]仍然唯一，其中键名是用来查询特定元素的。
ES6中的WeakMap的键只能是对象，并且它的键（对象）引用不计入垃圾回收机制中（举例：let a = {},arr = [a],a = null,这里js是不会将a的内存回收的因为arr中还存在着对a的引用，WeakMap中键如果其他地方没有在被引用，则会将该键内存回收，并且WeakMap会自动帮我们清除键为null（不在被引用的对象）的键值，如图） image.png
2.2 散列表：散列表是字典实现的一种特定方式，那为什么要以新方式实现字典呢，字典看上去根据key获得value值，但实际、还是需要遍历key看是否相等，是的话取出对应的值（散列算法：尽可能快地在数据结构中找到一个值，即散列函数给定一个键值，然后返回值在表中的作用）

//代码实现
let  m = require('./LinkedList'); //导入链表 后面需要用到链表结构在之前文章（https://www.jianshu.com/p/8ad9037b3307）有提到
// 散列函数
function loseloseHashCode(key){
    let hash = 0;
    for(let i = 0; i <  key.length;i++){
        hash += key.charCodeAt(i)
    }
    return hash;
}
// 优化的散列函数,
// 1.它包括初始化一个hash变量并赋值为一个质数，大多数实现都是使用5381
// 2.然后将hash和33相乘并于当前迭代ASCII码值相加，
// 3.最后我们将使用相加的和与另一个随机质数（比我们认为散列表大小要大）相除的余数
// function loseloseHashCode(key){
//     let hash = 5381;
//     for(let i = 0; i < key.length;i++){
//         hash += hash*33 + key.charCodeAt(i)
//     }
//     return hash%1013;
// }
function HashTable(){
    let table = [];
    this.put = function(key,value){
        // 最简单实现
        // let position = loseloseHashCode(key);
        // table[position] = value
        // 1.分离链接
        // let position = loseloseHashCode(key);
        // if(table[position] === undefined){
        //     table[position] = new m.LinkedList();
        // }
        // table[position].append(new ValuePair(key,value))
        // 2.线性探查
        let position = loseloseHashCode(key);
        while(table[position++]);
        table[position-1] = new ValuePair(key,value);
        
    }
    this.get = function(key){
        // 最简单实现
        // let position = loseloseHashCode(key);
        // return table[position];
        // 1.分离链接
        // let  position = loseloseHashCode(key);
        // if(table[position] !==undefined){
        //     let head = table[position].getHead();
        //     while(head){
        //         if(head.val.key === key){
        //             return head.val.value
        //         }
        //         head = head.next;
        //     }
        // }
        // 2.线性探查
        let  position = loseloseHashCode(key);
        while(table[position]){
            if(table[position].key === key){
                return table[position].value
            }
            position++;
        }
    }
    this.remove = function(key){
        // 最简单实现
        // let position = loseloseHashCode(key);
        // table[position] = undefined;
        // 1.分离链接
        // let  position = loseloseHashCode(key);
        // if(table[position] !==undefined){
        //     let head = table[position].getHead();
        //     let index = 0;
        //     while(head){
        //         if(head.val.key === key){
                    
        //             table[position].remove(index)
        //             ++index;
        //             if(table[position].isEmpty()){
        //                 table[position] = undefined
        //             }
        //             return;
        //         }
        //         head = head.next;
        //     }
        // }
        // 2.线性探查
        let  position = loseloseHashCode(key);
        while(table[position]){
            if(table[position].key === key){
                return table[position] = undefined
            }
             position++;
        }
    }
}
// 处理散列冲突（一些键值会有相同的散列值）分离链接，线性探查
// 1.分离链接是为散列表的每一个位置创建一个链表并将元素存储在里面 2.线性探查 如果索引为index位置已经被占据了，就尝试index+1的位置
// 为了实现一个分离链接和线性探查的HashTable实例，我们需要额外引入一个新的辅助类来表示将要加入LinkList实例的元素
function ValuePair(key,value){
    this.key = key;
    this.value = value;
}
let hashTable = new HashTable();
hashTable.put("w","1111111@11.com")
hashTable.put("Aaron","2222222@11.com")
hashTable.put("Tyrion","3333333@11.com")
console.log(hashTable.get("w"),hashTable.get("Aaron"),hashTable.get("Tyrion"))
hashTable.remove("Aaron")
console.log(hashTable.get("w"),hashTable.get("Aaron"),hashTable.get("Tyrion"))