Java中集合框架
集合（Set）是由一组无序且唯一（即不能重复）的项组成的数据结构，它使用了与有限集合相同的数学概念。可将它想象成是一个即没有重复元素，也没有排序顺序概念的数组。
- 集合是一种包含不同元素的数据结构
- 集合中的元素称为成员
- 集合中的成员是无序的
- 集合不允许相同成员存在
集合的相关概念
集合的数学概念
- 空集，表示不包含任何元素的集合。如24和29之间的素数集合。
{}
- 一个由大于或等于0的整数组成的自然数集合
N = {0, 1, 2, 3, 4, 5, 6...}
集合的相关概念
- 不包含任何成员的集合称为空集，全集则是包含一切可能成员的集合。
- 若两个集合的成员完全相同则成两个集合相等
- 若一个集合中所有成员都属于另一个集合，则前一个集合称为后一集合的子集。
小结：集合是由一组无序但彼此之间又有一定相关性的成员构成的，每个成员在集合中只能出现一次。
- 集合中的成员的顺序是任意的或其他任意形式的组合
- 集合必须保证每个成员只能出现一次
集合的基本操作
集合操作
对集合的基本操作分为
- 交集（intersect）：两个集合中共同存在的成员组成一个新集合
- 并集（union）：将两个集合中的成员进行合并后得到一个新集合
- 补集/差集（subtract）：属于一个集合而不属于另一个集合的成员组成的集合
- 子集（subset）：验证一个给定集合是否是另一个集合的子集
集合的实现
目前的JS实现已经是基于2011年6月发布的ECMAScript5.1（现代浏览器均已支持），包括了Array类的实现。ECMAScript6（ECMAScript2015，2015年6月发布）包括了Set类的实现。
基于数组实现Set类
/*基于数组实现的集合类*/
function Set(){
this.data = [];//存放数据
/*集合的增删改查*/
this.add = add;
this.remove = remove;
this.show = show;
this.size = size;
/*集合的专属操作*/
this.contains = contains;
this.union = union;
this.intersect = intersect;
this.subset = subset;
this.difference = difference;
}
/**将数据存储到集合：集合中不能包含相同元素*/
function add(element){
//检查新加入的元素在数组中是否存在
var pos = this.data.indexOf(element);
if(pos < 0){
//将新增元素追加到数组末尾
this.data.push(element);
return true;
}else{
return false;
}
}
/*从集合中删除指定数据*/
function remove(element){
//检查待删除元素是否存在数组中
var pos = this.data.indexOf(element);
if(pos > -1){
//删除数组元素
this.data.splice(pos, 1);
return true;
}else{
return false;
}
}
/*显示集合成员*/
function show(){
return this.data;
}
/*显示集合成员个数*/
function size(){
return this.data.length;
}
/*检查一个成员是否属于该集合*/
function contains(element){
var pos = this.data.indexOf(element);
return pos > -1;
}
/*并集操作：将两个集合合并成一个*/
function union(set){
//将第一个集合的成员悉数加入到一个临时集合中
var tmpset = new Set();
for(var i=0; i<this.data.length; ++i){
tmpset.add(this.data[i]);
}
//检查第二个集合中的成员是否同时属于第一个集合，若属于则跳过否则加入临时集合
for(var i=0; i<set.data.length; ++i){
if(!tmpset.contains(set.data[i])){
tmpset.add(set.data[i]);
}
}
//返回临时集合
return tmpset;
}
/*求两个集合的交集*/
function intersect(set){
var tmpset = new Set();
for(var i=0; i<this.data.length; ++i){
if(set.contains(this.data[i])){
tmpset.add(this.data[i]);
}
}
return tmpset;
}
/*是否子集*/
function subset(set){
//确定该集合的长度是否小于待比较集合
if(this.size() > set.size()){
return false;
}else{
//判断该集合内的成员是否都属于待比较集合
for each(var member in this.data){
if(!set.contains(member)){
return false;
}
}
}
return true;
}
/*集合补集：属于第一个集合但不属于第二个集合的成员*/
function difference(set){
var tmpset = new Set();
for(var i=0; i<this.size(); ++i){
if(!set.contains(this.data[i])){
tmpset.add(this.data[i]);
}
}
return tmpset;
}
/*test*/
var it = new Set();
it.add('jennifer');
it.add('john');
it.add('clayton');
it.add('alice');
var cis = new Set();
cis.add('alice');
cis.add('bryan');
cis.add('clayton');
cis.add('danny');
var union = new Set();
union = it.union(cis);
print(union.show());//jennifer,john,clayton,alice,bryan,danny
var inter = it.intersect(cis);
print(inter.show());//clayton,alice
print(it.subset(union));//true
var diff = new Set();
diff = it.difference(cis);
print(diff.show());//jennifer,john
基于数组实现集合操作
/*集合交集*/
Array.intersection = function(){
var arr = [], obj = {};
for(var i=0; i<arguments.length; i++){
for(var j=0; j<arguments[i].length; j++){
var ele = arguments[i][j];
if(!obj[ele]){
obj[ele] = 1;
}else{
obj[ele]++;
if(obj[ele] == arguments.length){
arr.push(ele);
}
}
}
}
return arr;
};
/*数组并集*/
Array.union = function(){
var arr=[], obj={};
for(var i=0; i<arguments.length; i++){
for(var j=0; j<arguments[i].length; j++){
var ele = arguments[i][j];
if(!obj[ele]){
obj[ele] = 1;
arr.push(ele);
}
}
}
return arr;
};
/*集合去重*/
Array.prototype.unique = function(){
var arr = [], obj = {};
for(var i=0,j=this.length; i<j; i++){
if(!obj[this[i]]){
obj[this[i]] = 1;
arr.push(this[i]);
}
}
return arr;
}
/*集合差集*/
Array.prototype.subtract = function(ary){
var arr = [], obj = {};
for (var i = 0; i < ary.length; i++) {
obj[ary[i]] = 1;
}
for (var j = 0; j < this.length; j++) {
if (!obj[this[j]]){
obj[this[j]] = 1;
arr.push(this[j]);
}
}
return arr;
}
/*test*/
//print(Array.intersection([1,2,3],[1,2,4]));//1,2
// print([1,2,3,4,1,2,3].unique());//1,2,3,4
// print(Array.union([1,2],[2,3],[3,4]));//1,2,3,4
// print([1,2,3,4,5,6].subtract([1,3,9,8]));//2,4,5,6
基于对象实现Set类
使用对象而非数组来表示集合（items），JS的对象不允许一个键指向两个不同的属性，保证了集合中的元素都是唯一的。
集合类的抽象数据类型
-
add(value)向集合中添加一个新项 -
remove(value)从集合中移除一个值 -
has(value)判断值是否存在集合中，存在返回true，不存在返回false。 -
clear()移除集合中所有项 -
size()获取集合中所包含元素的数量 -
values()获取包含集合汇总所有值的数组
function Set(){
var items = {};
/*判断值是否存在集合中*/
this.has = function(value){
//return value in items;
//所有JS对象均有hasOwnProperty方法，它返回一个表明对象是否具有特定属性的布尔值。
return items.hasOwnProperty(value);
};
/*向集合中添加新值*/
this.add = function(value){
if(!this.has(value)){
//添加新值时将其同时作为键和值保存有利于查找
items[value] = value;//将新值添加到集合中
return true;
}
return false;
};
/*从集合中移除某值*/
this.remove = function(value){
if(this.has(value)){
delete items[value];//从对象中移除属性
return true;
}
return false;
};
/*从集合中移除所有值*/
this.clear = function(){
items = {};//使用空对象赋值即可
};
/*获取集合所包含元素的个数*/
this.size = function(){
//return Object.keys(items).length;//IE9+、FF4、Chrome5+、Opera12+、Sarafi5+
var count = 0;
for(var prop in items){
//检查是否为对象自身属性，因为对象的原型会包含了额外的属性，以避免重复计数。
if(items.hasOwnProperty(prop)){
++count;
}
}
return count;
};
/*获取包含集合所有值的数组*/
this.values = function(){
// return Object.keys(items);//IE9+、FF4、Chrome5+、Opera12+、Sarafi5+
var keys = [];
for(var key in items){
keys.push(key);
}
return keys;
};
/*交集：元素同时存在两个不同的集合中*/
this.intersection = function(set){
var tmpset = new Set();
var values = this.values();
for(var i=0; i<values.length; i++){
if(set.has(values[i])){
tmpset.add(values[i]);
}
}
return tmpset;
};
/*并集*/
this.union = function(set){
var tmpset = new Set();
var values = this.values();
for(var i=0; i<values.length; i++){
tmpset.add(values[i]);
}
values = set.values();
for(var i=0; i<values.length; i++){
tmpset.add(values[i]);
}
return tmpset;
};
/*差集*/
this.difference = function(set){
var tmpset = new Set();
var values = this.values();
for(var i=0; i<values.length; i++){
if(!set.has(values[i])){
tmpset.add(values[i]);
}
}
return tmpset;
};
/*子集*/
this.subset = function(set){
if(this.size() > set.size()){
return false;
}else{
var values = this.values();
for(var i=0; i<values.length; i++){
if(!set.has(values[i])){
return false;
}
}
return true;
}
};
}
/*test*/
var set = new Set();
set.add(1);
print(set.values(), set.has(1), set.size());//1 true 1
set.remove(1);
print(set.values(), set.has(1), set.size());// false 0
集合操作
/*test*/
var setA = new Set();
setA.add(1);
setA.add(2);
setA.add(3);
var setB = new Set();
setB.add(1);
setB.add(2);
setB.add(4);
var inter = setA.intersection(setB);
var union = setA.union(setB);
var diff = setA.difference(setB);
var subset = setA.subset(setB);
print(inter.values());//1,2
print(union.values());//1,2,3,4
print(diff.values());//3
print(subset);//false
