说明: 这是在面试中面试官出的题虽然是常见的优化问题, 但这种经验的确很有用感慨之余, 分享出来, 以此共勉
场景: 现有 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;
- @Before
- public 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));
- }
- @Test
- public 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, 恍然大悟
原创分享, 转载标注
来源: https://www.cnblogs.com/find-the-right-direction/p/8506289.html