如何从两个List中筛选出相同的值

问题

现有社保卡和身份证若干,想要匹配筛选出一一对应的社保卡和身份证。
转换为List<社保卡> socialList,和List idList,从二者中找出匹配的社保卡。

模型

创建社保卡类

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
/**
* @author Ryan Miao
*/
class SocialSecurity{
private Integer id;//社保号码
private Integer idCard;//身份证号码
private String somethingElse;

public SocialSecurity(Integer id, Integer idCard, String somethingElse) {
this.id = id;
this.idCard = idCard;
this.somethingElse = somethingElse;
}

public Integer getId() {
return id;
}

public Integer getIdCard() {
return idCard;
}

public String getSomethingElse() {
return somethingElse;
}

@Override
public String toString() {
return "SocialSecurity{" +
"id=" + id +
", idCard=" + idCard +
", somethingElse='" + somethingElse + '\'' +
'}';
}
}

创建身份证类

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
class IdCard {
private Integer id;//身份证号码
private String somethingElse;

public IdCard(Integer id, String somethingElse) {
this.id = id;
this.somethingElse = somethingElse;
}

public Integer getId() {
return id;
}

public String getSomethingElse() {
return somethingElse;
}

@Override
public String toString() {
return "IdCard{" +
"id=" + id +
", somethingElse='" + somethingElse + '\'' +
'}';
}
}

最简单的办法:遍历

只要做两轮循环即可。
准备初始化数据:

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


private ArrayList<SocialSecurity> socialSecurities;
private ArrayList<IdCard> idCards;

@Before
public void setUp(){
socialSecurities = Lists.newArrayList(
new SocialSecurity(1, 12, "小明"),
new SocialSecurity(2, 13, "小红"),
new SocialSecurity(3, 14, "小王"),
new SocialSecurity(4, 15, "小peng")
);

idCards = Lists.newArrayList(
new IdCard(14, "xiaopeng"),
new IdCard(13, "xiaohong"),
new IdCard(12, "xiaoming")
);

//目标: 从socialSecurities中筛选出idCards中存在的卡片
}

遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 @Test
public void testFilterForEach(){
List<SocialSecurity> result = new ArrayList<>();
int count = 0;
for (SocialSecurity socialSecurity : socialSecurities) {
for (IdCard idCard : idCards) {
count++;
if (socialSecurity.getIdCard().equals(idCard.getId())){
result.add(socialSecurity);
}
}
}

System.out.println(result);
System.out.println(count);//12 = 3 * 4
//O(m,n) = m*n;
}

很容易看出,时间复杂度O(m,n)=m*n.

采用Hash

通过观察发现,两个list取相同的部分时,每次都遍历两个list。那么,可以把判断条件放入Hash中,判断hash是否存在来代替遍历查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
@Test
public void testFilterHash(){
Set<Integer> ids = idCards
.stream()
.map(IdCard::getId)
.collect(Collectors.toSet());
List<SocialSecurity> result = socialSecurities
.stream()
.filter(e->ids.contains(e.getIdCard()))
.collect(Collectors.toList());

System.out.println(result);
//初始化 hash 3
//遍历socialSecurities 4
//从hash中判断key是否存在 4
//O(m,n)=2m+n=11
}

如此,假设hash算法特别好,hash的时间复杂度为O(n)=n。如此推出这种做法的时间复杂度为O(m,n)=2m+n. 当然,更重要的是这种写法更让人喜欢,天然不喜欢嵌套的判断,喜欢扁平化的风格。

Hash一定会比遍历快吗

想当然的以为,hash肯定会比遍历快,因为是hash啊。其实,可以算算比较结果。比较什么时候2m+n < m*n
从数据归纳法的角度,n必须大于2,不然即演变程2m+2 < 2m。于是,当n>2时:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
@Test
public void testCondition(){
int maxN = 0;
for (int m = 2; m < 100; m++) {
for (int n = 3; n < 100; n++) {
if ((2*m+n)>m*n){
System.out.println("m="+m +",n="+n);
if (n>maxN){
maxN = n;
}
}
}
}

System.out.println(maxN);
}

结果是:

1
2
m=2,n=3
3

也就是说n<=3的时候,遍历要比hash快。事实上还要更快,因为hash还需要创建更多的对象。然而,大部分情况下,n也就是第二个数组的长度是大于3的。这就是为什么说hash要更好写。当然,另一个很重要的原因是lambda stream的运算符号远比嵌套循环让人喜爱。

Ryan Miao wechat
关注我的公众账号,接收最新文章
Donate
0%