再談Java數據結構—分析底層實現與應用注意事項

在回顧js數據結構，寫《再談js對象數據結構底層實現原理-object array map set》系列的時候，在來整理下java的數據結構。

java把內存分兩種：一種是棧內存，另一種是堆內存

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

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

  不要在經常調用的方法中或在循環中創建對象。可以適當的使用hashtable，vector創建一組對象容器，然后從容器中去取那些對象，而不用每次new之后又丟棄。盡量避免在類的構造函數里創建、初始化大量的對象，防止在調用其自身類的構造器時造成不必要的內存資源浪費，尤其是大對象
  

包裝類

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

數組

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

靜態變量

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

那靜態變量與方法是在什么時候初始化的呢？對于兩種不同的類屬性，static屬性與instance屬性，初始化的時機是不同的。instance屬性在創建實例的時候初始化，static屬性在類加載，也就是第一次用到這個類的時候初始化，對于后來的實例的創建，不再次進行初始化。

盡量少用靜態變量，因為靜態變量是全局的，GC不會回收的。

數組Array和集合的區別

• 1 長度限制之別

  • 數組長度是固定不變的，

  • 集合的大小是可動態變化的

• 2 存儲類型之別

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

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

• 3 訪問元素方式

  • 數組是根據索引來獲取元素的

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

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

java集合是什么？

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

1. 長度限制之別：集合只能存放對象。比如你存一個 int 型數據 1放入集合中，其實它是自動轉換成 Integer 類后存入的，Java中每一種基本類型都有對應的引用類型。

2. 集合存放的是多個對象的引用，對象本身還是放在堆內存中。

3. 集合可以存放不同類型，不限數量的數據類型。

史上最全Java集合關系圖??，java集合關系UML類圖vsdx原圖。

Collection

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

? ? |--|----LinkedList?底層使用雙向鏈表實現，查詢慢，增刪快。效率高

? ? |--|----ArrayList?底層使用數組實現，查詢快，增刪慢。效率高。

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

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

? ? |--|----Vector?底層使用數組實現，線程安全，查詢快，增刪慢。效率低。

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

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

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

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

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

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

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

? ? |--|--TreeSet?基于 TreeMap 的 NavigableSet 實現。非同步，排序，元素唯一。?保持有序的set使用(使用元素的自然順序對元素進行排序，或者根據創建 set 時提供的 Comparator 進行排序(紅黑數維護次序)

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

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

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

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

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

java集合框架概括

只有Vector，HashTable是線程安全的

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

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

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

?

簡明圖

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?的元素上進行迭代的迭代器。
boolean?remove(Object?o)
????從此?collection?中移除指定元素的單個實例，如果存在的話（可選操作）。?
boolean?removeAll(Collection?c)
????移除此?collection?中那些也包含在指定?collection?中的所有元素（可選操作）。
boolean?retainAll(Collection?c)
????僅保留此?collection?中那些也包含在指定?collection?的元素（可選操作）。
int?size()
????返回此?collection?中的元素數。
Object[]?toArray()
????返回包含此?collection?中所有元素的數組。?T[]
????toArray(T[]?a)

List泛型接口

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

void?add(int?index,?E?element)
????在列表的指定位置插入指定元素（可選操作）。
boolean?addAll(int?index,?Collection?c)
????將指定?collection?中的所有元素都插入到列表中的指定位置（可選操作）。
int?indexOf(Object?o)
????返回此列表中第一次出現的指定元素的索引；如果此列表不包含該元素，則返回?-1。
int?lastIndexOf(Object?o)
????返回此列表中最后出現的指定元素的索引；如果列表不包含此元素，則返回?-1。
ListIterator?listIterator()
????返回此列表元素的列表迭代器（按適當順序）。
ListIterator?listIterator(int?index)
????返回列表中元素的列表迭代器（按適當順序），從列表的指定位置開始。
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常用數據結構?https://www.jianshu.com/p/fb4fb24ecc8f

java中的集合和數組?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常用數據結構及特點 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命中率最高的替換算法是什么？替換最近最少使用的塊算法