image.png

Collection体系

对Collection了如指掌

  • Set/List/Map/SortedSet/SortedMap/HashSet/ArrayList/LinkedList/Vecotr/Collections/Arrays/AbstractCollection
  • 每个方法的含义(包含java8之后的default方法)

Collection体系的核心约定

equals

  • 自反性
  • 对称性
  • 传递性
  • 一致性

    hashCode

  • 终生不变性

  • equals相同则hashCode必须相同
  • equals不同hashCode可以不同

    Comparable/Comparator

    自然顺序:从小到大

  • x -1

  • x=y -> 0
  • x>y -> 1

    如果写,就好好写,不要用奇技淫巧

  • 整型的一处:减肥与取非

    在实践中,几乎永远不需要手工写他们

  • Integer.compare

  • Comparator

SortedSet/SortedMap

有序的集合

  • 使用Comparable/Comparator约定

    • 坑 对象的消失之谜 ```java public class User implements Coparable { private Integer id; private Integer age;

      // get set

      @override public boolean equals(Object o) { if(this == 0){

      1. return true;

      } if(o == null || getClass() != o.getClass()){

         return false;
      

      } User user = (User) o; return Objects.equals(id, user.id)

      }

      @override public int hashCode(){ return Objects.hash(id); }

      @override public int compareTo(User that){ return this.age.compareTo(that.age) }

      public static void main(STring[] args){ Set set = new TreeSet<>(); set.add(new User(1, 10)); set.add(new User(2, 20)); set.add(new User(3, 10));

      System.out.println(set) } } // 本来应该有3个元素,但是打印出来的结果只有两个 // 原因: equals因该和compareTo的比较的结果应该是一致的。如果compareTo返回0的话,那么equals必须得返回true,保持一直 // 因为treeSet比较元素相同的时候,会用到compareTo方法, equals用id来比较,compareTo用年龄来比较, // 因为第三个人年龄和第一个一样,所以在set里面就会被认为是重复的元素,那么就添加不进去 // 以下是Comparable接口的类的注释

/*

  • The natural ordering for a class {@code C} is said to be consistent
  • with equals if and only if {@code e1.compareTo(e2) == 0} has
  • the same boolean value as {@code e1.equals(e2)} for every
  • {@code e1} and {@code e2} of class {@code C}. Note that {@code null}
  • is not an instance of any class, and {@code e.compareTo(null)} should
  • throw a {@code NullPointerException} even though {@code e.equals(null)}
  • returns {@code false}.

    • / ``` image.png
  • 可以取第一个/最后一个
  • 可以进程范围查询

论数组

什么是数组

  • jvm原生提供的定长数据结构,类型安全
  • 下面就是数组的声明

image.png

为什么从来没见过数组的定义

  • jvm提供了虚拟机级别的支持,有对应的字节码
  • 数组是jvm原生提供的,在虚拟机指令级支持的一个特殊的类,就是数组的本质,如下面的代码所示

    class String[]{
      public int length;
      public [x][x][x][x]...[x] // 10个元素
    
      // 方法名字就叫做【】, 所以可以使用这个方法名来来直接取到数组内的元素
      public String [] (int i){
          return // 第i个元素
      }
    
      // 这样来保证类型安全
      public void set(){
          if (s instanceof String){
              //
          } else {
              throw new ArrayStoreException();
          }
      }
    }
    

ArrayList

  • 使用Array(数组)作为内部存储
    • 速度快:寻址操作O(1) -> 无论数据规模多大,时间总是常数

image.png

  • 扩容麻烦(慢,费内存)
    • 什么是RandomAccess?
  • 标记接口,用于实现快速算法 用于标记一个东西可以被实现,但是没有方法。 arraylist就实现了这个接口。 下图是Collections接口的方法,如果list实现了randomAccess,那么查找的时候可以基于索引进行寻址(get操作)。但是没有实现的话,只能使用基于迭代器的二分查找进行寻址,速度慢

image.png

初始化

  • 指定一个长度,初始化的时候按照这个长度分配内存,如果长度等于零,那么声明arrayList长度为0,减少内存开销,详细见源码
      /**
       * Constructs an empty list with the specified initial capacity.
       *
       * @param  initialCapacity  the initial capacity of the list
       * @throws IllegalArgumentException if the specified initial capacity
       *         is negative
       */
      public ArrayList(int initialCapacity) {
          if (initialCapacity > 0) {
              this.elementData = new Object[initialCapacity];
          } else if (initialCapacity == 0) {
              this.elementData = EMPTY_ELEMENTDATA;
          } else {
              throw new IllegalArgumentException("Illegal Capacity: "+
                                                 initialCapacity);
          }
      }
    

    添加元素

    先进行容量确认,不够就扩容,扩为原来长度的1.5倍(增加原来长度右移1位的长度),然后把原来的数组都给放到新数组里面,再把新追加的元素丢到对应的位置上
    image.png
    image.png

删除元素

删掉的元素,后面的元素应该补进来,删除的元素如果是最后一个,那么就不用补
image.png
image.png
为什么需要 elementData[—size] = null // clear to let GC do its work
image.png
如果不这么做,那么被删掉元素位置会持有object3的强引用,导致object3没办法被GC,导致内存泄漏。

面试考点

  • 基于什么实现
    • 数组
  • 查找/插入/删除时间复杂度
    • O(1)/O(n)/O(n) 解决一个规模为n的问题,需要的时间是常数/n
    • 因为arraylist查找实现了随机查找,无论是找第一个还是第100万个,花费的时间都一样。 增加和删除涉及到元素的位置移动,花费的时间是随元素的规模而增长的。
  • 扩容是如何实现的
    • *1.5倍
    • 拷贝

LinkedList

不光实现了List还实现了Deque(双端队列)

  • 使用双向链表
    • 经典的双链表实现:prev/next指针
  • 查找非常慢
    • O(n)
  • 从头/尾删除
    • O(1)
    • 因此适合作为队列

image.png

  • transient(转瞬即逝的) 是个什么东西。 不应该被序列化。比如用户的密码,不应该被保存再序列话的数据里面

image.png
image.png

添加元素

加到最后一个元素上去
image.png

查找元素(要亲命的骚操作)

linkedlist 查找操作做了一点点的优化。节点是双向链表,要查找的元素再列表的前半部分,那么从头开始找,再后半部分从尾部开始找
image.png

考点

  • 核心数据结构
    • 双向链表
  • 查找/插入/删除复杂度
    • 查找O(n)
    • 查找+插入/删除 O(n)
    • 头尾插入/删除 O(1)
  • 和ArrayList区别和联系?

    • 核心数据结构差别
    • 使用场景

      HashMap

  • 数据结构:哈希表简介

    • 哈希桶+链表
    • O(1)的平均插入,查找,删除时间
    • 致命缺陷的哈希值的碰撞
  • HashSet:简单粗暴的HashMap套皮实现

Java7时代的hashmap

  • 经典的hash表实现
    • 初始容量/负载因子/哈希算法/扩容
  • hash数组+链表
  • 问题
    • 并发环境下,非常容易碰到死锁 详细见链接 链接
    • CVE-2011-4858 可能hashCode返回的一致,那么hashMap会退化成一个链表,原本是O(1)的复杂度,变成了O(n)的复杂度
    • image.png

负载因子:当当前的容量达到总容量的75%时,map将进行扩容,即负载因子
哈希算法:来了一个对象,变成了一个整数,怎么把整数映射到hash桶上
image.png
image.png
hash算法避免碰撞。

image.png
image.png
image.png

Java8时代的hashMap

  • 解决安全问题
    • 改用哈希桶+链表+红黑树的数据结构
  • 解决线程安全问题(注意:任然是线程不安全的)
    • 再扩容时使用与插入顺序一致的方法

image.png
当前桶的容量超过下面这个值,那么链表将转换为红黑树
image.png
当小于下面的值,那么树就会被转换回为链表
image.png
image.png

红黑树和TreeMap

基于红黑树的数据结构,详细见另一篇博客 红黑树

image.png

HashSet/LinkedHashSet/TreeSet

  • 简单粗暴
    • 直接包装一个HashMap/LinkedHashMap/TreeMap