java遍历的优化

说明：这是在面试中面试官出的题。虽然是常见的优化问题，但这种经验的确很有用。感慨之余，分享出来，以此共勉。

场景：现有List<PersonA>,List<PersonB>,PersonA 的属性是 String类型的身份证号，int型age；PersonB 的属性是 String类型的身份证号，int型sex；两个集合中的身份证号有相同的；

需求：查找身份证号相同的人的性别。

常见的思路是：

@Data
public class PersonA {
    private String card;
    private int age;

    public PersonA(String card, int age) {
        this.card = card;
        this.age = age;
    }
}
----------------------------------------------
@Data
public class PersonB {
    private String card;
    private int sex;

    public PersonB(String card, int sex) {
        this.card = card;
        this.sex = sex;
    }
}

public class TestForFor {private List<PersonA> pa;private List<PersonB> pb;@Beforepublic void before(){pa = new ArrayList<>();for (int i = 0; i < 10000; i++) {pa.add(new PersonA(UUID.randomUUID().toString(),20));}pa.add(new PersonA("abcd111",10));pa.add(new PersonA("abcd112",10));pa.add(new PersonA("abcd113",10));pa.add(new PersonA("abcd114",10));pa.add(new PersonA("abcd115",10));pa.add(new PersonA("abcd116",10));pb = new ArrayList<>();for (int i = 0; i < 10000; i++) {pb.add(new PersonB(UUID.randomUUID().toString(),Math.random() >= 0.5 ? 1 : 0));}pb.add(new PersonB("abcd111",1));pb.add(new PersonB("abcd112",1));pb.add(new PersonB("abcd113",1));pb.add(new PersonB("abcd114",1));pb.add(new PersonB("abcd115",1));pb.add(new PersonB("abcd116",1));}@Testpublic void testFor(){out.println("start search");for (PersonA a : pa) {for (PersonB b : pb) {if (a.getCard().equals(b.getCard())){out.println(b.getSex()==1?"男":"女");}}}}
}

结果。。。花费三秒多的时间。这还只是一万条数据

现在换一种思路，直接贴代码

 private List<PersonA> pa;
    private List<PersonB> pb;
    private Map<String,Object> map;
    @Before
    public void before(){
        out.println("start before");
        pa = new ArrayList<>();
        for (int i = 0; i < 10000; i++) {
            pa.add(new PersonA(UUID.randomUUID().toString(),20));
        }
        pa.add(new PersonA("abcd111",10));
        pa.add(new PersonA("abcd112",10));
        pa.add(new PersonA("abcd113",10));
        pa.add(new PersonA("abcd114",10));
        pa.add(new PersonA("abcd115",10));
        pa.add(new PersonA("abcd116",10));


        pb = new ArrayList<>();
        for (int i = 0; i < 10000; i++) {
            pb.add(new PersonB(UUID.randomUUID().toString(),Math.random() >= 0.5 ? 1 : 0));
        }
        pb.add(new PersonB("abcd111",1));
        pb.add(new PersonB("abcd112",1));
        pb.add(new PersonB("abcd113",1));
        pb.add(new PersonB("abcd114",1));
        pb.add(new PersonB("abcd115",1));
        pb.add(new PersonB("abcd116",1));
        map = new HashMap<>();
        for ( PersonB pbb : pb ) {
            map.put(pbb.getCard(),pbb.getSex());
        }
    }
    @Test
    public void testFor(){
        out.println("start search");
        for (PersonA a : pa) {
            if (map.containsKey(a.getCard())){
                out.print(a.getAge()+" ");
                out.println((int)map.get(a.getCard())==1?"男":"女");
            }
            //out.println(map.get(a.getCard())==null?"空":map.get(a.getCard()));
            //out.println((int)map.get(a.getCard())==1?"男":"女");
        }
    }

可以看出，查找的效率明显提升。

这里面的重点，第29行我用map重新填写了pb的数据[我的本地的sql坏了，所以用伪数据库的方式模仿，感兴趣也可以从数据库里试试]，

为什么用map填完了后速度会这么快？

原因很简单。因为ArrayList的底层是数组实现的，若要查找必定是从索引0开始一个个的进行比对；而HashMap则不同，

HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么对于查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度依然为O(1)，因为最新的Entry会插入链表头部，仅需要简单改变引用链即可，而对于查找操作来讲，此时就需要遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。

关于以上加粗内容取自博客

我在面试时只想到了hash，面试官提醒我用hashmap，恍然大悟。

---

时隔数月，回来归纳下这个问题。2018/9/13

---

其实这个问题可以抽象为：两个数组求交集，这里简要说下思路。

使用 treeset装载第一个数组，遍历第二个数组，if(！contains数组二中的值)，add到一个新list中,最后这个list存的就是交集

原创分享，转载标注。