常用的:
ArrayList 和LinkedList
HashSet和TreeSet
PriorityQueue
HashMap和TreeMap
1.ArrayList和LinkedList
ArrayList 线程不安全
LinkedList 线程不安全
ArrayList采用数组存储,LinkedList采用链表存储,所以ArrayList支持高速随机元素访问,LinkedList支持高速随机元素访问
我们在项目中一般是不会使用到 LinkedList
的,需要用到 LinkedList
的场景几乎都可以使用 ArrayList
来代替,并且,性能通常会更好!就连 LinkedList
的作者约书亚 · 布洛克(Josh Bloch)自己都说从来不会使用 LinkedList
2.HashMap
线程不安全(即在同一时刻有多个线程同时写HashMap时将可能导致数据的不一致)
哈希函数:
你认为的hash表是这样的:
其实是这样的:
index = hash_function(key)
也就是说先通过key得到index,有了index就可以到内存中取出数据了
当多个key通过哈希算法算出来的index相同:
JDK1.8 之前 HashMap
就是通过链地址法来解决哈希冲突的。不过,JDK1.8 以后HashMap
为了减少链表过长的时候搜索时间过长引入了红黑树。
HashMap扩容:
在JDK1.8之前,HashMap由数组+链表组成(拉链法解决哈希冲突的时候用到链表)
capacity表示数组的容量,默认是16,每次扩容后为当前数组容量的两倍(因此数组容量一定是2
的n次方)
localFactor:负载因子,默认是0.75
threshold:扩容的阈值,当数组容量达到这个值的时候,数组开始进行扩容,threshold=capacity*localFactor
在JDK1.8之后:
3.ArrayList扩容机制
Java ArrayList扩容机制_Pr Young的博客-CSDN博客_java中arraylist扩容
4.HashSet,线程不安全,底层数据结构是哈希表(HashMap)
TreeSet,线程不安全,底层结构是红黑树
LinkedHashSet ,线程不安全,底层结构是链表和哈希表
5.HashMap和HashTable之间的区别
(1)HashMap非线程同步,HashTable是线程同步的(也就是说HashTable的安全性更高,多线程访问的时候也不会出现问题),HashMap虽然不安全,但是效率比较高,比较快
(2)HashMap允许Key-Value键值对有空值,HashTable不允许键值对有空值
(3)初始大小和扩容机制不同
6.HashMap两种保证线程安全的方式:
方法一:返回的是一个新的Map,这个新Map是线程安全的
- HashMap map=new HashMap();
-
- Collections.synchronizedMap(map);
利用经典的synchronized进行互斥,锁住了尽可能大的代码块,性能比较差
方法二:比方法一有了很大的改进,使用ConcurrentHashMap
将HashMap进行了拆分,拆分成了多个独立的块,发生碰撞的几率大大啊降低锁住的代码块会比较少,性能比较好
使用NonfairSync,调用CAS指令来确保原子性和互斥性,当有多个线程恰好操作到同一个小分块的时候,只有一个线程会得到运行