一岖研、java集合類的整體繼承關(guān)系
可以看出java集合的頂層接口分兩類：Collection卿操，Map
兩個(gè)工具類：Collections警检，Arrays
Collection接口中定義了15種方法：
1.8之后還新增了
Stream<E> stream()
Stream<E> parallelStream()
stream與parallelStream可以理解為一種高級(jí)版的Iterator孙援『τ伲基于stream的函數(shù)式變成可以讓程序變的更簡潔。
下面是一個(gè)獲取list集合中字符串長度大于4的程序拓售，分別比較了三種方式普通的窥摄，基于stream及parallelStream的運(yùn)行比較
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你爸的加拉水電費(fèi)"});
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運(yùn)行時(shí)間" + (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運(yùn)行時(shí)間：" + (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速度相當(dāng)，parallelStream速度要比
Map接口與Collection接口地位相同础淤，都是根接口崭放，Map中提供了3個(gè)角度來分析Map
Set<K> keySet():所有key的集合
Collections<V> values()：所有value的集合
Set<Map.Entry<k,v>> entrySet()：key和value的集合，
需要遍歷map集合時(shí)建議使用第三種方式鸽凶，因?yàn)檫@種方式是構(gòu)造map集合的方式币砂，最節(jié)省時(shí)間，第一種方式獲取key玻侥，value需要遍歷2次决摧。第二種方式只能獲取value的值，它的速度與entry的速度應(yīng)該差不多凑兰。
阿里編程規(guī)范中遍歷Map的key-Value對(duì)時(shí)使用EntrySet()的方式
二掌桩、Set、List姑食、Map的幾種常用的實(shí)現(xiàn)類及注意事項(xiàng)
1波岛、List接口是一個(gè)元素有序的、可以重復(fù)音半、可以為 null 的集合则拷，常用的實(shí)現(xiàn)類，ArrayList曹鸠，LinkedList這兩個(gè)實(shí)現(xiàn)類的底層的存儲(chǔ)結(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){
/*檢查下標(biāo)是否越界，代碼不在拷貝*/
//若需要擴(kuò)容永票，則增大底層數(shù)組的長度
ensureCapacity(size + 1);
//給index下標(biāo)之后的元素（包括當(dāng)前元素）的下標(biāo)加1，空出index位置（將elementData從index起始痴鳄，復(fù)制到index+1的職位
System.arraycopy(elementData,index,elementData,index + 1,size - index);
//賦值index位置元素
elementData[index] = element;
//列表的長度+1
size++;
}
注：這里ArrayList會(huì)進(jìn)行擴(kuò)容判斷柏卤，如果需要擴(kuò)容就會(huì)以當(dāng)前容量的1.5倍進(jìn)行擴(kuò)容。在用淺拷貝的方式對(duì)數(shù)組元素進(jìn)行后移抖拴。
也是由于這個(gè)原因燎字，阿里的開發(fā)手冊(cè)中有了下面這條建議腥椒。
public E remove(int index){
//下標(biāo)校驗(yàn)
RangeCheck(index);
//修改計(jì)數(shù)器+1
modCount++;
//記錄要?jiǎng)h除的元素
E oldValue = (E)elementData(index);
//有多少個(gè)元素向前移動(dòng)
int numMoved = size - index - 1;
if(numMoved > 0)
//index后的元素向前移動(dòng)一位
System.arraycopy(elementData,index + 1,elementData,index,numMoved);
//列表長度減1，并且最后一位設(shè)為null
elementData[--size] = null;
//返回刪除的值
return oldValue;
}
這是arrayList的刪除操作候衍，同樣需要對(duì)數(shù)組元素進(jìn)行部分移動(dòng)笼蛛。
與之對(duì)應(yīng)的LinkedList的操作如下：
public void add(int index,E element){
addBefore(element,(index==size?header:entry(index)));
}
private Entry<E> addBefore(E e,Entry<E> entry){
//組裝一個(gè)新的節(jié)點(diǎn)，previous指向原節(jié)點(diǎn)的前節(jié)點(diǎn)蛉鹿，next指向原節(jié)點(diǎn)
Entry<E> newEntry = new Entry<E>(e,entry,entry.previous);
//前節(jié)點(diǎn)的next指向自己
newEntry.previous.next = newEntry;
//后節(jié)點(diǎn)的previous指向自己
newEntry.next.previous = newEntry;
//長度+1
size++;
//修改計(jì)數(shù)器+1
modCount ++;
return newEntry;
}
private E remove(Entry<E> e){
//取得原始值
E result = e.element;
//前節(jié)點(diǎn)next指向當(dāng)前節(jié)點(diǎn)的next
e.previous.next = e.next;
//后節(jié)點(diǎn)的previouse指向當(dāng)前節(jié)點(diǎn)的previous
e.next.previous = e.previous;
//置空當(dāng)前節(jié)點(diǎn)的next和previous
e.next = e.previous= null;
//當(dāng)前元素置空
e.element = null;
//列表長度減1
size --;
//修改計(jì)數(shù)器+1
modCount++;
return result;
}
結(jié)論：在數(shù)據(jù)需要進(jìn)行大量刪除及新增的時(shí)候滨砍，LinkedList的速度要比ArrayList的快很多建議使用ArrayList，在數(shù)據(jù)查詢及修改指定元素值時(shí)妖异，ArrayList速度要比LinkedList速度快惋戏。
注意：在使用ArrayList的sublist()方法時(shí)需要注意，不能將sublist()集合強(qiáng)轉(zhuǎn)成ArrayList否則會(huì)報(bào)java.util.RandomAccessSubList cannot be cast to java.util.ArrayList異常他膳，因?yàn)镾ublist這個(gè)內(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集合舔亭，它的實(shí)現(xiàn)類有hashSet及LinkedHashSet，當(dāng)需要對(duì)元素進(jìn)行去重存儲(chǔ)時(shí)散罕，可以選擇set集合分歇。
3、hashMap:Node<K,V> table, Set<Map.Entry<K,V>> entrySet
傳統(tǒng)hashMap的缺點(diǎn)：它的存儲(chǔ)結(jié)構(gòu)是數(shù)組+鏈表的形式欧漱，當(dāng)大量的元素hash值相同時(shí)會(huì)被放入同一個(gè)桶中职抡，此時(shí)的就相當(dāng)于一個(gè)單鏈表查找時(shí)間復(fù)雜度為o(n).
java1.8之前hashMap的存儲(chǔ)使用的是數(shù)組+鏈表，即使哈希函數(shù)取得再好误甚，也很難達(dá)到元素百分百均勻分布缚甩。在1.8之后采用紅黑樹來優(yōu)化這個(gè)問題查找時(shí)間復(fù)雜度為（Ologn），在1.8中hashmap的存儲(chǔ)的具體過程在鏈表的長度小于8時(shí)任然采用之前的數(shù)據(jù)接口當(dāng)長度大于8是采用紅黑樹結(jié)構(gòu)窑邦。紅黑樹本質(zhì)上是一種二叉查找樹擅威，但它在二叉查找樹的基礎(chǔ)上額外添加了一個(gè)標(biāo)記（顏色），同時(shí)具有一定的規(guī)則冈钦。這些規(guī)則可以保證紅黑樹結(jié)構(gòu)在插入郊丛、刪除、查找時(shí)的最壞時(shí)間復(fù)雜度為 O(logn)瞧筛。（紅黑樹的詳細(xì)介紹https://blog.csdn.net/u011240877/article/details/53329023）
原先的鏈表節(jié)點(diǎn)：
static class Node<K,V> implements Map.Entry<K,V> {
//哈希值厉熟，就是位置
final int hash;
//鍵
final K key;
//值
V value;
//指向下一個(gè)幾點(diǎn)的指針
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;
}
加入紅黑樹之后的整個(gè)hashMap的put操作
3、被忽略的Set與Map的聯(lián)系：
Set代表的是一種集合元素?zé)o序较幌，集合元素不可重復(fù)的集合揍瑟，Map則代表一種由多個(gè)Key-Value對(duì)組成的集合，Map集合類似于傳統(tǒng)的關(guān)聯(lián)數(shù)組乍炉。表面上看绢片，Map和Set毫無關(guān)聯(lián)滤馍，但其實(shí)Map和Set之間有莫大的關(guān)聯(lián)，可以說底循，Map是Set的擴(kuò)展巢株。
Set及Map的繼承體系
這張圖可以明顯地看出Set與Map有著極其相似的繼承體系。
實(shí)際上
Map的key是無序的不能重復(fù)的此叠，所以Map的所有key的集合實(shí)際上就是一個(gè)Set集合纯续，事實(shí)上Map中的keySet方法也是這樣實(shí)現(xiàn)的
從Set到Map随珠，如果將（key-value）看做一個(gè)整體灭袁，將Entry放入到Set中，實(shí)際上Set就轉(zhuǎn)化成了Map集合窗看。
利用Set實(shí)現(xiàn)一個(gè)Map集合就變得很簡單了
1茸歧、定義一個(gè)實(shí)體類存儲(chǔ)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實(shí)現(xiàn)一個(gè)hashMap2
public class HashMap2<K,V> extends HashSet<SimpleEntry<K,V>> {
@Override
public void clear() {
super.clear();
}
//判斷是否包含某個(gè)key
public boolean containsKey(K key){
return super.contains(new SimpleEntry<K, V>(key,null));
}
//判斷是否包含某個(gè)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;
}
//存放一個(gè)Map的key-value對(duì)放入該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對(duì)
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中實(shí)現(xiàn)類是否安全显沈，能否鍵值為空的一個(gè)比較
具體的線程安全的實(shí)現(xiàn)細(xì)節(jié)软瞎，有興趣的可以自己看一下，這里沒有做總結(jié)
