Java集合
[TOC]
集合概述
List
Set
Queue
Map
HashMap
底层数据结构,重要的四个点 HashMap原理解析
- HashMap的底层实现数据结构
- HashMap初始化和桶数组的初始化 HashMap桶数组长度初始化 为什么HashMap桶数组长度为2的幂次
- HashMap的扩容 何时扩容、扩容多少、负载因子和容量 为什么负载因子是0.75 红黑树漫画解析 红黑树插入删除操作详解 红黑树插入删除操作详解2.0
- HashMap为什么线程不安全 HashMap是否可以使用任意类型作为key? 为什么Integer、String这种包装类适合作为HashMap的key? 如果使用Object作为key,需要注意什么? HashMap的优缺点
LinkedHashMap
ConcurrentHashMap
TreeMap
HashTable
hash,hashCode,key-value,HashTable实现原理,重要的三个点 HashTable原理
- HashTable重要三点
- HashTable源码分析1.0 HashTable源码分析2.0
- HashTable线程安全
- HashTable和HashMap的区别1.0 HashTable和HashMap的区别2.0 底层结构 初始化 插入 null 效率 安全 扩容
- HashTable的k-v为什么不允许为null
线程安全的HashMap
(1)使用ConcurrentHashMap (2)使用HashTable (3)Collections.synchronizedHashMap()方法
ConcurrentHashMap原如何保证的线程安全
JDK1.7:使用分段锁,将一个Map分为了16个段,每个段都是一个小的hashmap,每次操作只对其中一个段加锁
JDK1.8:采用CAS+Synchronized保证线程安全,每次插入数据时判断在当前数组下标是否是第一次插入,是就通过CAS方式插入,然后判断f.hash是否=-1,是的话就说明其他线程正在进行扩容,当前线程也会参与扩容;删除方法用了synchronized修饰,保证并发下移除元素安全
HashTable与HashMap的区别
(1)HashTable的每个方法都用synchronized修饰,因此是线程安全的,但同时读写效率很低 (2)HashTable的Key不允许为null (3)HashTable只对key进行一次hash,HashMap进行了两次Hash (4)HashTable底层使用的数组加链表
ArrayList和LinkedList的区别
ArratList的底层使用动态数组,默认容量为10,当元素数量到达容量时,生成一个新的数组,大小为前一次的1.5倍,然后将原来的数组copy过来;因为数组在内存中是连续的地址,所以ArrayList查找数据更快,由于扩容机制添加数据效率更低
LinkedList的底层使用链表,在内存中是离散的,没有扩容机制;LinkedList在查找数据时需要从头遍历,所以查找慢,但是添加数据效率更高
如何保证ArrayList的线程安全?
(1)使用collentions.synchronizedList()方法为ArrayList加锁 (2)使用Vector,Vector底层与Arraylist相同,但是每个方法都由synchronized修饰,速度很慢 (3)使用juc下的CopyOnWriterArrayList,该类实现了读操作不加锁,写操作时为list创建一个副本,期间其它线程读取的都是原本list,写操作都在副本中进行,写入完成后,再将指针指向副本。