再談Java數(shù)據(jù)結(jié)構(gòu)—分析底層實(shí)現(xiàn)與應(yīng)用注意事項(xiàng)

在回顧js數(shù)據(jù)結(jié)構(gòu)，寫《再談js對象數(shù)據(jù)結(jié)構(gòu)底層實(shí)現(xiàn)原理-object array map set》系列的時(shí)候，在來整理下java的數(shù)據(jù)結(jié)構(gòu)。

java把內(nèi)存分兩種：一種是棧內(nèi)存，另一種是堆內(nèi)存

• 基本類型在棧區(qū)分配空間，java的基本數(shù)據(jù)類型共有8種，即int,short,long,byte,float,double,boolean,char(注意，并沒有String的基本類型 )。由于大小可知，生存期可知(這些字面值定義在某個(gè)程序塊里面，程序塊退出后，字段值就消失了)，出于追求速度的原因，就存在于棧中。

• 所有的對象都在堆(Heap)中分配空間，關(guān)鍵字new為每個(gè)對象申請內(nèi)存空間(基本類型除外)，對象的釋放是由垃圾回收機(jī)制決定和執(zhí)行的，這樣做確實(shí)簡化了程序員的工作。但同時(shí)，它也加重了JVM的工作。因?yàn)?，GC為了能夠正確釋放對象，GC必須監(jiān)控每一個(gè)對象的運(yùn)行狀態(tài)，包括對象的申請、引用、被引用、賦值等，GC都需要進(jìn)行監(jiān)控。

  不要在經(jīng)常調(diào)用的方法中或在循環(huán)中創(chuàng)建對象。可以適當(dāng)?shù)氖褂胔ashtable，vector創(chuàng)建一組對象容器，然后從容器中去取那些對象，而不用每次new之后又丟棄。盡量避免在類的構(gòu)造函數(shù)里創(chuàng)建、初始化大量的對象，防止在調(diào)用其自身類的構(gòu)造器時(shí)造成不必要的內(nèi)存資源浪費(fèi)，尤其是大對象
  

包裝類

基本類型都有對應(yīng)的包裝類：如int對應(yīng)Integer類，double對應(yīng)Double類等，基本類型的定義都是直接在棧中，如果用包裝類來創(chuàng)建對象，就和普通對象一樣了。例如：int i=0；i直接存儲在棧中。Integer i（i此時(shí)是對象）= new Integer(5)；這樣，i對象數(shù)據(jù)存儲在堆中，i的引用存儲在棧中，通過棧中的引用來操作對象。大量使用字符串處理，避免使用String，應(yīng)大量使用StringBuffer，因?yàn)镾tring被設(shè)計(jì)成不可變(immutable)類，所以它的所有對象都是不可變對象

數(shù)組

當(dāng)定義一個(gè)數(shù)組，int x[]；或int[] x；時(shí)，在棧內(nèi)存中創(chuàng)建一個(gè)數(shù)組引用，通過該引用（即數(shù)組名）來引用數(shù)組。x=new int[3]；將在堆內(nèi)存中分配3個(gè)保存 int型數(shù)據(jù)的空間，堆內(nèi)存的首地址放到棧內(nèi)存中，每個(gè)數(shù)組元素被初始化為0。

靜態(tài)變量

用static的修飾的變量和方法，實(shí)際上是指定了這些變量和方法在內(nèi)存中的”固定位置”－static storage，可以理解為所有實(shí)例對象共有的內(nèi)存空間。static變量有點(diǎn)類似于C中的全局變量的概念；靜態(tài)表示的是內(nèi)存的共享，就是它的每一個(gè)實(shí)例都指向同一個(gè)內(nèi)存地址。把static拿來，就是告訴JVM它是靜態(tài)的，它的引用（含間接引用）都是指向同一個(gè)位置，在那個(gè)地方，你把它改了，它就不會變成原樣，你把它清理了，它就不會回來了。

那靜態(tài)變量與方法是在什么時(shí)候初始化的呢？對于兩種不同的類屬性，static屬性與instance屬性，初始化的時(shí)機(jī)是不同的。instance屬性在創(chuàng)建實(shí)例的時(shí)候初始化，static屬性在類加載，也就是第一次用到這個(gè)類的時(shí)候初始化，對于后來的實(shí)例的創(chuàng)建，不再次進(jìn)行初始化。

盡量少用靜態(tài)變量，因?yàn)殪o態(tài)變量是全局的，GC不會回收的。

數(shù)組Array和集合的區(qū)別

• 1 長度限制之別

  • 數(shù)組長度是固定不變的，

  • 集合的大小是可動態(tài)變化的

• 2 存儲類型之別

  • 一個(gè)數(shù)組存儲的元素可以是基本類型，也可以是引用類型，且只能存儲同一種類型的元素

  • 一個(gè)集合存儲的元素只能是引用類型，但集合可以存儲不同類型的元素(但集合一般存儲同一種類型，可以用泛型加以控制)

• 3 訪問元素方式

  • 數(shù)組是根據(jù)索引來獲取元素的

  • 集合通常會提供一個(gè)迭代器來方便訪問元素

若程序時(shí)不知道究竟需要多少對象，需要在空間不足時(shí)自動擴(kuò)增容量，則需要使用容器類庫，array不適用。

java集合是什么？

Java集合類存放于 java.util 包中，是一個(gè)用來存放對象的容器。

1. 長度限制之別：集合只能存放對象。比如你存一個(gè) int 型數(shù)據(jù) 1放入集合中，其實(shí)它是自動轉(zhuǎn)換成 Integer 類后存入的，Java中每一種基本類型都有對應(yīng)的引用類型。

2. 集合存放的是多個(gè)對象的引用，對象本身還是放在堆內(nèi)存中。

3. 集合可以存放不同類型，不限數(shù)量的數(shù)據(jù)類型。

史上最全Java集合關(guān)系圖??，java集合關(guān)系UML類圖vsdx原圖。

Collection

? ? |-----List??有序，可重復(fù)(存儲順序和取出順序一致)

? ? |--|----LinkedList?底層使用雙向鏈表實(shí)現(xiàn)，查詢慢，增刪快。效率高

? ? |--|----ArrayList?底層使用數(shù)組實(shí)現(xiàn)，查詢快，增刪慢。效率高。

? ? |? |? ? ? ? 每次容量不足時(shí)，自增長度的一半，如下源碼可知

? ? |? |? ? ? ? ? int newCapacity = oldCapacity + (oldCapacity >> 1);

? ? |--|----Vector?底層使用數(shù)組實(shí)現(xiàn)，線程安全，查詢快，增刪慢。效率低。

? ? |? |? ? ? ? 每次容量不足時(shí)，默認(rèn)自增長度的一倍（如果不指定增量的話），如下源碼可知

? ? |? |? ? ? ? ? int newCapacity = oldCapacity + ((capacityIncrement > 0) ?

? ? |? |? ? ? ? ? ? ? ? ? ? ? ? ? ? capacityIncrement : oldCapacity);

? ? |-----Set? ?元素唯一(最多包含一個(gè) null 元素)，只能通過游標(biāo)來取值，線程不安全

? ? ? ? ? ?HashSet比TreeSet高效(尤其是查詢、添加),LinkedHashSet比hash插入、刪除慢，但是遍歷快。

? ? |--|--HashSet?底層是由HashMap實(shí)現(xiàn)的，線程非安全，通過對象的hashCode方法與equals方法來保證插入元素的唯一性，無序(存儲順序和取出順序不一致)?

? ? |--|--|--LinkedHashSet?底層數(shù)據(jù)結(jié)構(gòu)由哈希表和鏈表組成。哈希表保證元素的唯一性，鏈表保證元素有序。(存儲和取出是一致)

? ? |--|--TreeSet?基于 TreeMap 的 NavigableSet 實(shí)現(xiàn)。非同步，排序，元素唯一。?保持有序的set使用(使用元素的自然順序?qū)υ剡M(jìn)行排序，或者根據(jù)創(chuàng)建 set 時(shí)提供的 Comparator 進(jìn)行排序(紅黑數(shù)維護(hù)次序)

Map?是鍵值對集合,key 不允許重復(fù)，value 可以

? ? |-----HashMap?基于鏈表和紅黑樹:hashMap用hash表實(shí)現(xiàn)的Map,就是利用對象的hashcode(hashcode()是Object的方法)進(jìn)行快速散列查找。Null可以做主鍵，但只能有一個(gè)

? ? |-----TreeMap?基于紅黑樹

? ? |-----LinkedHashMap?HashMap+LinkedList

? ? |-----HashTable?線程安全，不允許有null值的存在

java集合框架概括

只有Vector，HashTable是線程安全的

ArrayList，LinkedList，HashSet，TreeSet，HashMap，TreeMap都不是線程安全的。

如果沒有必要,推薦代碼只同List,Map接口打交道.

HashMap的輸出順序是隨機(jī)的，TreeMap中的條目是按鍵值的升序排列的，LinkedHashMap是按元素最后一次被訪問的時(shí)間從早到晚排序的

?

簡明圖

Collection||Set泛型接口方法摘要

boolean?add(E?e)
????確保此?collection?包含指定的元素（可選操作）。
boolean?addAll(Collection?c)
????將指定?collection?中的所有元素都添加到此?collection?中（可選操作）。
void?clear()
????移除此?collection?中的所有元素（可選操作）。
boolean?contains(Object?o)
????如果此?collection?包含指定的元素，則返回?true。
boolean?containsAll(Collection?c)
????如果此?collection?包含指定?collection?中的所有元素，則返回?true。
boolean?equals(Object?o)
????比較此?collection?與指定對象是否相等。
int?hashCode()
????返回此?collection?的哈希碼值。
boolean?isEmpty()
????如果此?collection?不包含元素，則返回?true。
Iterator?iterator()
????返回在此?collection?的元素上進(jìn)行迭代的迭代器。
boolean?remove(Object?o)
????從此?collection?中移除指定元素的單個(gè)實(shí)例，如果存在的話（可選操作）。?
boolean?removeAll(Collection?c)
????移除此?collection?中那些也包含在指定?collection?中的所有元素（可選操作）。
boolean?retainAll(Collection?c)
????僅保留此?collection?中那些也包含在指定?collection?的元素（可選操作）。
int?size()
????返回此?collection?中的元素?cái)?shù)。
Object[]?toArray()
????返回包含此?collection?中所有元素的數(shù)組。?T[]
????toArray(T[]?a)

List泛型接口

特有方法(相對于Collection—繼承自Collection)

void?add(int?index,?E?element)
????在列表的指定位置插入指定元素（可選操作）。
boolean?addAll(int?index,?Collection?c)
????將指定?collection?中的所有元素都插入到列表中的指定位置（可選操作）。
int?indexOf(Object?o)
????返回此列表中第一次出現(xiàn)的指定元素的索引；如果此列表不包含該元素，則返回?-1。
int?lastIndexOf(Object?o)
????返回此列表中最后出現(xiàn)的指定元素的索引；如果列表不包含此元素，則返回?-1。
ListIterator?listIterator()
????返回此列表元素的列表迭代器（按適當(dāng)順序）。
ListIterator?listIterator(int?index)
????返回列表中元素的列表迭代器（按適當(dāng)順序），從列表的指定位置開始。
E?get(int?index)
????返回列表中指定位置的元素。
E?remove(int?index)
????移除列表中指定位置的元素（可選操作）。
E?set(int?index,?E?element)
????用指定元素替換列表中指定位置的元素（可選操作）。
List?subList(int?fromIndex,?int?toIndex)
????返回列表中指定的?fromIndex（包括?）和?toIndex（不包括）之間的部分視圖。

原文鏈接：https://www.zhoulujun.cn/html/java/javaBase/159.html 排版效果可能更好，本文若有不妥之處，請留言告知，拜謝！

參考文章：

java 集合詳解?https://www.cnblogs.com/ysocean/p/6555373.html

java集合詳解與基本使用方法?https://blog.csdn.net/qq_34232889/article/details/79997471

圖解Java常用數(shù)據(jù)結(jié)構(gòu)?https://www.jianshu.com/p/fb4fb24ecc8f

java中的集合和數(shù)組?https://www.cnblogs.com/summers/p/4094260.html

集合的線程安全性?https://www.cnblogs.com/wuchaodzxx/p/6007970.html

Set與線程安全?https://blog.csdn.net/l153097889/article/details/77891250

java常用數(shù)據(jù)結(jié)構(gòu)及特點(diǎn) https://blog.csdn.net/hujiangtaochn/article/details/84136432

Java集合框架之圖解 https://www.cnblogs.com/SamSarah/p/4893217.html

java.util包中集合詳解?https://www.jianshu.com/p/4bb01e139cda

使Cache命中率最高的替換算法是什么？替換最近最少使用的塊算法