java常用数据结构

List：ArrayList 和 LinkedList

? ? ?1、ArrayList 和 LinkedList都是非线程安全
?????2、ArrayList 可以直接根据下表定位元素，查找速度快，但是修改元素慢；LinkedList 查找元素必须从第一个开始逐个查找，查找速度慢，但是修改元素快
?????3、当多个线程访问list时，因为每两个相邻节点之间存在前后关系(指针或内存地址)，所以多个线程同时对list添加数据时会报错

Set：HashSet、LinkedHashSet、TreeSet

? ? ?1、HashSet：存放的元素是无序的，可以存null
? ? ?2、TreeSet: 存放的数据是有序的（根据存放的数据排序，而不是存放的先后顺序，同时也提供了排序规则的构造函数），不能存null
? ? ?3、LinkedHashSet: 有序，基于链表实现
? ? ?4、HashSet、TreeSet、LinkedHashSet都是非线程安全的

Map：HashMap、TreeMap、Hashtable、ConcurrentHashMap

? ? 1、HashMap 非线程安全，数据是无序的，可存储空的键或值，查找的事件复杂度是O(1)，
? ? 2、TreeMap 非线程安全，基于红黑树实现，根据键的自然顺序或Comparator 来排序，查找的事件复杂度是O(logn)
? ? 3、Hashtable 通过在方法上加 synchronized实现了线程安全，性能差

? ? ? ? ?也可以通过?Collections.synchronizedMap(hashMap) 获得一个线程安全的类，也是通过在方法上加 synchronized实现线程安全

? ? ?4、ConcurrentHashMap：是线程安全的，通过put方法看一下ConcurrentHashMap的原理

? ? ? ? ? ?从下面的代码可以看到ConcurrentHashMap是通过cas、synchronized在方法里面加锁，锁的粒度比Hashtable要小，所以效率更高；

? ? ? ? ? ?在jdk1.7中使用了Segment 来优化来提高效率，一个ConcurrentHashMap中默认有16个Segment ，每个Segment都是线程安全的，而且Segment负责一段hash值，这样可以最多16个线程同时对map操作，但在jdk1.8中不再使用Segment，虽然代码中仍然有Segment知识为了兼容以前的版本；

final V putVal(K key, V value, boolean onlyIfAbsent) {
? ? ? ? if (key == null || value == null) throw new NullPointerException();
?? ??? ?//获取键的hash值
? ? ? ? int hash = spread(key.hashCode());
? ? ? ? int binCount = 0;
? ? ? ? for (Node<K,V>[] tab = table;;) {
? ? ? ? ? ? Node<K,V> f; int n, i, fh;
?? ??? ??? ?//1、判断 table 如果为空，就初始化，tabel是一个node数组，默认大小为16
? ? ? ? ? ? if (tab == null || (n = tab.length) == 0)
? ? ? ? ? ? ? ? tab = initTable();
?? ??? ??? ?//2、判断i位置是否为空，如果是就将 key和value封装成node放在i位置，通过cas(unsafe接口)实现?? ?
? ? ? ? ? ? else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
? ? ? ? ? ? ? ? if (casTabAt(tab, i, null,
? ? ? ? ? ? ? ? ? ? ? ? ? ? ?new Node<K,V>(hash, key, value, null)))
? ? ? ? ? ? ? ? ? ? break; ? ? ? ? ? ? ? ? ? // no lock when adding to empty bin
? ? ? ? ? ? }
?? ??? ??? ?//3、如果i位置不为空，并且i位置的节点的hash为-1，则说明table正在扩容中
? ? ? ? ? ? else if ((fh = f.hash) == MOVED)
? ? ? ? ? ? ? ? tab = helpTransfer(tab, f);
?? ??? ? ? ?//4、如果i位置不为空，并且节点的key的hash不为-1，则更新节点
? ? ? ? ? ? else {
? ? ? ? ? ? ? ? V oldVal = null;
? ? ? ? ? ? ? ? synchronized (f) {
? ? ? ? ? ? ? ? ? ? if (tabAt(tab, i) == f) {
?? ??? ??? ??? ??? ? ? ? 4.1这一段是插入链表的逻辑
? ? ? ? ? ? ? ? ? ? ? ? if (fh >= 0) {
? ? ? ? ? ? ? ? ? ? ? ? ? ? binCount = 1;
? ? ? ? ? ? ? ? ? ? ? ? ? ? for (Node<K,V> e = f;; ++binCount) {
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? K ek;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? if (e.hash == hash &&
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ((ek = e.key) == key ||
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(ek != null && key.equals(ek)))) {
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? oldVal = e.val;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? if (!onlyIfAbsent)
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? e.val = value;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? Node<K,V> pred = e;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? if ((e = e.next) == null) {
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? pred.next = new Node<K,V>(hash, key,
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? value, null);
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? ? ? }
?? ??? ??? ??? ??? ??? ? 4.2这一段时插入红黑树的逻辑
? ? ? ? ? ? ? ? ? ? ? ? else if (f instanceof TreeBin) {
? ? ? ? ? ? ? ? ? ? ? ? ? ? Node<K,V> p;
? ? ? ? ? ? ? ? ? ? ? ? ? ? binCount = 2;
? ? ? ? ? ? ? ? ? ? ? ? ? ? if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?value)) != null) {
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? oldVal = p.val;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? if (!onlyIfAbsent)
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? p.val = value;
? ? ? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? if (binCount != 0) {
?? ??? ??? ??? ? ? ?// ?当链表中的元素个数超过八个时自动转为红黑树
? ? ? ? ? ? ? ? ? ? if (binCount >= TREEIFY_THRESHOLD)
? ? ? ? ? ? ? ? ? ? ? ? treeifyBin(tab, i);
? ? ? ? ? ? ? ? ? ? if (oldVal != null)
? ? ? ? ? ? ? ? ? ? ? ? return oldVal;
? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? addCount(1L, binCount);
? ? ? ? return null;
? ? }