map 和 对象的一个区别
map的键值可以区分不同类型 ,不会发生类型转换
而对象的键值都会转化为字符串(用 toString)
let map = new Map();
let obj = {};
/ 设置
map.set(1,2);
map.set('1','aaa');
/ 设置
obj[1] = 2;
obj['1'] = 'aaa';
/ 取值
console.log(map.get(1));/ 1
console.log(obj[1]);/ aaa
console.log(map.get('1'));/ aaa
console.log(obj['1']);/ aaa
map 的增删改查
增
map.set(1,2);
查
map.get(1);/2
map.has(1);/true
删
map.delete(1);
map.clear()
map 可以用引用值的 地址作为 key
map.set(obj,1);
console.log(map.get(obj));/1
初始化时 传值
let map = new Map([['name','mike'],['age',18],['sex','male']]);
console.log(map.get('name'));/ mike
map版 数组去重
Array.prototype.uniche = function () {
let map = new Map();
let resArr = [];
this.forEach(item => {
if (!map.has(item)) {
map.set(item,1);
resArr.push(item);
}
})
return arr;
}
丁老师版map 封装
// 封装map
function myMap() {
this.init();
}
myMap.prototype.bucket = [];
myMap.prototype.len = 8;
// 通过key 转换成 value
myMap.prototype.makeHash = function(key) {
let hash = 0;
if(typeof key === "string") {
// 取后三位进行处理
let len = (key.len > 3) ? key.length : 3;
for(let i = len - 3; i < len; i++) {
hash += key[i] !== undefined ? key[i].charCodeAt() : 0;
}
} else {
hash = +key
}
return hash;
}
myMap.prototype.init = function() {
// 生成桶
let len = this.len;
for(let i = 0; i < len; i++) {
this.bucket[i] = {
next: null
};
}
}
myMap.prototype.set = function(key, value) {
// 算出hash值
let hash = this.makeHash(key);
// 根据 hash 找到桶
let list = this.bucket[hash % this.len];
// 根据链表 遍历 这个桶
let nextNode = list;
while(nextNode.next) {
if(nextNode.key === key) {
nextNode.value = value;
return
} else {
nextNode = nextNode.next;
}
}
nextNode.next = {
key,
value,
next: null
};
return this;
}
myMap.prototype.get = function(key) {
let hash = this.makeHash(key);
let list = this.bucket[hash % this.len];
let nextNode = list;
while(nextNode.next) {
if(nextNode.key === key) {
return nextNode.value;
} else {
nextNode = nextNode.next;
}
}
return undefined
}
myMap.prototype.delete = function(key) {
let hash = this.makeHash(key);
let list = this.bucket[hash % this.len];
let nextNode = list;
while(nextNode.next) {
if(nextNode.next.key === key) {
nextNode.next = nextNode.next.next;
return true
} else {
nextNode = nextNode.next;
}
}
return false
}
myMap.prototype.clear = function() {
this.init();
}
myMap.prototype.has = function(key) {
let hash = this.makeHash(key);
let list = this.bucket[hash % this.len];
let nextNode = list;
while(nextNode.next) {
if(nextNode.key === key) {
return true;
} else {
nextNode = nextNode.next;
}
}
return false
}
let map = new myMap();
丁老师讲课确实牛逼, 深入浅出自是不必多说,
关键是 风格感觉很干净.
写代码, 或者问题什么的, 都感觉''轻轻''敲,''轻轻''分析,就都能解决.
我发现我自己不是这样的, 遇到问题,苦大仇深的.
发现上面的封装有一个问题.
他不会遍历出最后一个
比如
map.set(1,1);
map.set(1,2);
console.log(map.get(1));/1
console.log(map);//
image.png
会发现没有覆盖, 这是因为最后一个没有被遍历
稍微修改一下
function myMap() {
this.init();
}
myMap.prototype.bucket = [];
myMap.prototype.len = 8;
// 通过key 转换成 value
myMap.prototype.makeHash = function(key) {
let hash = 0;
if(typeof key === "string") {
// 取后三位进行处理
let len = (key.len > 3) ? key.length : 3;
for(let i = len - 3; i < len; i++) {
hash += key[i] !== undefined ? key[i].charCodeAt() : 0;
}
} else if (isNaN(key)) {
hash = 0;
} {
hash = +key
}
// 引用值是怎么处理的?
return hash;
}
myMap.prototype.init = function() {
// 生成桶
let len = this.len;
for(let i = 0; i < len; i++) {
this.bucket[i] = {
next: null
};
}
}
myMap.prototype.get = function(key) {
let hash = this.makeHash(key);
let list = this.bucket[hash % this.len];
let nextNode = list;
while(nextNode) {
if(nextNode.key === key) {
return nextNode.value;
} else {
nextNode = nextNode.next;
}
}
return undefined
}
myMap.prototype.delete = function(key) {
let hash = this.makeHash(key);
let list = this.bucket[hash % this.len];
let nextNode = list;
while(nextNode) {
if(nextNode.next.key === key) {
nextNode.next = nextNode.next.next;
return true
} else {
nextNode = nextNode.next;
}
}
return false
}
myMap.prototype.clear = function() {
this.init();
}
myMap.prototype.has = function(key) {
let hash = this.makeHash(key);
let list = this.bucket[hash % this.len];
let nextNode = list;
while(nextNode) {
if(nextNode.key === key) {
return true;
} else {
nextNode = nextNode.next;
}
}
return false
}
myMap.prototype.set = function(key, value) {
// 算出hash值
let hash = this.makeHash(key);
// 根据 hash 找到桶
let list = this.bucket[hash % this.len];
// 根据链表 遍历 这个桶
let prev = null;
let nextNode = list;
while(nextNode) {
if(nextNode.key === key) {
nextNode.value = value;
return
} else {
prev = nextNode;
nextNode = nextNode.next;
}
}
prev.next = {
key,
value,
next: null
};
return this;
}
let map = new myMap();
内存回收机制 : 两种
1.定时清理回收
2.内存达到一定量时回收
set 特点
有序列表, 包含相互独立且不相等的值
最快的数组去重?
let arr = [1,2,3,4,5,6,1,2,3,4,5,6];
let set = new Set(arr);
arr = [...set];
console.log(arr);
作业 根据上面的map封装, 写一下 set封装
只需要改一下 set api 改成 add , 去掉value 就可以了
myMap.prototype.add = function(key) {
// 算出hash值
let hash = this.makeHash(key);
// 根据 hash 找到桶
let list = this.bucket[hash % this.len];
// 根据链表 遍历 这个桶
let prev = null;
let nextNode = list;
while(nextNode) {
if(nextNode.key === key) {
return
} else {
prev = nextNode;
nextNode = nextNode.next;
}
}
prev.next = {
key,
next: null
};
return this;
}
new Set(arr)的时候的数据处理
function myMap(arr) {
this.init();
arr.forEach(item => {
this.add(item)
})
}
new Map(obj)的时候的数据处理
同理
function myMap(obj) {
this.init();
for(var key in obj) {
if (obj.hasOwnProperty(key)) {
this.set(key,obj[key])
}
}
}
思考,
总结: map的封装,主要是用了两个东西
一个是哈希算法, 另一个是链表结构.
链表结构的遍历实际上也没什么, 跟数组的遍历也差不多.
哈希算法本身也没什么,
关键是通过哈希算法, 把本来一维的数据存储方式, 改成了二维.
先分成八个组, 根据key转换的哈希值, 将数据放入相应的组中.
用多维的方式降低遍历次数,
但精彩的地方在于
通常我们想要完成多维的数据存储, 则需要多个坐标.
比如
var obj = {
key1 : 1,
key2 : 2,
...
//以上key值可以看成是各个维度的坐标.
value : 'value'
}
坐标就是需要和其他坐标不同,
哈希算法的应用高明之处就在于, 用一个key值,
生成了另一个坐标(key值)
再思考一下, 通过哈希算法, 我们只能生成一个 坐标嘛?
有没有可能生成 多个坐标? 进而按照多个维度进行存储?
哈希算法的基础是, 把一切key值,都变成数字.然后取余
所以要研究一下数字.
最简单的考虑是
我们分别 用 不同的数进行取值, 生成多个哈希值
比如
function makehash (num) {
let hash = {};
hash[0] = num%2;
hash[1] = num%3;
hash[2] = num%4;
hash[3] = num%5;
hash[4] = num%6;
hash[5] = num%7;
hash[6] = num%8;
hash[7] = num%9;
console.log(hash);
}
makehash(100);
makehash(101);
image.png
可以看到这是可以的,也不知道会存在什么限制
但感觉, 可以通过这种方式生成很多维度的坐标
也许 有一个限制是, 这个数字本身的大小最好应该比维度数要小?
否则性能反而降低? 也就是存储的数据数量太少就没有必要?
makehash(2);
makehash(1);
image.png
另一个问题是,
有没有可能完全用 哈希算法生成的 多维度坐标, 唯一确定该值?
换到map 这道题就是, 能不能只通过坐标,
而不用链表进行遍历就可以找到value?
换句话说,一串哈希值是唯一的嘛?
应该不是唯一的, 当然这应该需要数学上的证明啊什么的Hash算法总结
确实不能,假设数据量可以无限增大, 必然会有重复, 也就是'碰撞'
不过感觉这个哈希算法,很有用啊, 起码以后在数据存储的时候,
可以考虑用这种方法.
用es6语法写了一下
class myMap {
constructor(arr = []) {
this.init(arr);
}
// 生成八个桶头.
init(arr) {
for(let i = 0; i < this.len; i++) {
this.bucket[i] = {
next: null
}
}
arr.forEach(([key,value]) => {
this.set(key,value);
})
}
// 返回 哈希值
makeHash(key) {
let hash = 0;
// 如果是字符串, 截取后三位
if(typeof key == "string") {
let len = key.length > 3 ? 3 : key.length;
for(let i = key.length - len; i < key.length; i++) {
hash += key[i] !== undefined ? key[i].charCodeAt() : 0;
}
} else if(isNaN(key)) {
hash = 0
} else {
hash = +key;
}
return hash % this.len;
}
set(key, value) {
// 先计算是哪个桶.找到桶头
let head = this.bucket[this.makeHash(key)];
// 开始遍历该桶, 需要设置一个遍历索引,
let node = head;
let prev = null;
while(node) {
if(node.key === key) {
node.value = value;
return
} else {
prev = node;
node = node.next
}
}
prev.next = {
key,
value,
next: null
}
}
get(key) {
let head = this.bucket[this.makeHash(key)];
// 开始遍历该桶, 需要设置一个遍历索引,
let node = head;
let prev = null;
while(node) {
if(node.key === key) {
return node.value;
} else {
prev = node;
node = node.next
}
}
return undefined;
}
has (key) {
let head = this.bucket[this.makeHash(key)];
// 开始遍历该桶, 需要设置一个遍历索引,
let node = head;
let prev = null;
while(node) {
if(node.key === key) {
return true;
} else {
prev = node;
node = node.next
}
}
return false;
}
del (key) {
let head = this.bucket[this.makeHash(key)];
let node = head;
let prev = null;
while(node) {
if(node.next.key === key) {
node.next = node.next.next;
return true;
} else {
prev = node;
node = node.next
}
}
return false;
}
clear () {
this.init();
}
}
myMap.prototype.bucket = [];
myMap.prototype.len = 8;
可以看到, 美中不足在于, bucket,len 不能直接放,
也许可以用 set,get?
我们发现, 自己模拟的 map 没有迭代器.
无法进行迭代,无法使用 for of
另一个问题是, bucket 放在了原型上, 导致不同实例之间会产生影响.
bucket 放在 实例上
constructor (arr = []) {
this.bucket = [];
this.init(arr)
}
模拟迭代器
*[Symbol.iterator]() {
// 问题变成了如何遍历一遍整个桶?
for(let i = 0; i < this._len; i++) {
let head = this.bucket[i];
let node = head.next;
while (node){
yield [node.key,node.value]
node = node.next;
}
}
}
贴一遍完整版
class myMap {
constructor (arr = []) {
this.bucket = [];
this.init(arr)
}
get _len () {
return 8
}
init (arr) {
for(let i = 0; i < this._len; i++) {
this.bucket[i] = {
next : null
}
}
arr.forEach(([key,value]) => {
this.set(key,value)
})
}
makeHash (key) {
let hash = 0;
if (Object.is(key,NaN)) {
hash = 0;
}else if (typeof key == "string") {
let len = key.length > 3 ? 3 : key.length;
for(let i = key.length - len; i < key.length; i++) {
hash += typeof key[i] !== "undefined" ? key[i].charCodeAt() : 0;
}
}else {
hash = +key
}
return hash%8
}
set (key, value) {
let head = this.bucket[this.makeHash(key)];
let node = head;
let prev = node;
while (node){
if (node.key === key) {
node.value = value
return
}
prev = node;
node = node.next;
}
prev.next = {
key,
value,
next : null
}
return
}
has (key) {
let head = this.bucket[this.makeHash(key)];
let node = head;
let prev = node;
while (node){
if (node.key === key) {
return true;
}
node = node.next;
}
return false
}
get (key) {
let head = this.bucket[this.makeHash(key)];
let node = head;
let prev = node;
while (node){
if (node.key === key) {
return node.value;
}
node = node.next;
}
return undefined
}
del (key) {
let head = this.bucket[this.makeHash(key)];
let node = head;
let prev = node;
while (node){
if (node.key === key) {
return prev.next = prev.next.next
}
prev = node;
node = node.next;
}
return undefined
}
clear () {
this.init();
}
*[Symbol.iterator]() {
// 问题变成了如何遍历一遍整个桶?
for(let i = 0; i < this._len; i++) {
let head = this.bucket[i];
let node = head.next;
while (node){
yield [node.key,node.value]
node = node.next;
}
}
}
}
let map = new myMap([["a",1],["b",3],["c",3]]);
网友评论