前言
映射是高层的数据结构，高层的数据结构还有栈和队列，这种数据结构更像是定义好了这种数据结构的相应的使用接口。
有了这些使用的接口包括这些数据结构本身所维持的一些性质，就可以非常容易的把它们放入一些具体的应用中，但是底层实现可以是多种多样的。
比如栈和队列的底层实现即可以是动态数组也可以是链表，映射 Map 也是类似这样的数据结构。
还是那句老话：光看文章能够掌握两成，动手敲代码、动脑思考、画图才可以掌握八成。源码仓库
不要完美主义。掌握好“度”。
太过于追求完美会把自己逼的太紧，会产生各种焦虑的心态，最后甚至会怀疑自己，温故而知新，不要停止不前，掌握好这个度，不存在你把那些你认为完全掌握了，然后就成了某一个领域的专家，相反一旦你产生很浓厚的厌恶感，那么就意味着你即将会放弃或者已经选择了放弃，虽然你之前想把它做到 100 分，但是由于你的放弃让它变为 0 分。
学习本着自己的目标去。不要在学的过程中偏离了自己的目标。要分清主次。
难的东西，你可以慢慢的回头看一看。那样才会更加的柳暗花明，更能提升自己的收获。
映射(Map)
高中数学里的函数就可以理解成是一种映射。如 f(x)=2*x+1，在映域中每取出一个值，相应的在值域中都有有一个值与它对应，如 x 为 1，f(x)就为 3，x 为 2，f(x)就为 5，从一个值向另外一个值的对应关系其实就是映射。
映射关系你也可以把它称之为字典。如 单词 -----> 释意，字典就是这样一个从单词对应到释意这种数据的一个集合，字典的英文是 dictionary。在很多语言中把映射这样的一种数据结构称之为 dictionary 的简写 dict，最典型的就是 python 里面基础数据结构 dict，但是在 java、c++、js 语言中把这种关系称之为 Map，其实它描述的就是类似字典这样的数据结构。
生活中的映射的应用
dict：key ----> value 字典：单词 ----> 释意 名册：身份证号 ----> 人 车辆管理：车牌号 ----> 车 数据库：id ----> 信息 词频统计：单词 ----> 频率
存储（键，值）数据对的数据结构（key，value）, 数据是一对一对出现的，这样的数据结构就叫映射， 很多时候都是要根据键（Key）来寻找值（Value）， 例如生活中的映射的应用例子。
可以非常容易的使用链表或者二分搜索树来实现映射。
// 链表实现时的Node
class Node {
key; // Key
value; //Value
Node next;// Node
}
// 二分搜索树实现时的Node
class Node {
key; // Key
value; //Value
left;// Node
right;// Node
}映射接口
MyMap
void add(k, v) V remove(k) boolean contains(k) V get(k) void set(k, v) int getSize() boolean isEmpty()
通过链表来实现映射 Map
代码示例
(class: MyLinkedListMap)
MyLinkedListMap
// 自定义链表映射节点 LinkedListMapNode
class MyLinkedListMapNode {
constructor(key = null, value = null, next = null) {
this.key = key;
this.value = value;
this.next = next;
}
// @Override toString 2018-11-5-jwl
toString() {
return this.key.toString() + '---------->' + this.value.toString();
}
}
// 自定义链表映射 Map
class MyLinkedListMap {
constructor() {
this.dummyHead = new MyLinkedListMapNode();
this.size = 0;
}
// 根据key获取节点 -
getNode(key) {
let cur = this.dummyHead.next;
while (cur !== null) {
if (cur.key === key) return cur;
cur = cur.next;
}
return null;
}
// 添加操作 +
add(key, value) {
let node = this.getNode(key);
// 这个节点如果存在就 覆盖值即可
if (node !== null) node.value = value;
else {
// 如果不存在，那么就在头部添加以下
let newNode = new MyLinkedListMapNode(key, value);
newNode.next = this.dummyHead.next;
this.dummyHead.next = newNode;
this.size++;
}
}
// 删除操作 返回被删除的元素 +
remove(key) {
let prev = this.dummyHead;
// 循环查找
while (prev.next !== null) {
if (prev.next.key === key) break;
prev = prev.next;
}
// 如果触碰了break， 那就满足条件
if (prev.next !== null) {
let delNode = prev.next;
prev.next = delNode.next;
let value = delNode.value;
devNode = delNode.next = null;
this.size--;
return value;
}
// 如果没有触屏break 那就返回空值回去
return null;
}
// 查询操作 返回查询到的元素 +
get(key) {
let node = this.getNode(key);
if (node === null) return null;
return node.value;
}
// 修改操作 +
set(key, value) {
let node = this.getNode(key);
if (node === null) throw new Error(key + " doesn't exist.");
node.value = value;
}
// 返回是否包含该key的元素的判断值 +
contains(key) {
return this.getNode(key) !== null;
}
// 返回映射中实际的元素个数 +
getSize() {
return this.size;
}
// 返回映射中是否为空的判断值 +
isEmpty() {
return this.size === 0;
}
// @Override toString() 2018-11-05-jwl
toString() {
let mapInfo = `MyLinkedListMap: size = ${this.size}, data = [ `;
document.body.innerHTML += `MyLinkedListMap: size = ${
this.size
}, data = [ <br/><br/>`;
let cur = this.dummyHead.next;
for (var i = 0; i < this.size - 1; i++) {
mapInfo += ` ${cur.toString()}, \r\n`;
document.body.innerHTML += ` ${cur.toString()}, <br/><br/>`;
cur = cur.next;
}
if (cur !== null) {
mapInfo += ` ${cur.toString()} \r\n`;
document.body.innerHTML += ` ${cur.toString()} <br/><br/>`;
}
mapInfo += ` ] \r\n`;
document.body.innerHTML += ` ] <br/><br/>`;
return mapInfo;
}
}通过二分搜索树来实现映射 Map
代码示例
(class: MyBSTMap)
MyBSTMap
// 自定义二分搜索树树映射节点 TreeMapNode
class MyBinarySearchTreeMapNode {
constructor(key = null, value = null, left = null, right = null) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
// @Override toString 2018-11-5-jwl
toString() {
return this.key.toString() + '---------->' + this.value.toString();
}
}
// 自定义二分搜索树映射 Map
class MyBinarySearchTreeMap {
constructor() {
this.root = null;
this.size = 0;
}
// 比较的功能
compare(keyA, keyB) {
if (keyA === null || keyB === null)
throw new Error("key is error. key can't compare.");
if (keyA > keyB) return 1;
else if (keyA < keyB) return -1;
else return 0;
}
// 根据key获取节点 -
getNode(node, key) {
// 先解决最基本的问题
if (node === null) return null;
// 开始将复杂的问题 逐渐缩小规模
// 从而求出小问题的解，最后构建出原问题的解
switch (this.compare(node.key, key)) {
case 1: // 向左找
return this.getNode(node.left, key);
break;
case -1: // 向右找
return this.getNode(node.right, key);
break;
case 0: // 找到了
return node;
break;
default:
throw new Error(
'compare result is error. compare result : 0、 1、 -1 .'
);
break;
}
}
// 添加操作 +
add(key, value) {
this.root = this.recursiveAdd(this.root, key, value);
}
// 添加操作 递归算法 -
recursiveAdd(node, key, value) {
// 解决最简单的问题
if (node === null) {
this.size++;
return new MyBinarySearchTreeMapNode(key, value);
}
// 将复杂的问题规模逐渐变小，
// 从而求出小问题的解，从而构建出原问题的答案
if (this.compare(node.key, key) > 0)
node.left = this.recursiveAdd(node.left, key, value);
else if (this.compare(node.key, key) < 0)
node.right = this.recursiveAdd(node.right, key, value);
else node.value = value;
return node;
}
// 删除操作 返回被删除的元素 +
remove(key) {
let node = this.getNode(this.root, key);
if (node === null) return null;
this.root = this.recursiveRemove(this.root, key);
return node.value;
}
// 删除操作 递归算法 +
recursiveRemove(node, key) {
// 解决最基本的问题
if (node === null) return null;
if (this.compare(node.key, key) > 0) {
node.left = this.recursiveRemove(node.left, key);
return node;
} else if (this.compare(node.key, key) < 0) {
node.right = this.recursiveRemove(node.right, key);
return node;
} else {
// 当前节点的key 与 待删除的key的那个节点相同
// 有三种情况
// 1. 当前节点没有左子树，那么只有让当前节点的右子树直接覆盖当前节点，就表示当前节点被删除了
// 2. 当前节点没有右子树，那么只有让当前节点的左子树直接覆盖当前节点，就表示当前节点被删除了
// 3. 当前节点左右子树都有， 那么又分两种情况，使用前驱删除法或者后继删除法
// 1. 前驱删除法：使用当前节点的左子树上最大的那个节点覆盖当前节点
// 2. 后继删除法：使用当前节点的右子树上最小的那个节点覆盖当前节点
if (node.left === null) {
let rightNode = node.right;
node.right = null;
this.size--;
return rightNode;
} else if (node.right === null) {
let leftNode = node.left;
node.left = null;
this.size--;
return leftNode;
} else {
let predecessor = this.maximum(node.left);
node.left = this.removeMax(node.left);
this.size++;
// 开始嫁接 当前节点的左右子树
predecessor.left = node.left;
predecessor.right = node.right;
// 将当前节点从根节点剔除
node = node.left = node.right = null;
this.size--;
// 返回嫁接后的新节点
return predecessor;
}
}
}
// 删除操作的两个辅助函数
// 获取最大值、删除最大值
// 以前驱的方式 来辅助删除操作的函数
// 获取最大值
maximum(node) {
// 再也不能往右了，说明当前节点已经是最大的了
if (node.right === null) return node;
// 将复杂的问题渐渐减小规模，从而求出小问题的解，最后用小问题的解构建出原问题的答案
return this.maximum(node.right);
}
// 删除最大值
removeMax(node) {
// 解决最基本的问题
if (node.right === null) {
let leftNode = node.left;
node.left = null;
this.size--;
return leftNode;
}
// 开始化归
node.right = this.removeMax(node.right);
return node;
}
// 查询操作 返回查询到的元素 +
get(key) {
let node = this.getNode(this.root, key);
if (node === null) return null;
return node.value;
}
// 修改操作 +
set(key, value) {
let node = this.getNode(this.root, key);
if (node === null) throw new Error(key + " doesn't exist.");
node.value = value;
}
// 返回是否包含该key的元素的判断值 +
contains(key) {
return this.getNode(this.root, key) !== null;
}
// 返回映射中实际的元素个数 +
getSize() {
return this.size;
}
// 返回映射中是否为空的判断值 +
isEmpty() {
return this.size === 0;
}
// @Override toString() 2018-11-05-jwl
toString() {
let mapInfo = `MyBinarySearchTreeMap: size = ${this.size}, data = [ `;
document.body.innerHTML += `MyBinarySearchTreeMap: size = ${
this.size
}, data = [ <br/><br/>`;
// 以非递归的前序遍历 输出字符串
let stack = new MyLinkedListStack();
stack.push(this.root);
if (this.root === null) stack.pop();
while (!stack.isEmpty()) {
let node = stack.pop();
if (node.left !== null) stack.push(node.left);
if (node.right !== null) stack.push(node.right);
if (node.left === null && node.right === null) {
mapInfo += ` ${node.toString()} \r\n`;
document.body.innerHTML += ` ${node.toString()} <br/><br/>`;
} else {
mapInfo += ` ${node.toString()}, \r\n`;
document.body.innerHTML += ` ${node.toString()}, <br/><br/>`;
}
}
mapInfo += ` ] \r\n`;
document.body.innerHTML += ` ] <br/><br/>`;
return mapInfo;
}
}两种映射 Map 的时间复杂度分析
MyLinkedListMap
MyLinkedListMap O(n)
增加 add O(n)：为了防止指定 key 的节点不存在，所以必须先查询一遍，然后再决定是直接赋值还是创建新节点，虽然添加的复杂度为O(1)，但是查询的操作是遍历整个链表，所以整体时间复杂度为O(n)。
查询 contains、get O(n)：查询的操作是遍历整个链表，所以时间复杂度为O(n)
修改 set O(n)：为了防止指定 key 的节点不存在，所以必须先查询一遍，所以时间复杂度为O(n)
删除 remove O(n)：删操作也需要遍历整个链表，所以时间复杂度为O(n)
MyBSTMap
MyBSTMap O(h) or O(log n)
增加 add O(h) or O(log n)：添加一个元素(key/value)，待添加的这个元素 key 和根节点的这个元素 key 进行比较，如果小于的话直接去左子树，如果大于的话直接去右子树，每一次近乎都能把一半儿的元素(key/value)给扔掉。
添加这个元素这个过程其实就像是在走一个链表，一层一层的从这个树的根节点向叶子节点出发，最终一共经历的节点个数就是这棵树的高度，也就是整棵树最大的深度，查询元素也是如此，删除元素还是如此。
所以对于二分搜索树来说，这三个时间复杂度都是O(h)这个级别的，这个 h 就是二分搜索树的高度。
查询 contains、get O(h) or O(log n)
修改 set O(h) or O(log n)
删除 remove O(h) or O(log n)
代码示例
class: MyLinkedListMap, class: MyBSTMap , class: PerformanceTest, class: Main)
MyLinkedListMap
// 自定义链表映射节点 LinkedListMapNode
class MyLinkedListMapNode {
constructor(key = null, value = null, next = null) {
this.key = key;
this.value = value;
this.next = next;
}
// @Override toString 2018-11-5-jwl
toString() {
return this.key.toString() + '---------->' + this.value.toString();
}
}
// 自定义链表映射 Map
class MyLinkedListMap {
constructor() {
this.dummyHead = new MyLinkedListMapNode();
this.size = 0;
}
// 根据key获取节点 -
getNode(key) {
let cur = this.dummyHead.next;
while (cur !== null) {
if (cur.key === key) return cur;
cur = cur.next;
}
return null;
}
// 添加操作 +
add(key, value) {
let node = this.getNode(key);
// 这个节点如果存在就 覆盖值即可
if (node !== null) node.value = value;
else {
// 如果不存在，那么就在头部添加以下
let newNode = new MyLinkedListMapNode(key, value);
newNode.next = this.dummyHead.next;
this.dummyHead.next = newNode;
this.size++;
}
}
// 删除操作 返回被删除的元素 +
remove(key) {
let prev = this.dummyHead;
// 循环查找
while (prev.next !== null) {
if (prev.next.key === key) break;
prev = prev.next;
}
// 如果触碰了break， 那就满足条件
if (prev.next !== null) {
let delNode = prev.next;
prev.next = delNode.next;
let value = delNode.value;
delNode = delNode.next = null;
this.size--;
return value;
}
// 如果没有触屏break 那就返回空值回去
return null;
}
// 查询操作 返回查询到的元素 +
get(key) {
let node = this.getNode(key);
if (node === null) return null;
return node.value;
}
// 修改操作 +
set(key, value) {
let node = this.getNode(key);
if (node === null) throw new Error(key + " doesn't exist.");
node.value = value;
}
// 返回是否包含该key的元素的判断值 +
contains(key) {
return this.getNode(key) !== null;
}
// 返回映射中实际的元素个数 +
getSize() {
return this.size;
}
// 返回映射中是否为空的判断值 +
isEmpty() {
return this.size === 0;
}
// @Override toString() 2018-11-05-jwl
toString() {
let mapInfo = `MyLinkedListMap: size = ${this.size}, data = [ `;
document.body.innerHTML += `MyLinkedListMap: size = ${
this.size
}, data = [ <br/><br/>`;
let cur = this.dummyHead.next;
for (var i = 0; i < this.size - 1; i++) {
mapInfo += ` ${cur.toString()}, \r\n`;
document.body.innerHTML += ` ${cur.toString()}, <br/><br/>`;
cur = cur.next;
}
if (cur !== null) {
mapInfo += ` ${cur.toString()} \r\n`;
document.body.innerHTML += ` ${cur.toString()} <br/><br/>`;
}
mapInfo += ` ] \r\n`;
document.body.innerHTML += ` ] <br/><br/>`;
return mapInfo;
}
}MyBSTMap
// 自定义二分搜索树树映射节点 TreeMapNode
class MyBinarySearchTreeMapNode {
constructor(key = null, value = null, left = null, right = null) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
// @Override toString 2018-11-5-jwl
toString() {
return this.key.toString() + '---------->' + this.value.toString();
}
}
// 自定义二分搜索树映射 Map
class MyBinarySearchTreeMap {
constructor() {
this.root = null;
this.size = 0;
}
// 比较的功能
compare(keyA, keyB) {
if (keyA === null || keyB === null)
throw new Error("key is error. key can't compare.");
if (keyA > keyB) return 1;
else if (keyA < keyB) return -1;
else return 0;
}
// 根据key获取节点 -
getNode(node, key) {
// 先解决最基本的问题
if (node === null) return null;
// 开始将复杂的问题 逐渐缩小规模
// 从而求出小问题的解，最后构建出原问题的解
switch (this.compare(node.key, key)) {
case 1: // 向左找
return this.getNode(node.left, key);
break;
case -1: // 向右找
return this.getNode(node.right, key);
break;
case 0: // 找到了
return node;
break;
default:
throw new Error(
'compare result is error. compare result : 0、 1、 -1 .'
);
break;
}
}
// 添加操作 +
add(key, value) {
this.root = this.recursiveAdd(this.root, key, value);
}
// 添加操作 递归算法 -
recursiveAdd(node, key, value) {
// 解决最简单的问题
if (node === null) {
this.size++;
return new MyBinarySearchTreeMapNode(key, value);
}
// 将复杂的问题规模逐渐变小，
// 从而求出小问题的解，从而构建出原问题的答案
if (this.compare(node.key, key) > 0)
node.left = this.recursiveAdd(node.left, key, value);
else if (this.compare(node.key, key) < 0)
node.right = this.recursiveAdd(node.right, key, value);
else node.value = value;
return node;
}
// 删除操作 返回被删除的元素 +
remove(key) {
let node = this.getNode(this.root, key);
if (node === null) return null;
this.root = this.recursiveRemove(this.root, key);
return node.value;
}
// 删除操作 递归算法 +
recursiveRemove(node, key) {
// 解决最基本的问题
if (node === null) return null;
if (this.compare(node.key, key) > 0) {
node.left = this.recursiveRemove(node.left, key);
return node;
} else if (this.compare(node.key, key) < 0) {
node.right = this.recursiveRemove(node.right, key);
return node;
} else {
// 当前节点的key 与 待删除的key的那个节点相同
// 有三种情况
// 1. 当前节点没有左子树，那么只有让当前节点的右子树直接覆盖当前节点，就表示当前节点被删除了
// 2. 当前节点没有右子树，那么只有让当前节点的左子树直接覆盖当前节点，就表示当前节点被删除了
// 3. 当前节点左右子树都有， 那么又分两种情况，使用前驱删除法或者后继删除法
// 1. 前驱删除法：使用当前节点的左子树上最大的那个节点覆盖当前节点
// 2. 后继删除法：使用当前节点的右子树上最小的那个节点覆盖当前节点
if (node.left === null) {
let rightNode = node.right;
node.right = null;
this.size--;
return rightNode;
} else if (node.right === null) {
let leftNode = node.left;
node.left = null;
this.size--;
return leftNode;
} else {
let predecessor = this.maximum(node.left);
node.left = this.removeMax(node.left);
this.size++;
// 开始嫁接 当前节点的左右子树
predecessor.left = node.left;
predecessor.right = node.right;
// 将当前节点从根节点剔除
node = node.left = node.right = null;
this.size--;
// 返回嫁接后的新节点
return predecessor;
}
}
}
// 删除操作的两个辅助函数
// 获取最大值、删除最大值
// 以前驱的方式 来辅助删除操作的函数
// 获取最大值
maximum(node) {
// 再也不能往右了，说明当前节点已经是最大的了
if (node.right === null) return node;
// 将复杂的问题渐渐减小规模，从而求出小问题的解，最后用小问题的解构建出原问题的答案
return this.maximum(node.right);
}
// 删除最大值
removeMax(node) {
// 解决最基本的问题
if (node.right === null) {
let leftNode = node.left;
node.left = null;
this.size--;
return leftNode;
}
// 开始化归
node.right = this.removeMax(node.right);
return node;
}
// 查询操作 返回查询到的元素 +
get(key) {
let node = this.getNode(this.root, key);
if (node === null) return null;
return node.value;
}
// 修改操作 +
set(key, value) {
let node = this.getNode(this.root, key);
if (node === null) throw new Error(key + " doesn't exist.");
node.value = value;
}
// 返回是否包含该key的元素的判断值 +
contains(key) {
return this.getNode(this.root, key) !== null;
}
// 返回映射中实际的元素个数 +
getSize() {
return this.size;
}
// 返回映射中是否为空的判断值 +
isEmpty() {
return this.size === 0;
}
// @Override toString() 2018-11-05-jwl
toString() {
let mapInfo = `MyBinarySearchTreeMap: size = ${this.size}, data = [ `;
document.body.innerHTML += `MyBinarySearchTreeMap: size = ${
this.size
}, data = [ <br/><br/>`;
// 以非递归的前序遍历 输出字符串
let stack = new MyLinkedListStack();
stack.push(this.root);
if (this.root === null) stack.pop();
while (!stack.isEmpty()) {
let node = stack.pop();
if (node.left !== null) stack.push(node.left);
if (node.right !== null) stack.push(node.right);
if (node.left === null && node.right === null) {
mapInfo += ` ${node.toString()} \r\n`;
document.body.innerHTML += ` ${node.toString()} <br/><br/>`;
} else {
mapInfo += ` ${node.toString()}, \r\n`;
document.body.innerHTML += ` ${node.toString()}, <br/><br/>`;
}
}
mapInfo += ` ] \r\n`;
document.body.innerHTML += ` ] <br/><br/>`;
return mapInfo;
}
}PerformanceTest
// 性能测试
class PerformanceTest {
constructor() {}
// 对比都列
testQueue(queue, openCount) {
let startTime = Date.now();
let random = Math.random;
for (var i = 0; i < openCount; i++) {
queue.enqueue(random() * openCount);
}
while (!queue.isEmpty()) {
queue.dequeue();
}
let endTime = Date.now();
return this.calcTime(endTime - startTime);
}
// 对比栈
testStack(stack, openCount) {
let startTime = Date.now();
let random = Math.random;
for (var i = 0; i < openCount; i++) {
stack.push(random() * openCount);
}
while (!stack.isEmpty()) {
stack.pop();
}
let endTime = Date.now();
return this.calcTime(endTime - startTime);
}
// 对比集合
testSet(set, openCount) {
let startTime = Date.now();
let random = Math.random;
let arr = [];
let temp = null;
// 第一遍测试
for (var i = 0; i < openCount; i++) {
temp = random();
// 添加重复元素，从而测试集合去重的能力
set.add(temp * openCount);
set.add(temp * openCount);
arr.push(temp * openCount);
}
for (var i = 0; i < openCount; i++) {
set.remove(arr[i]);
}
// 第二遍测试
for (var i = 0; i < openCount; i++) {
set.add(arr[i]);
set.add(arr[i]);
}
while (!set.isEmpty()) {
set.remove(arr[set.getSize() - 1]);
}
let endTime = Date.now();
// 求出两次测试的平均时间
let avgTime = Math.ceil((endTime - startTime) / 2);
return this.calcTime(avgTime);
}
// 对比映射
testMap(map, openCount) {
let startTime = Date.now();
let array = new MyArray();
let random = Math.random;
let temp = null;
let result = null;
for (var i = 0; i < openCount; i++) {
temp = random();
result = openCount * temp;
array.add(result);
array.add(result);
array.add(result);
array.add(result);
}
for (var i = 0; i < array.getSize(); i++) {
result = array.get(i);
if (map.contains(result)) map.add(result, map.get(result) + 1);
else map.add(result, 1);
}
for (var i = 0; i < array.getSize(); i++) {
result = array.get(i);
map.remove(result);
}
let endTime = Date.now();
return this.calcTime(endTime - startTime);
}
// 计算运行的时间，转换为 天-小时-分钟-秒-毫秒
calcTime(result) {
//获取距离的天数
var day = Math.floor(result / (24 * 60 * 60 * 1000));
//获取距离的小时数
var hours = Math.floor((result / (60 * 60 * 1000)) % 24);
//获取距离的分钟数
var minutes = Math.floor((result / (60 * 1000)) % 60);
//获取距离的秒数
var seconds = Math.floor((result / 1000) % 60);
//获取距离的毫秒数
var milliSeconds = Math.floor(result % 1000);
// 计算时间
day = day < 10 ? '0' + day : day;
hours = hours < 10 ? '0' + hours : hours;
minutes = minutes < 10 ? '0' + minutes : minutes;
seconds = seconds < 10 ? '0' + seconds : seconds;
milliSeconds =
milliSeconds < 100
? milliSeconds < 10
? '00' + milliSeconds
: '0' + milliSeconds
: milliSeconds;
// 输出耗时字符串
result =
day +
'天' +
hours +
'小时' +
minutes +
'分' +
seconds +
'秒' +
milliSeconds +
'毫秒' +
' <<<<============>>>> 总毫秒数：' +
result;
return result;
}
}Main
// main 函数
class Main {
constructor() {
this.alterLine('Map Comparison Area');
let myLinkedListMap = new MyLinkedListMap();
let myBinarySearchTreeMap = new MyBinarySearchTreeMap();
let systemMap = new Map();
let performanceTest = new PerformanceTest();
systemMap.remove = systemMap.delete;
systemMap.contains = systemMap.has;
systemMap.add = systemMap.set;
systemMap.isEmpty = () => systemMap.size === 0;
systemMap.getSize = () => systemMap.size;
let myLinkedListMapInfo = performanceTest.testMap(
myLinkedListMap,
50000
);
let myBinarySearchTreeMapInfo = performanceTest.testMap(
myBinarySearchTreeMap,
50000
);
let systemMapInfo = performanceTest.testMap(systemMap, 50000);
this.alterLine('MyLinkedListMap Area');
console.log(myLinkedListMapInfo);
this.show(myLinkedListMapInfo);
this.alterLine('MyBinarySearchTreeMap Area');
console.log(myBinarySearchTreeMapInfo);
this.show(myBinarySearchTreeMapInfo);
this.alterLine('SystemMap Area');
console.log(systemMapInfo);
this.show(systemMapInfo);
}
// 将内容显示在页面上
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// 展示分割线
alterLine(title) {
let line = `--------------------${title}----------------------`;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`;
}
}
// 页面加载完毕
window.onload = function() {
// 执行主函数
new Main();
};总结
上一篇文章实现了自己的专属集合Set，这一篇文章实现了自己的专属Map，再来看看它们的关系，之后赶快根据学习到的思想去leetcode中去小试牛刀一下吧。
MySet
void add (e) : 不能添加重复元素 void remove (e) boolean conatains (e) int getSize () boolean isEmpty ()
MyMap
void add(k, v) V remove(k) boolean contains(k) V get(k) void set(k, v) int getSize() boolean isEmpty()
实现这两种数据结构的时候既可以使用链表也可以使用二分搜索树。在实现的过程中，这两种数据结构有很多相同之处，对于映射来说它本身也是一个集合，只不过是一个键 key 这样的集合，而且每一个 key 还带着一个 value 而已。
它的本质和集合并没有太大的区别，只不过最开始实现的二分搜索树只能够存储一个元素，所以在用二分搜索树实现 map 的时候很多方法需要重新写一遍，但是它的实质和集合中的逻辑没有什么大的区别，所以集合和映射之间是存在这样的联系的。
在很多系统类库中完全可以基于集合 set 的实现去实现映射 map。或者基于映射 map 的实现来实现集合 set，其实这个方法非常的简单。
例如你有了一个集合的底层实现，在这种情况下再完成一个映射的只需要重定义集合中的元素是什么，这个时候你只需要定义集合中的元素是键值对(key/value)，并且一定要特别的强调对于这种新的键值的数据对比较的时候，是以键 key 的值来进行比较的而不是去比较 value 的值。
在这样的定义下，对于集合的定义所有操作都会适用于映射，不过对于映射还需要添加新的操作，所以更加常见的的方式是基于映射 map 的底层实现，直接包装出集合 set 来。
当你有了一个映射的底层实现的时候，直接将相应的映射的键值对(key/value)中的 value 赋值为空即可，也就是只使用 key 而不使用 value，只考虑键 key 不考虑值 value，这样一来整个 map 就是一个键 key 的集合。
只考虑键的时候，get 方法和 set 方法就没有意义了，这样就相当于实现了一个映射之后在对这个映射进行包装，就可以包装出集合这个数据结构了。集合映射的核心逻辑其实是一致的。
其实可以直接对链表和二分搜索树直接设置 key 和 value。这种很常见的设计思路，平衡二叉树、红黑树这样的树结构直接带有 key 和 value。
实现了集合Set和映射Map后，可以尝试去leetcode上解决更多集合和映射的问题哟。
解决 leetcode 上的更多集合和映射方面的问题
leetcode 上349.两个数组的交集：https://leetcode-cn.com/problems/intersection-of-two-arrays/。
这个交集不保留重复元素，使用 系统内置 Set 即可。
leetcode 上350.两个数组的交集 II：https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/。
这个交集保留重复元素使用 系统内置 Map 即可。
其实和哈希表相关的大多数问题，可以使用 Set 和 Map 来解决其实系统内置的 Set 和 Map 都是通过哈希表来实现的，再底层才会是红黑树，使用基于哈希表实现的集合或者映射来解决和哈希表相关的大多数问题。
系统内置的 Set 和 Map 是先基于 hash 表的底层实现，然后 hash 表是再基于平衡二叉树的底层实现，set 和 map 的结构是相同的，所以从用户使用的角度来看，可以完全不管它们的底层是怎么回事儿，只需要知道它们可以实现这样的功能就好了。
相应的也应该知道它们背后不同的底层实现的时间复杂度是怎样的，在多大数情况下使用平衡二叉树实现的 Set 和 Map，在时间上是完全没有问题的，logn 这个复杂度也是非常非常快的。
可以尝试去使用 Set 和 Map 去实现 leetcode 上的哈希表标签的问题，https://leetcode-cn.com/tag/hash-table/。
解题：leetcode 上349.两个数组的交集 和 leetcode 上350.两个数组的交集 II
// 答题
class Solution {
// leetcode 349. 两个数组的交集
intersection(nums1, nums2) {
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var intersection = function(nums1, nums2) {
let set = new Set();
let arr = [];
for (const num of nums1) set.add(num);
for (const num of nums2) {
if (set.has(num)) {
arr.push(num);
set.delete(num);
}
}
return arr;
};
return intersection(nums1, nums2);
}
// leetcode 350.两个数组的交集 II
intersect(nums1, nums2) {
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var intersect = function(nums1, nums2) {
let map = new Map();
let arr = [];
for (const num of nums1) {
if (map.has(num)) map.set(num, map.get(num) + 1);
else map.set(num, 1);
}
for (const num of nums2) {
if (map.has(num)) {
arr.push(num);
let result = map.get(num) - 1;
map.set(num, result);
if (result === 0) map.delete(num);
}
}
return arr;
};
return intersect(nums1, nums2);
}
}
// main 函数
class Main {
constructor() {
this.alterLine('leetcode 349. 两个数组的交集');
let s = new Solution();
var nums1 = [1, 2, 2, 1],
nums2 = [2, 2];
var nums3 = [4, 9, 5],
nums4 = [9, 4, 9, 8, 4];
console.log('[' + s.intersection(nums1, nums2) + ']');
console.log('[' + s.intersection(nums3, nums4) + ']');
this.show('[' + s.intersection(nums1, nums2) + ']');
this.show('[' + s.intersection(nums3, nums4) + ']');
this.alterLine('leetcode 350. 两个数组的交集 II');
console.log('[' + s.intersect(nums1, nums2) + ']');
console.log('[' + s.intersect(nums3, nums4) + ']');
this.show('[' + s.intersect(nums1, nums2) + ']');
this.show('[' + s.intersect(nums3, nums4) + ']');
}
// 将内容显示在页面上
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// 展示分割线
alterLine(title) {
let line = `--------------------${title}----------------------`;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`;
}
}
// 页面加载完毕
window.onload = function() {
// 执行主函数
new Main();
};拓展
有序映射和无序映射
有序映射是指在 map 中的键是具有顺序性的。映射中这些 key 就充当了集合中相应的元素 e，只不过在映射中每一个 key 都有一个 value 的值而已，有序映射通常都是基于搜索树来实现的，因为搜索树具有这样额外的能力，可以维持数据的有序性。
无序映射是指在 map 中键不具有顺序性的。链表实现的映射也是无序映射，而且它非常的慢，无序映射通常基于哈希表来实现的。
多重映射
多重映射中的键可以重复，普通映射的键是不能够重复的。但是在极个别的情况下，有些应用场景可能希望映射 map 中可以存储具有重复键的相应的数据对，在这种情况下就需要使用多重映射了。
