- 源码地址请点击此处
集合也是一种常见的数据结构，在 ES6 中已经原生支持了这种数据结构 Set。集合是一种无序、且不能有重复元素的数据结构。
集合有如下常用操作：
- 添加元素
- 移除元素
- 判断元素是否存在
- 清空集合
- 获取集合的长度
- 获取集合的并集、交集、差集
集合的代码实现
下面是集合的代码实现，首先进行接口定义 IMySet：
interface IMySet<T>{
// 向集合中添加元素
add(ele:T):void;
// 从集合中移除元素
remove(ele:T):T;
// 判断集合中是否拥有某个元素
has(ele:T):boolean;
// 清空集合
clear():void;
// 获取集合的长度
size():number;
// 获取集合中的元素
toString():T[];
// 获取并集
getUnionSet(newSet:IMySet<T>):IMySet<T>;
// 获取交集
getIntersectionSet(newSet:IMySet<T>):IMySet<T>;
// 获取差集
getDifferenceSet(newSet:IMySet<T>):IMySet<T>;
// 判断是否是子集
isSubset(parSet:IMySet<T>):boolean;
}
下面实现 MySet 类：
class MySet<T> implements IMySet<T>{
private dataStore:{
[propName:string]:T
} = {};
private _size:number = 0;
add(ele:T):void{
// 判断该元素是否存在
if(!this.has(ele)){
// 获取字符串的键值
const key:string = ele.toString();
this.dataStore[key] = ele;
this._size++;
}
}
remove(ele:T):T{
// 获取字符串的键值
const key:string = ele.toString();
// 获取元素
const val:T = this.dataStore[key];
// 删除 dataStore 上的键
delete this.dataStore[key]
this._size--;
return val;
}
has(ele:T):boolean{
const key:string = ele.toString();
// 通过 hasOwnProperty 方法判断集合中是否存在某个值
return this.dataStore.hasOwnProperty(key);
}
size():number{
return this._size;
}
clear():void{
// 情况集合
this.dataStore = {};
}
toString():T[]{
// 遍历 dataStore 中的所有键值
const res:T[] = Object.keys(this.dataStore).map(v => this.dataStore[v]);
return res;
}
// 获取并集
getUnionSet(newSet:IMySet<T>):IMySet<T>{
const
// 新建空集合
tmp:IMySet<T> = new MySet<T>(),
// 获取新集合中的所有值
newSetVals:T[] = newSet.toString(),
// 获取当前集合中的所有值
currentSetVals:T[] = this.toString();
// 遍历新集合
newSetVals.forEach(v => {
tmp.add(v);
})
// 遍历当前集合
currentSetVals.forEach(v => {
tmp.add(v);
})
return tmp;
}
// 获取交集
getIntersectionSet(newSet:IMySet<T>):IMySet<T>{
const
// 新建空集合
tmp:IMySet<T> = new MySet<T>(),
// 获取新集合中的所有值
newSetVals:T[] = newSet.toString();
newSetVals.forEach(v => {
if(this.has(v)){
tmp.add(v);
}
})
return tmp;
}
// 获取差集
getDifferenceSet(newSet:IMySet<T>):IMySet<T>{
const
// 新建空集合
tmp:IMySet<T> = new MySet<T>(),
// 获取新集合中的所有值
newSetVals:T[] = newSet.toString();
newSetVals.forEach(v => {
if(!this.has(v)){
tmp.add(v);
}
})
return tmp;
}
// 判断是否是子集
isSubset(parSet:IMySet<T>):boolean{
const
// 获取父集合的所有元素
parSetVals:T[] = parSet.toString(),
// 获取当前集合的所有元素
currentSetVals:T[] = this.toString();
let res:boolean = false;
if(parSet.size() >= this.size()){
// 判断当前集合中的元素是否都存在于父集合中
res = currentSetVals.every(v => parSet.has(v))
}
return res;
}
}
集合实现原理浅析
在 ES6 的 Set 出现以前，主要借助 JavaScript 中的对象实现。集合的实现原理：当向集合中添加元素时（调用 add() 方法），在对象中创建一个和新增元素对应的键，值就是新增的元素。
使用对象模拟的集合大概是这样：
{
"A":"A",
"B":"B",
"C":"C",
...
}
由于 JavaScript 对象的限制只能使用字符串或者数字作为键，在向集合中添加复杂的数据结构时，需要将这些数据结构转换为字符串添加到对象中。因此下面的代码，只有第一个 add() 方法调用生效：
const set = new MySet<{name:string}>();
set.add({name:"MIKE"})
set.add({name:"JERRY"})
set.add({name:"PENNY"})
上面的调用结果中，集合中只有一个元素：{name:"MIKE"}，且集合的键为：[object Object]。
为了解决这个问题，可以在添加元素时使用差异化的键，这就要求对不同的元素求一个独特的特征值，这有点像散列的做法，当然这是我个人的想法，对于集合肯定还有其他的实现，如果您有其他的方案，可以在评论区留言。
完。
