Collection体系
对Collection了如指掌
- Set/List/Map/SortedSet/SortedMap/HashSet/ArrayList/LinkedList/Vecotr/Collections/Arrays/AbstractCollection
- 每个方法的含义(包含java8之后的default方法)
Collection体系的核心约定
equals
- 自反性
- 对称性
- 传递性
-
hashCode
终生不变性
- equals相同则hashCode必须相同
-
Comparable/Comparator
自然顺序:从小到大
x
-1 - x=y -> 0
-
如果写,就好好写,不要用奇技淫巧
-
在实践中,几乎永远不需要手工写他们
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){
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}.
- / ```
- 可以取第一个/最后一个
- 可以进程范围查询
论数组
什么是数组
- jvm原生提供的定长数据结构,类型安全
- 下面就是数组的声明
为什么从来没见过数组的定义
- 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) -> 无论数据规模多大,时间总是常数
- 扩容麻烦(慢,费内存)
- 什么是RandomAccess?
- 标记接口,用于实现快速算法 用于标记一个东西可以被实现,但是没有方法。 arraylist就实现了这个接口。 下图是Collections接口的方法,如果list实现了randomAccess,那么查找的时候可以基于索引进行寻址(get操作)。但是没有实现的话,只能使用基于迭代器的二分查找进行寻址,速度慢
初始化
- 指定一个长度,初始化的时候按照这个长度分配内存,如果长度等于零,那么声明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位的长度),然后把原来的数组都给放到新数组里面,再把新追加的元素丢到对应的位置上
删除元素
删掉的元素,后面的元素应该补进来,删除的元素如果是最后一个,那么就不用补
为什么需要 elementData[—size] = null // clear to let GC do its work
如果不这么做,那么被删掉元素位置会持有object3的强引用,导致object3没办法被GC,导致内存泄漏。
面试考点
- 基于什么实现
- 数组
- 查找/插入/删除时间复杂度
- O(1)/O(n)/O(n) 解决一个规模为n的问题,需要的时间是常数/n
- 因为arraylist查找实现了随机查找,无论是找第一个还是第100万个,花费的时间都一样。 增加和删除涉及到元素的位置移动,花费的时间是随元素的规模而增长的。
- 扩容是如何实现的
- *1.5倍
- 拷贝
LinkedList
不光实现了List还实现了Deque(双端队列)
- 使用双向链表
- 经典的双链表实现:prev/next指针
- 查找非常慢
- O(n)
- 从头/尾删除
- O(1)
- 因此适合作为队列
- transient(转瞬即逝的) 是个什么东西。 不应该被序列化。比如用户的密码,不应该被保存再序列话的数据里面
添加元素
加到最后一个元素上去
查找元素(要亲命的骚操作)
linkedlist 查找操作做了一点点的优化。节点是双向链表,要查找的元素再列表的前半部分,那么从头开始找,再后半部分从尾部开始找
考点
- 核心数据结构
- 双向链表
- 查找/插入/删除复杂度
- 查找O(n)
- 查找+插入/删除 O(n)
- 头尾插入/删除 O(1)
和ArrayList区别和联系?
数据结构:哈希表简介
- 哈希桶+链表
- O(1)的平均插入,查找,删除时间
- 致命缺陷的哈希值的碰撞
- HashSet:简单粗暴的HashMap套皮实现
Java7时代的hashmap
- 经典的hash表实现
- 初始容量/负载因子/哈希算法/扩容
- hash数组+链表
- 问题
- 并发环境下,非常容易碰到死锁 详细见链接 链接
- CVE-2011-4858 可能hashCode返回的一致,那么hashMap会退化成一个链表,原本是O(1)的复杂度,变成了O(n)的复杂度
负载因子:当当前的容量达到总容量的75%时,map将进行扩容,即负载因子
哈希算法:来了一个对象,变成了一个整数,怎么把整数映射到hash桶上
hash算法避免碰撞。
Java8时代的hashMap
- 解决安全问题
- 改用哈希桶+链表+红黑树的数据结构
- 解决线程安全问题(注意:任然是线程不安全的)
- 再扩容时使用与插入顺序一致的方法
当前桶的容量超过下面这个值,那么链表将转换为红黑树
当小于下面的值,那么树就会被转换回为链表
红黑树和TreeMap
基于红黑树的数据结构,详细见另一篇博客 红黑树
HashSet/LinkedHashSet/TreeSet
- 简单粗暴
- 直接包装一个HashMap/LinkedHashMap/TreeMap