一、java集合類的整體繼承關(guān)系
可以看出java集合的頂層接口分兩類：Collection，Map
兩個工具類：Collections，Arrays
Collection接口中定義了15種方法：
1.8之后還新增了
Stream<E> stream()
Stream<E> parallelStream()
stream與parallelStream可以理解為一種高級版的Iterator?；趕tream的函數(shù)式變成可以讓程序變的更簡潔。
下面是一個獲取list集合中字符串長度大于4的程序，分別比較了三種方式普通的，基于stream及parallelStream的運行比較
public static void main(String[] args){
List<String> handles = new ArrayList<>();
for (int i= 0;i<2000000;i++){
List<String> lists = Arrays.asList(new String[]{"abcdsd","bcd","efgdddd","你是誰啊啊啊啊啊","b你爸的加拉水電費"});
handles.addAll(lists);
}
long start0 = System.currentTimeMillis();
List<String> result0 = new ArrayList<>();
for (int i=0; i<handles.size(); i++){
if (handles.get(i).length() > 4){
result0.add(handles.get(i).substring(1));
}
}
long end0 = System.currentTimeMillis();
System.out.println("noStream運行時間" + (end0-start0)); //2890
long start1 = System.currentTimeMillis();
List<String> result = handles.stream().filter(e->e.length() > 4).map(e->e.substring(1)).collect(toList());
long end1 = System.currentTimeMillis();
System.out.println("stream運行時間：" + (end1-start1));//2899
long start2 = System.currentTimeMillis();
handles.parallelStream().filter(e->e.length() > 4).map(e->e.substring(1)).collect(toList());
long end2 = System.currentTimeMillis();
System.out.println("parallelStream" + (end2-start2));//2500
}
nostream與stream速度相當，parallelStream速度要比
Map接口與Collection接口地位相同，都是根接口，Map中提供了3個角度來分析Map
Set<K> keySet():所有key的集合
Collections<V> values()：所有value的集合
Set<Map.Entry<k,v>> entrySet()：key和value的集合，
需要遍歷map集合時建議使用第三種方式，因為這種方式是構(gòu)造map集合的方式，最節(jié)省時間，第一種方式獲取key，value需要遍歷2次。第二種方式只能獲取value的值，它的速度與entry的速度應該差不多。
阿里編程規(guī)范中遍歷Map的key-Value對時使用EntrySet()的方式
二、Set、List、Map的幾種常用的實現(xiàn)類及注意事項
1、List接口是一個元素有序的、可以重復、可以為 null 的集合，常用的實現(xiàn)類，ArrayList，LinkedList這兩個實現(xiàn)類的底層的存儲結(jié)構(gòu)，ArrayList采用的是數(shù)組結(jié)構(gòu)，
LinkedList采用的是雙向鏈表結(jié)構(gòu)。
下面是ArrayList及LinkedList的add、set、及remove操作
1、ArrayList
public void add(int index,E element){
/*檢查下標是否越界，代碼不在拷貝*/
//若需要擴容，則增大底層數(shù)組的長度
ensureCapacity(size + 1);
//給index下標之后的元素（包括當前元素）的下標加1，空出index位置（將elementData從index起始，復制到index+1的職位
System.arraycopy(elementData,index,elementData,index + 1,size - index);
//賦值index位置元素
elementData[index] = element;
//列表的長度+1
size++;
}
注：這里ArrayList會進行擴容判斷，如果需要擴容就會以當前容量的1.5倍進行擴容。在用淺拷貝的方式對數(shù)組元素進行后移。
也是由于這個原因，阿里的開發(fā)手冊中有了下面這條建議。
public E remove(int index){
//下標校驗
RangeCheck(index);
//修改計數(shù)器+1
modCount++;
//記錄要刪除的元素
E oldValue = (E)elementData(index);
//有多少個元素向前移動
int numMoved = size - index - 1;
if(numMoved > 0)
//index后的元素向前移動一位
System.arraycopy(elementData,index + 1,elementData,index,numMoved);
//列表長度減1，并且最后一位設為null
elementData[--size] = null;
//返回刪除的值
return oldValue;
}
這是arrayList的刪除操作，同樣需要對數(shù)組元素進行部分移動。
與之對應的LinkedList的操作如下：
public void add(int index,E element){
addBefore(element,(index==size?header:entry(index)));
}
private Entry<E> addBefore(E e,Entry<E> entry){
//組裝一個新的節(jié)點，previous指向原節(jié)點的前節(jié)點，next指向原節(jié)點
Entry<E> newEntry = new Entry<E>(e,entry,entry.previous);
//前節(jié)點的next指向自己
newEntry.previous.next = newEntry;
//后節(jié)點的previous指向自己
newEntry.next.previous = newEntry;
//長度+1
size++;
//修改計數(shù)器+1
modCount ++;
return newEntry;
}
private E remove(Entry<E> e){
//取得原始值
E result = e.element;
//前節(jié)點next指向當前節(jié)點的next
e.previous.next = e.next;
//后節(jié)點的previouse指向當前節(jié)點的previous
e.next.previous = e.previous;
//置空當前節(jié)點的next和previous
e.next = e.previous= null;
//當前元素置空
e.element = null;
//列表長度減1
size --;
//修改計數(shù)器+1
modCount++;
return result;
}
結(jié)論：在數(shù)據(jù)需要進行大量刪除及新增的時候，LinkedList的速度要比ArrayList的快很多建議使用ArrayList，在數(shù)據(jù)查詢及修改指定元素值時，ArrayList速度要比LinkedList速度快。
注意：在使用ArrayList的sublist()方法時需要注意，不能將sublist()集合強轉(zhuǎn)成ArrayList否則會報java.util.RandomAccessSubList cannot be cast to java.util.ArrayList異常，因為Sublist這個內(nèi)部類沒有繼承ArrayList
public void test(){
List<String> items = Arrays.asList(new String[]{"a","b","c"});
List<String> results = new ArrayList<>();
results.addAll(items);
List<String> sublist = results.subList(0,3);
sublist.remove(1);
for (String str : results){
System.out.println(str);
}
}
最后輸出的結(jié)果是a,c,因此asList()方法并沒有創(chuàng)建新的集合，還是引用的原來的內(nèi)存。
2、set是一種無序不可重值可以為null集合，它的實現(xiàn)類有hashSet及LinkedHashSet，當需要對元素進行去重存儲時，可以選擇set集合。
3、hashMap:Node<K,V> table, Set<Map.Entry<K,V>> entrySet
傳統(tǒng)hashMap的缺點：它的存儲結(jié)構(gòu)是數(shù)組+鏈表的形式，當大量的元素hash值相同時會被放入同一個桶中，此時的就相當于一個單鏈表查找時間復雜度為o(n).
java1.8之前hashMap的存儲使用的是數(shù)組+鏈表，即使哈希函數(shù)取得再好，也很難達到元素百分百均勻分布。在1.8之后采用紅黑樹來優(yōu)化這個問題查找時間復雜度為（Ologn），在1.8中hashmap的存儲的具體過程在鏈表的長度小于8時任然采用之前的數(shù)據(jù)接口當長度大于8是采用紅黑樹結(jié)構(gòu)。紅黑樹本質(zhì)上是一種二叉查找樹，但它在二叉查找樹的基礎上額外添加了一個標記（顏色），同時具有一定的規(guī)則。這些規(guī)則可以保證紅黑樹結(jié)構(gòu)在插入、刪除、查找時的最壞時間復雜度為 O(logn)。（紅黑樹的詳細介紹https://blog.csdn.net/u011240877/article/details/53329023）
原先的鏈表節(jié)點：
static class Node<K,V> implements Map.Entry<K,V> {
//哈希值，就是位置
final int hash;
//鍵
final K key;
//值
V value;
//指向下一個幾點的指針
Node<K,V> next;
//...
}
jdk1.8中新增的紅黑樹結(jié)構(gòu)
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
}
加入紅黑樹之后的整個hashMap的put操作
3、被忽略的Set與Map的聯(lián)系：
Set代表的是一種集合元素無序，集合元素不可重復的集合，Map則代表一種由多個Key-Value對組成的集合，Map集合類似于傳統(tǒng)的關(guān)聯(lián)數(shù)組。表面上看，Map和Set毫無關(guān)聯(lián)，但其實Map和Set之間有莫大的關(guān)聯(lián)，可以說，Map是Set的擴展。
Set及Map的繼承體系
這張圖可以明顯地看出Set與Map有著極其相似的繼承體系。
實際上
Map的key是無序的不能重復的，所以Map的所有key的集合實際上就是一個Set集合，事實上Map中的keySet方法也是這樣實現(xiàn)的
從Set到Map，如果將（key-value）看做一個整體，將Entry放入到Set中，實際上Set就轉(zhuǎn)化成了Map集合。
利用Set實現(xiàn)一個Map集合就變得很簡單了
1、定義一個實體類存儲k-v
public class SimpleEntry<K,V> implements Map.Entry<K,V>,Serializable {
private K key;
private V value;
public SimpleEntry(K key,V value){
this.key = key;
this.value = value;
}
public SimpleEntry(Map.Entry<? extends K,? extends V> entry){
this.key = entry.getKey();
this.value = entry.getValue();
}
@Override
public K getKey() {
return key;
}
@Override
public V getValue() {
return value;
}
@Override
public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}
public boolean equals(Object object){
if(object == this){
return true;
}
if(object.getClass() == SimpleEntry.class){
SimpleEntry se = (SimpleEntry) object;
return se.getKey().equals(getKey());
}
return false;
}
public int hashCode(){
return key == null?0:key.hashCode();
}
@Override
public String toString() {
return key+"="+value;
}
}
2、繼承hashSet實現(xiàn)一個hashMap2
public class HashMap2<K,V> extends HashSet<SimpleEntry<K,V>> {
@Override
public void clear() {
super.clear();
}
//判斷是否包含某個key
public boolean containsKey(K key){
return super.contains(new SimpleEntry<K, V>(key,null));
}
//判斷是否包含某個value
public boolean containsValue(V value){
for(SimpleEntry<K,V> se :this){
if(se.getValue().equals(value)){
return true;
}
}
return false;
}
//根據(jù)Key取出Value
public V get(K key){
for(SimpleEntry<K,V> se:this){
if(se.getKey().equals(key)){
return se.getValue();
}
}
return null;
}
//存放入該Map中
public V put(K key,V value){
add(new SimpleEntry<K, V>(key,value));
return value;
}
//存放一個Map的key-value對放入該Map中
public void putAll(Map<? extends K,? extends V> map){
for(K key:map.keySet()){
add(new SimpleEntry<K, V>(key,map.get(key)));
}
}
//根據(jù)指定key刪除指定key-value對
public V removeEntry(K key){
for(Iterator<SimpleEntry<K,V>> it = this.iterator();it.hasNext();){
SimpleEntry<K,V> en = it.next();
if(en.getKey().equals(key)){
V v = en.getValue();
it.remove();
return v;
}
}
return null;
}
public int size(){
return super.size();
}
}
最后這是Map中實現(xiàn)類是否安全，能否鍵值為空的一個比較
具體的線程安全的實現(xiàn)細節(jié)，有興趣的可以自己看一下，這里沒有做總結(jié)
