List列表
ArrayList,基于数组
LinkList,基于链表
Vector,基于数组,线程安全
Stack栈,后进先出
ArrayQueue,数组队列,先进后出
set
HashSet,基于哈希表
LinkHashSet,基于链表
TreeSet,基于树
map
HashMap,基于哈希表
LinkHashMap,基于数组
TreeMap,基于哈希表
Queue
ArrayDeque,数组实现的双端队列
底层是一个Object[]
在jdk1.8中默认创建容量为0的数组
在容量用完时会自动扩容
优化:可以使用ArrayList(int capacity)设置初始化的容量,可以避免一开始就不断扩充容量,影响效率
查询效率高,增删效率差
底层是一个双向链表
增删效率高,查询效率差
查询指定下标的元素时,需要从头节点开始遍历
LinkedList.add方法只能将元素添加道链表末尾,如果要添加到中间,需要使用迭代器方法:ListIterator.add
底层是一个数组
当容量用完时,默认扩充为原容量的两倍
线程安全的,内置方法都带有synchronized关键字
如何将ArrayList变成线程安全的,调用Collections工具类中的synchronizedList(List list)方法
是一种泛型
在jdk1.5引入,之前都是使用Object[]
Object[]的缺点
需要强制转换类型
使用方法前需要用instanceof判断对象类型
使用Set优点
减少强制转换类型的次数
类型安全
运行阶段在JVM看不到泛型类型
支持lambda表达式
基于哈希表
无序,不可重复
底层是树
无序,不可重复,但是可以排序
HashMap的key部分底层是HashSet,TreeMap的key部分底层是TreeSet
Map和Collections没有继承关系
Map以键值对形式存储数据,key和value都是存储对象的内存地址(引用)
Map的迭代方法:
第一类:效率低下,得到Map的key集合keySet,再取出对应的value
通过foreach遍历map.keySet,取出对应的value
使用迭代器迭代keySet,取出Value
第二类:效率高,直接从结点中取出key和value
调用map.entrySet,然后foreach遍历keySet
调用map.entrySet,然后通过迭代器遍历keySet
基于数组和单链表
数组中每一个元素都是单链表
单链表中每一个结点Node的hash值不一定相同,但是下标一定是相同的,因为下标都是通过hash值哈希算法计算的
数组查询效率高,单链表增删效率高,HashMap结合了两者的优点
无序:因为不知道值挂到哪一个单链表上去了
不可重复:使用equals实现不可重复
默认初始容量为16(必须为2的次方),加载因子为0.75,即容量使用了3/4就开始扩容
在jdk1.7及其以前,使用数组+单链表实现;在jdk1.8时,使用数组+单链表+红黑树实现
单链表元素超过8个,将单链表转换成红黑树
当红黑树结点小于6个,将红黑树转换成单链表
这样做是为了提高检索效率,二叉树的检索会缩小检索范围,提高效率
将key,value封装到Node中
调用key的hashCode()获得hash值
使用hash值进行哈希函数计算得到下标
如果该下标没有元素,将该结点放入
如果有元素,将Node的key与该链表上的每个结点的key进行equals对比
如果都返回false,将该节点放入到该链表末尾
如果有一个返回了true,那么链表中对应这个结点的value会被Node的value覆盖(保证了不可重复)
注:
HashMap的key,value可以为null,但是只能有一个(不可重复)
HashTable的key,value都不能为null
先调用key的hashCode()函数计算hash值
通过哈希算法,将hash值转化为数组的下标
通过下标定位数组的某个位置:
如果这个位置什么都没有,返回null
如果这个位置有一个链表,将链表所有结点的key与当前key进行equals比对
如果都返回false,那么get方法返回null
如果有一个equals返回了true,那么返回这个结点的value
注:放在HashMap中的key的元素需要同时重写hashCode和equals方法
hash冲突:键(key)通过hash函数得到的结果作为地址去存放键值对(key-value)(这就是hashmap的存值方式),当时计算发现这个地址已经存放了键值对,就会产生冲突,这就是hash冲突。
解决方法:
1、开放定址法:当冲突发生时,通过某种探测技术在散列表上形成一个探测序列,沿着此序列逐个查找,直到找出一个开放的地址。常见的探测技术有:线性探测、再平方探测、伪随机探测
2、再哈希法:对冲突的哈希值再次进行哈希处理,直到没有哈希冲突。
3、链地址法:将所有哈希地址为i的元素构成一个称为同义词链的单链表,并将单链表的头指针放在哈希表的第i个单元中。链地址法适用于经常进行插入和删除的情况。
4、建立公共溢出区:将哈希表分为基本表和溢出表两部分,凡是和基本表发生冲突的元素,都放入溢出表。
ArrayList基于数组,对随机index的访问比较快,空间浪费体现在列表结尾的预留空间
LinkList基于链表,增加和删除元素比较快,空间浪费体现在每个元素都需要消耗一定的空间
Vector是线程安全的类,而ArrayList是非线程安全的。
底层结构:1.7采用数组+链表,1.8采用数组+链表+红黑树
初始化方式:哈希表为空时,1.7采用inflateTable()初始化一个数组;1.8采用resize()扩容
put()实现方式:1.7采用头插法;1.8采用尾插法
hash()实现方式:1.7直接计算key的hashCode值;1.8采用key的hashCode异或key的hashCode进行无符号右移16位的结果
扩容策略:在1.7中,只要元素个数不小于阈值(容量的3/4)就直接扩容2倍。在1.8中,容量未达到64时,以2倍扩容,超过64时,若单链表元素个数超过8个,将单链表转换成红黑树,若红黑树节点小于6个,将红黑树转换成单链表,这样做是为了提高检索效率,二叉树的检索会缩小检索范围,提高效率
String变量不可修改,StringBuffer和StringBuilder可以修改
StringBuffer是线程安全的,StringBuilder不是线程安全的。
StringBuffer使用了缓存区,StringBuilder没有使用缓存区,所以没有修改数据的情况下,多次调用StringBuffer的toString方法获取的字符串是共享底层的字符数组的。而StringBuilder不是共享底层数组的,每次都生成了新的字符数组。
因为方法被上锁,所以StringBuffer的性能一般会比StringBuilder差,单线程中建议使用StringBuilder。
String对象的相加底层调用的是StringBuilder对象,分别调用了append方法和toString方法,所以在大量字符串相加时,使用String对象相加效率低于使用StringBuffer和StringBuilder,因为还有有StringBuilder对象的创建过程和toString方法中字符数组的拷贝过程。