常見資料結(jié)構(gòu)有：java面試——資料結(jié)構(gòu)、Hashtable、 Concurrentjava面試——資料結(jié)構(gòu)。

（相關(guān)影片分享：java教學(xué)影片）

下面我們分別來介紹：

java面試——資料結(jié)構(gòu)

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

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

Hashtable

Hashtable線程安全的策略實(shí)現(xiàn)代價(jià)很大，get/put所有相關(guān)操作都是synchronized的，在競爭激烈的並發(fā)場景中性能非常差。

Concurrentjava面試——資料結(jié)構(gòu)

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

Linkedjava面試——資料結(jié)構(gòu)、TreeMap、TreeSet

• Linkedjava面試——資料結(jié)構(gòu)：順序存取的java面試——資料結(jié)構(gòu)（基於陣列和雙向鍊錶實(shí)作）。
• TreeMap：內(nèi)部排序（基於紅黑樹實(shí)作）。
• TreeSet：有序的Set集合（基於二元樹實(shí)作）。

ArrayList、LinkedList、Vector

• ArrayList：動(dòng)態(tài)陣列（基於陣列實(shí)作）。
• LinkedList：有序數(shù)組（基於雙向鍊錶實(shí)作）。
• Vector：物件容器，可放入不同類別的物件（基於陣列實(shí)作）。

Collection與Collections

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

（更多相關(guān)面試題推薦：java面試題目及答案）

二元樹

常見二元樹概念

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

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

• 哈夫曼樹：帶有權(quán)路徑長度最小的二元樹稱為最優(yōu)二元樹。哈夫曼樹構(gòu)造不唯一，但所有葉子結(jié)點(diǎn)的權(quán)限路徑長度總和都是最小的。

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

  1. 節(jié)點(diǎn)是紅色或黑色。
  2. 根節(jié)點(diǎn)是黑色。
  3. 每個(gè)葉子節(jié)點(diǎn)都是黑色的空節(jié)點(diǎn)（NIL節(jié)點(diǎn)）。
  4. 每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色。
  5. 從任一節(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。

  從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn)

二元樹的遍歷

//?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.?按層次遍歷。/*?思路：利用一個(gè)隊(duì)列，首先將根（頭指針）入隊(duì)列，以后若隊(duì)列不空則取隊(duì)頭元素?p，
如果?p?不空，則訪問之，然后將其左右子樹入隊(duì)列，如此循環(huán)直到隊(duì)列為空。*/void?LevelOrder?(?BinTree?bt?)?{
	//?隊(duì)列初始化為空
	InitQueue?(?Q?);
	//?根入隊(duì)列
	EnQueue?(?Q,?bt?);
	//?隊(duì)列不空則繼續(xù)遍歷
	while?(?!?QueueEmpty(Q)?)?{
		DeQueue?(?Q,?p?);
		if?(?p!=NULL?)?{
			visit?(?p->data?);
			//?左、右子樹入隊(duì)列
			EnQueue?(?Q,?p->lchild?);
			EnQueue?(?Q,?p->rchild?);
		}
	}}//?非遞歸遍歷二叉樹一般借助棧實(shí)現(xiàn)

相關(guān)推薦：java入門教學(xué)

以上是java面試——資料結(jié)構(gòu)的詳細(xì)內(nèi)容。更多資訊請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！