Java常用数据结构与集合

数据结构

数组：

内存地址连续
检索效率高(可以通过下标访问成员)
增删操作效率低(保证数据越界的问题,需动态扩容)
长度固定，扩容的需要新的数组复制或者Arrays类的copyOf方法

链表

内存地址不连续
查询快删除慢，因为需要移动指针
又分双向链表和单向链表，单向链表有下一个元素的指针，双向有指向上一个，下一个两个指针

双向链表的结构

    static final class Node {
       // 前一个节点
        volatile Node prev;
        // 后一个节点
        volatile Node next;
		// 链表节点存储的具体数据
        volatile Thread thread;
    }

队列

尾插头删
管状结构，先进先出

栈

尾插尾删
杯状结构，先进后出

集合框架

HashMap

底层是数组+链表的结构，hash值相同的会形成链表，jdk1.8之后当相同hash值超过8个之后会变为红黑树
并不是线程安全的，如果想要一个安全的collections.synchronizedMap返回一个线程安全的。或者使用concurrentHashMap
允许一个key为null，多个value为null

HashTable

是一个古老的Map实现类，它不允许使用null作为键和值。Hashtable的性能略低于HashMap，多线程安全。

LinkedHashMap

底层是数组+链表+双向链表，根据添加顺序排序;线程不安全。
数组和链表的作用和HashMap的作用一样，双向链表是来记录键值对的插入顺序或访问顺序

TreeMap

底层是红黑树，默认是根据键值字典排序就是无序，也可以自己排序。compareable接口或者Comparator
线程安全。

ConcurrentHashMap

ConcurrentHashMap底层采用分段的数组+链表实现，线程安全。通过分段锁的方式保证线程安全，默认性能提高16倍。超过75%时扩容，仅扩容当前分段数组
1.7的实现是使用Segment数组，每个Segment就是一个分段锁，对应了一个HashEntry数组。每个HashEntry对应着一个node数组。get（）时需要计算两次Hash,第一次拿到Segment,第二次拿到对应的hashEntry。1.8后只需要一次了。1.8之后去掉了Sement分段锁，直接以HashEntry为锁，这样减少了锁的粒度，也减少了冲突的概率。除了去掉Segment外，把node数组更换为红黑树，空间复杂度也从O(n)变为O(logn)