ES6 的 Map 的键可以是任意的数据结构, 并且不重复.
那么 map 的底层原理是啥呢?
Map 利用链表, hash 的思想来实现.
首先, Map 可以实现删除, 而且删除的数据可以是中间的值. 而链表的优势就是在中间的任意位置添加, 删除元素都非常快, 不需要移动其他元素, 直接改变指针的指向就可以.
.
而在存储数据很多的情况下, 会导致链条过长, 导致查找效率慢, 所以我们可以创建一个桶 (存储对象的容器), 根据 hash(把散列的值通过算法变成固定的某值) 来平局分配数据, 防止链条过长.
如下图: 桶里面有 3 个位置, 每一个位置都是一个对象, 通过 next 属性指向下一个对象来把没有关联的对象联到一起.
把 Map 属性值和属性名都存到对象的值里.
简单模拟 Map, 代码如下:
- function Mymap() { // 构造函数
- this.init();
- }
- // 初始化函数, 创建桶(数组), 每个位置都是一个对象, 每个对象的属性上设置 next 属性, 并且初始化为 null.
- Mymap.prototype.init = function () {
- this.tong = new Array(8);
- for (var i = 0; i < 8; i++) {
- this.tong[i] = new Object();
- this.tong[i].next = null;
- }
- };
- // 添加数据.
- Mymap.prototype.set = function (key, value) {
- var index = this.hash(key); // 获取到当前设置的 key 设置到那个位置上
- var TempBucket = this.tong[index]; // 获取当前位置的对象
- while (TempBucket.next) { // 遍历如果当前对象链接的下一个不为空
- if (TempBucket.next.key == key) { // 如果要设置的属性已经存在, 覆盖其值.
- TempBucket.next.value = value;
- return; //return , 不在继续遍历
- } else {
- TempBucket = TempBucket.next; // 把指针指向下一个对象.
- }
- }
- TempBucket.next = { // 对象的 next 是 null , 添加对象.
- key: key,
- value: value,
- next: null
- }
- };
- // 查询数据
- Mymap.prototype.get = function (key) {
- var index = this.hash(key);
- var TempBucket = this.tong[index];
- while(TempBucket){
- if(TempBucket.key == key){
- return TempBucket.value;
- }else{
- TempBucket = TempBucket.next;
- }
- }
- return undefined;
- }
- // 删除数据
- Mymap.prototype.delete = function(key){
- var index = this.hash(key);
- var TempBucket = this.tong[index];
- while(TempBucket){
- if(TempBucket.next.key == key){
- TempBucket.next = TempBucket.next.next;
- return true;
- }else{
- TempBucket = TempBucket.next;
- }
- }
- }
- // 看当前属性是否存在
- Mymap.prototype.has = function(key){
- var index = this.hash(key);
- var TempBucket = this.tong[index];
- while(TempBucket){
- if(TempBucket.key == key){
- return true;
- }else{
- TempBucket = TempBucket.next;
- }
- }
- return false;
- }
- // 清空这个 map
- Mymap.prototype.clear = function(){
- this.init();
- }
- // 使设置的属性平均分配到每个位置上, 使得不会某个链条过长.
- Mymap.prototype.hash = function (key) {
- var index = 0;
- if (typeof key == "string") {
- for (var i = 0; i < 3; i++) {
- index = index + isNaN(key.charCodeAt(i)) ? 0 : key.charCodeAt(i);
- }
- }
- else if (typeof key == 'object') {
- index = 0;
- }
- else if (typeof key == 'number') {
- index = isNaN(key) ? 7 : key;
- } else {
- index = 1;
- }
- return index % 8;
- }
- var map = new Mymap(); // 使用构造函数的方式实例化 map
- map.set('name','zwq');
- map.get('name');
- map.has('name);
来源: https://www.cnblogs.com/jiaobaba/p/11918975.html