ZB-021-Collection体系原理

Collection体系简介

  • Collection 是接口，无法实例化
  • 有非常非常多的类继承它
  • 它是整个Collection的根接口

最重要的两个实现（接口）

  • List
  • Set

list添加元素的三种方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Main {
    public static void main(String[] args) {
        Collection<Integer> c = new LinkedList<Integer>();
        
        List<Integer> list = new ArrayList(c);

        List<Integer> list2 = new ArrayList();
        list2.addAll(c);


        List<Integer> list3 = new ArrayList();
        for (Integer i: c) {
            list3.add(i);
        }

    }
}

Collection常用方法

  • new: new ArrayList(Collection) 或者 new ArrayList()
  • R:size()/isEmpty()/contains()/for()/stream()

  • C/U:add()/addAll()/retainAll()

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    // 求交集
    List<Integer> list = new ArrayList();
    list.add(1);
    list.add(2);

    List<Integer> list2 = new ArrayList();
    list2.add(2);
    list2.add(3);


    list.retainAll(list2);
    System.out.println(list); // [2]

  • D:clear()/remove()/removeAll()

List

  • 最常用的ArrayList
    本质就是一个数组
  • 面试题：动态扩容的实现
    • 创建一个更大的空间，然后把原先的所有元素拷贝过去
  • add()方法

ArrayList扩容源代码

  • 非常非常好的代码风格
  • 代码清晰易懂，命名非常好(见名知意)
  • 傻子都可以写出让机器识别的代码，但优秀的程序员应该写出人类轻松识别的代码
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
36
37
38
39
40
41
42
43
44
45
46
47
48
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{

    ...

    public boolean add(E e) {
        // 确保容量够
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

    private void ensureCapacityInternal(int minCapacity) {
        // 计算容量
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        // 右移一位就是 除2
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }


     private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
    ...
}

疑问?扩容后，之前的数组是不是变成垃圾了

  • 是
  • 垃圾回收帮你处理，你不用操心，你操心也操心不上。不归你管

Set

1
2
3
4
5
6
7
8
9
10
11
12
public class Main {
    public static void main(String[] args) {

        List<Integer> list = new ArrayList();
        list.add(1);
        list.add(2);
        list.add(2);
        list.add(3);

        Set<Integer> set = new HashSet(list); // [1,2,3]
    }
}
  • equals约定：不允许有重复元素
    判断重复：equals

  • 如果你有一个Set,如何实现？

    • 容易想到的办法都比较低效
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      class MySet {
          List<Object> elements;

          void add(Object object){
              if(!elements.contains(object)){
                  elements.add(object);
              }
          }
      }

      // 每次添加的时候都要比较当前列表里是否存在，非常的低效
      // 假设Set有100万数据,每次都比较100万次 非常低效
      set ==> [张三，李四，王五]

      set.add("张三"); 
      挨个比较非常低效

  • Java世界里第二最大重要的约定：hashCode

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    改良上面的低效问题， 百家姓
    张:张三，张三丰
    李:李四
    赵:赵六

    这样每次添加的时候 如 添加 赵奕欢
    先找 “赵”
    这样无形中提高了效率

    这个“百家姓”就是 hashCode

    同理我们想知道我们的 Object是不是重复的 
    - 新建很多“桶”  ==>哈希桶 
    - 映射成一个 int值 均匀的分配到 桶里面去
    - 此时有一个 obj 来了，想知道它存在不存在，只需要算一下它的 hashCode
    - 然后去对应的 hash桶里找就好了
    • 同一个对象必须始终返回相同的hashCode
    • 两个对象的 equals 返回 true,必须返回相同的 hashCode
    • 两个对象不等，也可能返回相同的hashCode
      • 百家姓里 “张” 姓 张三，张三丰 都姓“张” ==> hashCode相同

哈希算法

  • 哈希就是一个单向的映射
  • 例子：从姓名到姓的哈希运算
  • 从任意对象到一个整数的hashCode

注意！ 整数int的值是有范围的 正副21亿，而对象是无限多的可能

HashSet

  • 最常用！最高效的Set实现

    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
    public class Main {
        public static void main(String[] args) {


            List<Integer> list = new ArrayList();
            Set<Integer> set = new HashSet();

            for (int i = 0; i < 1000_0000; i++) {
                set.add(i);
                list.add(i);
            }

            long t0 = System.nanoTime();
            set.contains(9999_9999);

            long t1 = System.nanoTime();
            list.contains(9999_9999);

            long t2 = System.nanoTime();

            System.out.println("set:"+(t1-t0)/1000.0/1000);
            System.out.println("list:"+(t2-t1)/1000.0/1000);
        }
    }

    // 执行效率
    set:0.016948
    list:29.803517

  • HashSet 是无序的！如果有需要使用LinkedHashSet(双向链表)

Map

  • C/U:put/putAll
  • R
    • get/size
    • containsKey/containsValue
    • keySet/values/entrySet
  • D:remove/clear

Map非常容易踩到的坑

1
2
3
4
5
6
7
8
9
10
11
Map<String,String> map = new HashMap<>();
map.put("a":"1");
map.put("b":"2");

Set<String> keyset = map.keySet(); // ["a","b"]

// 坑来了
// 你修改 map 里的 key 会映射到 keyset里
// 你修改 keyset 里的值 会映射到 map里
map.remove("a");
// 此时 keyset ==》["b"]

entrySet

1
2
3
4
5
6
7
Map<String,String> map = new HashMap<>();
map.put("a":"1");
map.put("b":"2");
for(Map.Entry<String,String> entry:map.entrySet()){
    System.out.println(entry.getKey());
    System.out.println(entry.getValue());
}

面试题

HashMap 和 HashSet 区别

  • HashMap的key的Set就是一个 HashSet

请说一下 HashMap 扩容过程

  • 跟 ArrayList 一样，创建一个更大的 HashMap
  • 然后把之前的元素拷贝过来

问到唬住就50K唬不住就5K

HashMap的线程不安全性

HashMap在 Java7+ 后的改变： 链表==> 红黑树

  • 我们知道 HashSet/HashMap 本质实现是有很多 哈希桶 存储相同 hashCode
  • 但是之前说到 桶的个数是有限的，而对象可能是无限的 此时可能发生碰撞
  • 以致于 hashCode相同 因此被放到同一个 Hash桶里 ，但是 它们是不同对象所以equals 返回false
  • 问题来了，假如一组数据 它们hashCode都一样。你会发现 HashSet 就退化成了一个 链表
  • 假如你有100万个元素 你希望平均的分配在10万个桶里，但如遇到碰巧精心设计的一组数据 hashCode 相同，此时这个桶的性能就会急剧恶化
  • 坏处就是 HashSet 的性能和 List 一样了

因此在JDK7之后，当发生 哈希碰撞的时候，这个东西就不是链表了而是 红黑树

  • 红黑树 超级复杂的数据结构
    • 如被问到知道是什么东西就行了
    • 原理都不用知道
    • 面试官也够呛知道，如果让你手写，就说我不会，等面试结束的反问问题，我不会红黑树，你给我写一个红黑树！

补充知识

Set

  • HashSet 完全随机
  • LinkedHashSet 保证和插入顺序一样
  • TreeSet 有序的(会进行一个排序) 自然顺序从小到大
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Main {
    public static void main(String[] args) {

        List<Integer> list = Arrays.asList(100000,142,-2,-323121,321321,15);

        Set set1 = new HashSet(list);
        Set set2 = new LinkedHashSet(list);
        Set set3 = new TreeSet(list);

        set1.forEach(System.out::println); // 无序的
        set2.forEach(System.out::println); // 按添加顺序
        set3.forEach(System.out::println); // 排好序的
    }
}

TreeSet / ArrayList查找时间复杂度

  • ArrayList O(n)
  • TreeSet O(log n)

把算法的复杂度从 线性时间下降到对数时间

TreeSet/TreeMap

  • 二叉树/红黑树
  • 使用Comparable约定，认定排序相等的元素相等
  • 二叉树查找/插入

Collections 工具方法集合

  • emptySet() 返回一个空的集合
  • synchronizedCollection: 将一个集合变成线程安全的
  • unmodifiableCollection: 将一个集合变成不可变的 
    1
    2
    3
    4
    5
    List<Integer> list = Arrays.asList(100000,142,-2,-323121,321321,15);
    Set set1 = new HashSet(list);
    Set unmodifiableSet = Collections.unmodifiableSet(set1);

    unmodifiableSet.add(1); //报错

Collection 其他实现

  • Queue 队列/Deque 双端队列
    • 任何你想用 Stack的时候都可以使用 Deque
  • Vector/Stack
  • LinkedList 链表
  • ConcurrentHashMap
  • PriorityQueue 优先级队列 比如你的 闹钟列表 离你最近的那个会响

Guava 番石榴

补充java中 不完整的Collection实现

  • Lists/Sets/Maps
  • ImmutableMap/ImmutableSet 不可变的Map/Set

  • MultiSet/MultiMap 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    Set => 1,2,3,4

    #除了告诉你唯一的元素有那些，还可以告诉你 3 被加了几次
    MultiSet => 1,2,3x3,4 

    Map  key:value

    MultiMap 
    key:对应多个value

  • BiMap 双向Map

    • 普通的Map是 value对key的映射
    • BiMap 是双向映射