面试系列之java集合
1.java集合接口
集合类在java.util包下,主要有Set、List和Map
Collection:Collection 是集合 List、Set、Queue 的最基本的接口。
Iterator:迭代器,可以通过迭代器遍历集合中的数据
Map:是映射表的基础接口
java集合类
java集合框架
2.List
List是非常常用的集合,它里面的元素是可重复且有序的,主要有三个实现类分别是:ArrayList、Vector、LinkedList。
3.ArrayList
数据结构:底层是用数组实现的,利用数组连续下标的特性可以快速读取对应的元素
扩容机制:当容量不足需要扩容时,通过复制元素到新的数组。
线程安全:否
特点:查询快,利用数据的连续下标特点,增删慢,因为增删后需要对数组进行复制,移动。所以适合查多写少的场景。
4.Vector
Vector和ArrayList一样底层都是数组实现的,不同的是Vector是线程安全的。也就是说同一时刻只能由一个线程对Vector进行写,避免了多线程操作的数据安全问题,同时由于加锁的操作也使得性能低于ArrayList。
5.LinkedList
数据结构:双向链表结构,增删比较快只要修改前后指针的指向,读取由于没有下标需要遍历读
扩容机制:自动扩容
线程安全:否
特点:适合动态的增删,随机读取速度比较慢,另外还提供了操作头尾元素的方法,很适合做堆栈,队列或双向队列。
6.Set
Set主要是侧重元素的唯一性,且无序的,存入和读取不一定一样。保证唯一性主要是通过hashCode来保证,java对象的hashCode是通过内存地址来计算的哈希值。如果想让两个不同的对象视为相等就要重写Object的hashCode方法和equals方法。
7.HashSet
HashSet数据的存储和读取是根据哈希值来计算的,是无序的。HashSet会先判断hashCode方法是否一样,如果不一样就是不同对象,如果一样还要继续判断equals方法的返回结果,true就认为是同一个对象,false就是不同对象。但是他们的存储是有所不同的。
hashCode不同:
哈希值不同
hashCode一样,equals返回false:
哈希值相等
也就是说一个哈希值的位置上可以存放多个元素,只不过他们形成一个链表或者说放到一个哈希桶中。
8.TreeSet
TreeSet是以二叉树结构来存放,每新增一个对象都会按升序或降序存放到二叉树指定位置。
但是升序降序要实现Comparable接口重新compareTo()方法,Integer和String可以进行默认排序。
9.LinkedHashSet
LinkedHashSet实际上就是集成了HashSet,结构又是用LinkedHashMap来存储,说白了就是只用到Map的key部分。所以LinkedHashSet的方法和HashSet几乎一样,只是提供了几个构造函数,构造函数调用父构造函数初始化LinkedHashMap来做数据存储。
10.HashMap
Map是存放键值对数据,HashMap的key不允许重复,允许为null,但是只有一个null,value可以重复也可以为null。正常情况下通过哈希值都能快速读取到元素,但是遍历的顺序是不一定的。HashMap是非线程安全的。hashMap有几个比较重要的属性1. capacity:当前数组容量,始终保持 2^n,可以扩容,扩容后数组大小为当前的 2 倍。2. loadFactor:负载因子,默认为 0.75。3. threshold:扩容的阈值,等于 capacity * loadFactor。
不同版本的jdk,hashMap的结构有所区别
jdk1.7版本主要是哈希+链表的结构
1.7hashMap结构
大体上看是一个数组结构当哈希值冲突的时候在对应位置演变成一个链表结构,链表结构存的是Entry对象包括key,value,哈希值和next信息。
jdk1.8版本主要是哈希+链表+红黑树的结构
1.8hashMap结构
jdk1.8对hashMap的结构进行了优化,1.7中哈希冲突的的时候在对应位置上演变链表位置,那查找的时候链表上的元素的时候时间复杂度就是O(n),取决于链表的长度。1.8中在链表的长度超过8的时候将链表演变成红黑树,自然查找的效率就高很多。
11.ConcurrentHashMap
ConcurrentHashMap和HashMap的结构差不多,但是呢它是线程安全的,所以为了解决这个线程安全又想效率维持在较高的水平,就多了分段的概念。整个ConcurrentHashMap是有一个个分段Segment组成,Segment通过继承ReentrantLock来进行对该分段进行加锁,该分段里的数据结构跟HashMap几乎一样。
ConcurrentHashMap
在jdk1.8中链表超过8也是演变成红黑树。
ConcurrentHashMap 有 16 个 Segments,所以理论上,这个时候,最多可以同时支
持 16 个线程并发写,只要它们的操作分别分布在不同的 Segment 上。这个值可以在初始化的时
候设置为其他值,但是一旦初始化以后,它是不可以扩容的。
12.HashTable
HashTable现在几乎不使用了,他的功能和HashMap一样,是线程安全的,但是加锁的粒度比较大性能不是很高,如果想要线程安全就用ConcurrentHashMap,不在乎线程安全的场景就用HashMap。
13.TreeMap
TreeMap实现了SortedMap接口,支持根据key进行排序,默认是按键值的升序排序,也可以指定排序的比较器,在使用 TreeMap 时,key 必须实现 Comparable 接口或者在构造 TreeMap 传入自定义的
Comparator,否则会在运行时抛出 java.lang.ClassCastException 类型的异常。