html css js

5. map 哈希算法+ 链表结构进行封装

"Hello World, Hello Blog"

Posted by wudimingwo on December 15, 2018

map 和 对象的一个区别 map的键值可以区分不同类型 ,不会发生类型转换 而对象的键值都会转化为字符串(用 toString) ``` let map = new Map(); let obj = {};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

  / 设置
  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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

  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 = (this.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);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

    console.log(map.get(1));/1
    console.log(map);// ``` ![image.png](https://upload-images.jianshu.io/upload_images/13637909-cf03026a6dc1495d.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240) 会发现没有覆盖, 这是因为最后一个没有被遍历 稍微修改一下 ```

  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 = (this.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 特点 有序列表, 包含相互独立且不相等的值

最快的数组去重?

1
2
3
4
5

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;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

      }
    }
    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 = {};

1
2
3
4
5
6
7
8
9
10
11
12

        	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](https://upload-images.jianshu.io/upload_images/13637909-1d1aae3174e792b4.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240) > 可以看到这是可以的,也不知道会存在什么限制 > 但感觉, 可以通过这种方式生成很多维度的坐标 > 也许 有一个限制是, 这个数字本身的大小最好应该比维度数要小? > 否则性能反而降低? 也就是存储的数据数量太少就没有必要?

1
2

            makehash(2);
            makehash(1);

image.png

另一个问题是, 有没有可能完全用 哈希算法生成的 多维度坐标, 唯一确定该值? 换到map 这道题就是, 能不能只通过坐标, 而不用链表进行遍历就可以找到value? 换句话说,一串哈希值是唯一的嘛? 应该不是唯一的, 当然这应该需要数学上的证明啊什么的 ###Hash算法总结 确实不能,假设数据量可以无限增大, 必然会有重复, 也就是’碰撞’ 不过感觉这个哈希算法,很有用啊, 起码以后在数据存储的时候, 可以考虑用这种方法.

CATALOG
    FEATURED TAGS
    html css js
    FRIENDS