常見資料結構有：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。
哈夫曼樹：帶有權路徑長度最小的二元樹稱為最優二元樹。哈夫曼樹構造不唯一，但所有葉子結點的權限路徑長度總和都是最小的。
-
紅黑樹：一種自平衡二元尋找樹，它的性質有：
- 節點是紅色或黑色。
- 根節點是黑色。
- 每個葉子節點都是黑色的空節點（NIL節點）。
- 每個紅色節點的兩個子節點都是黑色。
- 從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。
從每個葉子到根的所有路徑上不能有兩個連續的紅色節點
二元樹的遍歷
// 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中文網其他相關文章！
