java集合框架总结

queue接口和Deque接口

public LinkedList extends AbstractSequentialList<E>
     implements List<E>, Deque<E>, Cloneable, java.io.Serializable


public interface Queue<E> extends Collection<E> {
    //添加尾部
    boolean add(E e);//满时抛异常
    boolean offer(E e);//false
    //删除头部
    E remove();//NoSuchElementException
    E poll(); // null
    //查看头部，不改变队列
    E element();//NoSuchElementException
    E peek(); // null 
}

//双端队列
public interface Deque<E> extends Queue<E> {
    void addFirst(E e);
    void addLast(E e);
    E getFirst();
    E getLast();
    boolean offerFirst(E e);
    boolean offerLast(E e);
    E peekFirst();
    E peekLast();
    E pollFirst();
    E pollLast();
    E removeFirst();
    E removeLast();
    Iterator<E> descendingIterator();//反向遍历
｝

LinkedList和ArrayList区别

    ArrayList内部是数组，元素在内存是连续存放的，但LinkedList不是。LinkedList直译就是链表，确切的说，它的内部实现是双向链表。
    LinkedList不可以随机访问，但是插入和删除效率高，可以用作 队列，双端队列，栈等数据结构。

HashMap 和 HashTable 区别

更多详情请看这里

http://www.importnew.com/24822.html

1. HashTable产生于JDK 1.1，而HashMap产生于JDK 1.2
2. 虽然都实现了Map、Cloneable、Serializable三个接口。但是HashMap继承自抽象类AbstractMap，而HashTable继承自抽象类Dictionary。其中Dictionary类是一个已经被废弃的类
3. HashMap是支持null键和null值的，而HashTable在遇到null时，会抛出NullPointerException异常。因为HashMap在实现时对null做了特殊处理，将null的hashCode值定为了0，从而将其存放在哈希表的第0个bucket。
4. 初始容量和扩容计算不同：HashTable初始为11，扩容为2n+1，会尽量使用素数和奇数，简单的哈希取模会更加均匀。而HashMap初始为1<<4=64，每次扩充为2n，可以直接使用位运算，提升效率。
5. HashTable是线程安全的，因为他使用了synchronized描述符

## 相同点
HashMap/HashTable内部用Entry数组实现哈希表
HashMap和HashTable在计算hash时都用到了一个叫hashSeed的变量，这是因为映射到同一个hash桶内的Entry对象，是以链表的形式存在的，而链表的查询效率比较低，所以HashMap/HashTable的效率对哈希冲突非常敏感，所以可以额外开启一个可选hash（hashSeed），从而减少哈希冲突。因为这是两个类相同的一点，所以本文不再展开了，感兴趣的看这里。事实上，这个优化在JDK 1.8中已经去掉了，因为JDK 1.8中，映射到同一个哈希桶（数组位置）的Entry对象，使用了红黑树来存储，从而大大加速了其查找效率。

TreeMap

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable{}
TreeMap内部是用红黑树实现的，红黑树是一种大致平衡的排序二叉树。
## 封装为线程安全
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));


## 源码
private final Comparator<? super K> comparator;
private transient Entry<K,V> root = null;
private transient int size = 0;
static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left = null;
    Entry<K,V> right = null;
    Entry<K,V> parent;
    boolean color = BLACK;

    /**
     * Make a new cell with given key, value, and parent, and with
     * {@code null} child links, and BLACK color.
     */
    Entry(K key, V value, Entry<K,V> parent) {
        this.key = key;
        this.value = value;
        this.parent = parent;
    }
}    

## TreeMap是按键而不是按值有序

## 逆序且忽略大小写
Map<String, String> map  = new TreeMap<>(
        Collections.reverseOrder(String.CASE_INSENSITIVE_ORDER));
        
Map<String, String> map  = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
map.put("T", "tree");
map.put("t", "try");

for(Entry<String,String> kv : map.entrySet()){
    System.out.print(kv.getKey()+"="+kv.getValue()+" ");
}
>> 输出 T=try

## NavigableMap接口（临近entry）
Map.Entry<K,V> floorEntry(K key);
Map.Entry<K,V> lowerEntry(K key);
Map.Entry<K,V> ceilingEntry(K key);
Map.Entry<K,V> higherEntry(K key);

higherEntry
ceilingEntry
Map.get(key)
floorEntry
lowerEntry

线程集合类

ConcurrentHashMap

源码赏析

### 根据下标找元素（如果下表在前半部分，则从头部，反之尾部）
Node<E> node(int index) {
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

附录集合框架图

image.png