java面試——資料結構

常見資料結構有：java面試——資料結構、Hashtable、 Concurrentjava面試——資料結構。

（相關影片分享：java教學影片）

下面我們分別來介紹：

java面試——資料結構

• 底層實作：java面試——資料結構底層整體結構是一個數組，數組中的每個元素又是一個鍊錶。每次新增一個物件（put）時會產生一個鍊錶物件（Object型別），Map中的每個Entry就是陣列中的一個元素（Map.Entry就是一個<key></key>） ，它具有由當前元素指向下一個元素的引用，這就構成了鍊錶。
• 儲存原理：當HsahMap新增元素的時候，先計算Key物件的Hash值，得到陣列下標，如果陣列該位置為空則插入，否則遍歷這個位置鍊錶。當某個節點Key物件和Node物件均和新元素的equals時，用新元素的Value物件取代該節點的Value對象，否則插入新節點。 （注意：JDK 8之後加入了紅黑樹）

java面試——資料結構長度為2的n次方是為了讓length-1的二進位值所有位全為1，這種情況下，hash值與(table.length - 1)進行&運算計算index時，其結果就等同於hashcode後幾位的值，此時只要輸入的hashcode本身分佈均勻，Hash演算法的結果就是均勻的。所以，java面試——資料結構的預設長度為16是為了降低hash碰撞的幾率，同時也是適合的大小。

Hashtable

#比較點	java面試——資料結構	Hashtable
實作原理	見上小節	和java面試——資料結構的實作原理幾乎一樣
Key和Value	允許Key和Value為null	不允許Key和Value為null
擴容策略	2倍擴容oldThr	2倍1擴容(oldCapacity
#安全性	執行緒不安全	執行緒安全性

#

Hashtable線程安全的策略實現代價很大，get/put所有相關操作都是synchronized的，在競爭激烈的並發場景中性能非常差。

Concurrentjava面試——資料結構

Concurrentjava面試——資料結構是Java並發套件中提供的一個線程安全且高效的java面試——資料結構實現，它採用了非常精妙的分段鎖定策略， Concurrentjava面試——資料結構的主幹是Segment數組。 Segment繼承自ReentrantLock，是一種可重入鎖。每個Segment都是一個子哈希表，Segment裡維護了一個HashEntry數組，並發環境下，對於不同Segment的資料進行操作不用考慮鎖定競爭。

Linkedjava面試——資料結構、TreeMap、TreeSet

• Linkedjava面試——資料結構：順序存取的java面試——資料結構（基於陣列和雙向鍊錶實作）。
• TreeMap：內部排序（基於紅黑樹實作）。
• TreeSet：有序的Set集合（基於二元樹實作）。

ArrayList、LinkedList、Vector

• ArrayList：動態陣列（基於陣列實作）。
• LinkedList：有序數組（基於雙向鍊錶實作）。
• Vector：物件容器，可放入不同類別的物件（基於陣列實作）。

Collection與Collections

• Collection：集合類別的上級接口，子接口主要有List、Set 、Queue等。
• Collections：提供對集合進行搜尋、排序、替換和執行緒安全化等操作的工具類別。

（更多相關面試題推薦：java面試題目及答案）

二元樹

常見二元樹概念

• B 樹：請參閱資料庫部分https://blog.csdn.net/u012102104/article/details/797773362

• # 平衡二元樹（AVL樹）：各結點左右子樹深度差的絕對值不超過1。

• 哈夫曼樹：帶有權路徑長度最小的二元樹稱為最優二元樹。哈夫曼樹構造不唯一，但所有葉子結點的權限路徑長度總和都是最小的。

• 紅黑樹：一種自平衡二元尋找樹，它的性質有：

  1. 節點是紅色或黑色。
  2. 根節點是黑色。
  3. 每個葉子節點都是黑色的空節點（NIL節點）。
  4. 每個紅色節點的兩個子節點都是黑色。
  5. 從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。

  從每個葉子到根的所有路徑上不能有兩個連續的紅色節點

二元樹的遍歷

// 1. 先序遍历算法 DLRvoid Preorder ( BinTree bt ) {
	if ( bt ) {
		visit ( bt->data );
		Preorder ( bt->lchild );
		Preorder ( bt->rchild );
	}}// 2. 中序遍历算法 LDRvoid Inorder ( BinTree bt ) {
	if ( bt ) {
		Inorder ( bt->lchild );
		visit ( bt->data );
		Inorder ( bt->rchild );
	}}// 3. 后序遍历 LRDvoid Postorder ( BinTree bt ) {
	if ( bt ) {
		Postorder ( bt->lchild );
		Postorder ( bt->rchild );
		visit ( bt->data );
	}}// 4. 按层次遍历。/* 思路：利用一个队列，首先将根（头指针）入队列，以后若队列不空则取队头元素 p，
如果 p 不空，则访问之，然后将其左右子树入队列，如此循环直到队列为空。*/void LevelOrder ( BinTree bt ) {
	// 队列初始化为空
	InitQueue ( Q );
	// 根入队列
	EnQueue ( Q, bt );
	// 队列不空则继续遍历
	while ( ! QueueEmpty(Q) ) {
		DeQueue ( Q, p );
		if ( p!=NULL ) {
			visit ( p->data );
			// 左、右子树入队列
			EnQueue ( Q, p->lchild );
			EnQueue ( Q, p->rchild );
		}
	}}// 非递归遍历二叉树一般借助栈实现

相關推薦：java入門教學

以上是java面試——資料結構的詳細內容。更多資訊請關注PHP中文網其他相關文章！