Data Structure

Java 基本介紹 (5)

教學目標

初步了解 Java 程式語言中集合框架之資料結構的基本概念。

重點概念

在現實社會中我們永遠不會知道未來有多少相同類型的物件,也無法準確的知道物件的類型,為了解決上述問題,Java 程式語言則提供集合框架,又稱容器。主要常用的集和介面則為 List 、 Set 和 Map,並且根據不同的應用情境選擇適合的資料結構。

資料結構 List Set Map
Array ArrayList
Tree TreeSet TreeMap
Linked List LinkedList
Hash Table HashSet HashMap
Hash Table + Linked List LinkedHashSet LinkedHashMap

首先 List 主要有兩種資料結構進行實作,分別為:

  1. ArrayList: 主要以陣列資料結構為主的序列,任何選取的元素皆可以在常數時間內容完成隨機的存取,此外其具有擴充機制,若沒有初始化長度則預設為 10,並且當增加元素超過原始容量時,則新容量為原始容量×3/2+1。
  2. LinkedList: 主要以串列資料結構為主的序列,任何選取的元素皆需在串列上進行,若元素愈接近串列最後位置,則花費時間愈久。

接著 Set 主要有三種資料結構進行實作,分別為:

  1. HashSet: 主要是將元素儲存至雜湊表中,效能最佳,但是對於迭代的順序無法確保。此外 HashSet 的雜湊值主要是由元素的值計算,且因為雜湊值會碰撞所以兩個物件可能會有相同的雜湊值,此時就會透過 equals() 方法判斷物件是否相等。
  2. LinkedHashSet: 主要是將的元素儲存至鏈接的雜湊表中,效能良好,但是會根據被插入集合的順序確保迭代的順序。
  3. TreeSet: 主要是將元素儲存至紅黑樹中,效能中等,但是對於元素的值會進行排序,若需要使用元素的值進行排序請採用 TreeSet,此外 TreeSet 可以搭配 Comparator 自定義針對值進行排序。

再來 Map 主要有三種資料結構進行實作,分別為:

  1. HashMap: 主要是將元素中的索引 (Key) 和值 (Value) 儲存至雜湊表中,效能最佳,但是對於迭代的順序無法確保。接著 HashMap 基於雜湊的原理使用 put(key, value) 方法儲存物件至 HashMap 中,此時會介面先透過 hashCode() 方法取得雜湊值 ((h = key.hashCode()) ^ (h >>> 16)),以利計算 index 值找到正確 Bucket 位置儲存物件,物件內容包括索引和值,若當不同物件有相同雜湊值時則發生碰撞,此時會以Bucket 接串列的形式進行儲存,以及當串列的數量大於 TREEIFY_THRESHOLD 值 (預設為 8) 時就會將串列轉為紅黑樹,接著使用 get(key) 從 HashMap 中取得物件,但若是因為雜湊值相同則發生碰撞時,則會再透過 keys.equals() 方法從串列中找出正確的節點,因此物件內容必須包括索引和值才能夠進行比對索引。再來在 HashMap 有兩個重要的參數,分別為容量 (預設為 16 ) 和負載因子 (預設為 0.75),所謂容量是指 Bucket 的大小,而負載因子則是 Bucket 允許填滿的最大程度,當 Bucket 中的物件數大於容量×負載因子時就會擴增兩位 Bucket 大小,此時還會執行 resize() 方法重新調整 Map 的大小,並且將原來的物件儲存至新的 Bucket 中的過程會執行 transfer() 方法,主要會將儲存在串列中的元素順序相反,直接將元素放在首位,為了避免 Tail Traversing 導致條件競爭發生造成死結。
  2. LinkedHashMap: 主要是將的元素中的索引 (Key) 和值 (Value) 儲存至鏈接的雜湊表中,效能良好,但是會根據被插入集合的順序確保迭代的順序。
  3. TreeMap: 主要是將元素儲存至紅黑樹中,效能中等,但是對於元素的值會進行排序,若需要使用元素的索引進行排序請採用 TreeMap,此外 TreeMap 可以搭配 Comparator 自定義針對索引進行排序。

最後要如何選擇適當集合介面搭配資料結構呢? 一開始最好的方式則是先以 ArrayList 為主,接著當發現效能問題的原因為在 List 中進行過多的插入和移除動作時,才使用 LinkedList,此外當時常進行隨機存取的方法 get() 和 set() 時則是 ArrayList 優於 LinkedList。接著 HashSet 效能優於 TreeSet ,尤其是插入和搜尋,除非需要維持元素的排序狀態,否則請採用 HashSet 即可。再來 HashMap 被設計應用於快速搜尋,其效能優於 TreeMap,除非需要維持元素索引的排序狀態,否則請採用 HashMap 即可,此外 HashMap 的實作主要使用雜湊表搭配陣列和串列的方式進行實作,若不當 hashCode() 方法不當使用則會被當成 LinkedList 使用。當然我們也可以參考不同資料結構的複雜度針對不同應用情境進行最適當的選擇。

資料結構 時間複雜度(搜尋) 時間複雜度(插入) 時間複雜度(刪除) 空間複雜度
Array Θ(n) Θ(n) Θ(n) O(n)
Tree Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n)
Linked List Θ(n) Θ(1) Θ(1) O(n)
Hash Table Θ(1) Θ(1) Θ(1) O(n)

相關資源

Node.js 圖的處理 (2)

基本介紹

教學目標

透過 Node.js 實作廣度優先搜尋找出圖元件中所有節點。

前置作業

  1. 完成 Node.js 套件安裝與設置。

使用教學

撰寫程式

graph.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
var create = function (v) {
this.vertices = v;
this.edges = 0;
this.adj = [];
for (var i = 0; i < this.vertices; ++i) {
this.adj[i] = [];
}
this.addEdge = addEdge;
this.show = show;
this.bfs = bfs;
return this
}
function addEdge(v, w) {
this.adj[v].push(w);
this.adj[w].push(v);
this.edges ++;
}
function show() {
for (var i = 0; i < this.vertices; ++i) {
for (var j = 0; j < this.vertices; ++j) {
if (this.adj[i][j] != undefined && this.adj[i][j] != "") {
console.log( i + " -> " + this.adj[i][j]);
}
}
}
}
function bfs(v) {
if (v == 0) {
this.marked = [];
for (var i = 0; i < this.vertices; ++i) {
this.marked[i] = false;
}
}
var queue = [];
this.marked[v] = true;
queue.push(v);
while (queue.length > 0) {
var v = queue.shift();
if (v != undefined) {
console.log(v);
}
for (var w=0; w<this.adj[v].length; w++) {
if (!this.marked[this.adj[v][w]]) {
this.marked[this.adj[v][w]] = true;
queue.push(this.adj[v][w]);
}
}
}
}
module.exports.create = create;

algorithm.js

1
2
3
4
5
6
7
8
9
10
11
var graph = require("./graph.js");
var g1 = graph.create(5);
g1.addEdge(0,1);
g1.addEdge(0,2);
g1.addEdge(1,3);
g1.addEdge(2,4);

console.log("圖元件");
g1.show();
console.log("廣度優先搜尋");
g1.bfs(0);

執行程式

1
$ node algorithm.js

執行結果

1
2
3
4
5
6
7
8
9
10
11
12
13
圖元件
0 -> 1
0 -> 2
1 -> 3
2 -> 4
3 -> 1
4 -> 2
廣度優先搜尋
0
1
2
3
4

相關資源

Node.js 圖的處理 (1)

基本介紹

教學目標

透過 Node.js 實作深度優先搜尋找出圖元件中所有節點。

前置作業

  1. 完成 Node.js 套件安裝與設置。

使用教學

撰寫程式

graph.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
var create = function (v) {
this.vertices = v;
this.edges = 0;
this.adj = [];
for (var i = 0; i < this.vertices; ++i) {
this.adj[i] = [];
}
this.addEdge = addEdge;
this.show = show;
this.dfs = dfs;
return this
}
function addEdge(v, w) {
this.adj[v].push(w);
this.adj[w].push(v);
this.edges ++;
}
function show() {
for (var i = 0; i < this.vertices; ++i) {
for (var j = 0; j < this.vertices; ++j) {
if (this.adj[i][j] != undefined && this.adj[i][j] != "") {
console.log( i + " -> " + this.adj[i][j]);
}
}
}
}
function dfs(v) {
if (v == 0) {
this.marked = [];
for (var i = 0; i < this.vertices; ++i) {
this.marked[i] = false;
}
}
this.marked[v] = true;
if (this.adj[v] != undefined) {
console.log(v)
}
for (var w = 0; w <this.adj[v].length; w++) {
if (!this.marked[this.adj[v][w]]) {
this.dfs(this.adj[v][w]);
}
}
}
module.exports.create = create;

algorithm.js

1
2
3
4
5
6
7
8
9
10
11
var graph = require("./graph.js");
var g1 = graph.create(5);
g1.addEdge(0,1);
g1.addEdge(0,2);
g1.addEdge(1,3);
g1.addEdge(2,4);

console.log("圖元件");
g1.show();
console.log("深度優先搜尋");
g1.dfs(0);

執行程式

1
$ node algorithm.js

執行結果

1
2
3
4
5
6
7
8
9
10
11
12
13
圖元件
0 -> 1
0 -> 2
1 -> 3
2 -> 4
3 -> 1
4 -> 2
深度優先搜尋
0
1
3
2
4

相關資源

Node.js 排序處理 (3)

基本介紹

教學目標

透過 Node.js 實作資料結構與演算法中的插入排序法。

前置作業

  1. 完成 Node.js 套件安裝與設置。

使用教學

撰寫程式

algorithm.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
var data = [];
var number = 500
for (var n = 0; n < number; n++) {
data[n] = Math.floor(Math.random() * (number + 1))
}

var shell_sort_start = new Date().getTime();
var shell_sort_result = shellSort(data.slice());
var shell_sort_stop = new Date().getTime();
var shell_sort_elapsed = shell_sort_stop - shell_sort_start;

console.log("希爾排序法");
console.log("原始資料: " + data );
console.log("排序結果: " + shell_sort_result );
console.log("花費時間: " + shell_sort_elapsed + " 毫秒" );

function shellSort(data) {
var gap = data.length / 2;
while (gap >= 1) {
for (var i = gap; i < data.length; i++) {
for (var j = i; j >= gap && data[j] < data[j-gap]; j -= gap) {
var temp = data[j];
data[j] = data[j-gap];
data[j-gap] = temp;
}
}
gap = parseInt(gap / 2);
}
return data;
}

執行程式

1
$ node algorithm.js

執行結果

1
2
3
4
希爾排序法
原始資料: 333,61,75,320,193,500,161,197,459,318,43,145,367,57,380,332,5,69,53,143,340,332,4,96,313,12,204,148,490,354,177,292,335,449,87,412,380,291,474,167,431,76,388,349,17,481,52,216,272,486,290,178,262,383,495,38,76,389,232,486,249,156,346,172,500,63,180,85,122,370,138,59,115,243,76,100,366,470,123,182,153,322,58,66,149,238,363,118,361,48,44,49,128,192,400,156,460,406,333,232,495,5,197,436,472,321,104,317,268,207,378,97,137,322,298,207,242,258,229,179,143,61,263,137,127,275,90,426,374,18,43,33,444,121,264,119,313,322,334,194,435,328,369,230,54,345,40,297,260,314,461,30,26,417,235,398,18,378,10,282,225,143,450,239,170,135,47,483,163,117,336,392,194,370,288,259,357,36,253,266,95,22,403,399,218,404,375,136,141,289,132,234,291,24,248,424,344,332,72,78,353,333,386,476,23,460,41,274,67,445,206,318,126,24,133,394,96,364,38,25,247,454,387,335,7,232,370,395,75,168,328,49,77,295,75,473,225,399,346,313,235,398,474,486,350,133,413,45,140,361,281,17,115,466,53,157,349,314,197,406,5,52,304,17,195,403,153,115,38,24,172,473,286,344,9,63,309,244,90,431,228,470,31,210,211,231,225,408,346,209,325,483,367,247,486,229,382,256,209,483,335,362,223,199,373,444,437,71,118,222,424,414,457,15,413,325,439,166,163,179,376,135,388,221,54,64,416,247,91,136,393,131,417,105,145,288,149,353,170,99,209,395,386,268,202,284,372,64,293,499,483,194,158,173,484,5,242,196,372,487,51,475,205,274,416,348,155,399,133,249,318,288,240,85,28,131,481,484,490,271,405,253,40,348,229,412,77,406,236,403,212,268,322,220,85,380,416,335,59,227,420,137,190,420,142,285,138,368,140,269,339,22,495,297,69,285,358,374,467,110,147,393,458,61,332,181,256,56,277,48,291,329,384,382,352,361,119,466,112,167,123,237,251,296,228,412,260,154,208,133,50,381,395,352,443,356,450,341,339,466,332,48,262,434,174,308,454,211,136,255,353,343,347,74,17,0,8,194,181,25,384,144,344,308,339,336,229,72,334,133,475,132,237,151,268,126,497,141,8,89
排序結果: 0,4,5,5,5,5,7,8,8,9,10,12,15,17,17,17,17,18,18,22,22,23,24,24,24,25,25,26,28,30,31,33,36,38,38,38,40,40,41,43,43,44,45,47,48,48,48,49,49,50,51,52,52,53,53,54,54,56,57,58,59,59,61,61,61,63,63,64,64,66,67,69,69,71,72,72,74,75,75,75,76,76,76,77,77,78,85,85,85,87,89,90,90,91,95,96,96,97,99,100,104,105,110,112,115,115,115,117,118,118,119,119,121,122,123,123,126,126,127,128,131,131,132,132,133,133,133,133,133,135,135,136,136,136,137,137,137,138,138,140,140,141,141,142,143,143,143,144,145,145,147,148,149,149,151,153,153,154,155,156,156,157,158,161,163,163,166,167,167,168,170,170,172,172,173,174,177,178,179,179,180,181,181,182,190,192,193,194,194,194,194,195,196,197,197,197,199,202,204,205,206,207,207,208,209,209,209,210,211,211,212,216,218,220,221,222,223,225,225,225,227,228,228,229,229,229,229,230,231,232,232,232,234,235,235,236,237,237,238,239,240,242,242,243,244,247,247,247,248,249,249,251,253,253,255,256,256,258,259,260,260,262,262,263,264,266,268,268,268,268,269,271,272,274,274,275,277,281,282,284,285,285,286,288,288,288,289,290,291,291,291,292,293,295,296,297,297,298,304,308,308,309,313,313,313,314,314,317,318,318,318,320,321,322,322,322,322,325,325,328,328,329,332,332,332,332,332,333,333,333,334,334,335,335,335,335,336,336,339,339,339,340,341,343,344,344,344,345,346,346,346,347,348,348,349,349,350,352,352,353,353,353,354,356,357,358,361,361,361,362,363,364,366,367,367,368,369,370,370,370,372,372,373,374,374,375,376,378,378,380,380,380,381,382,382,383,384,384,386,386,387,388,388,389,392,393,393,394,395,395,395,398,398,399,399,399,400,403,403,403,404,405,406,406,406,408,412,412,412,413,413,414,416,416,416,417,417,420,420,424,424,426,431,431,434,435,436,437,439,443,444,444,445,449,450,450,454,454,457,458,459,460,460,461,466,466,466,467,470,470,472,473,473,474,474,475,475,476,481,481,483,483,483,483,484,484,486,486,486,486,487,490,490,495,495,495,497,499,500,500
花費時間: 1 毫秒

相關資源

Node.js 排序處理 (2)

基本介紹

教學目標

透過 Node.js 實作資料結構與演算法中的插入排序法。

前置作業

  1. 完成 Node.js 套件安裝與設置。

使用教學

撰寫程式

algorithm.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
var data = [];
var number = 500
for (var n = 0; n < number; n++) {
data[n] = Math.floor(Math.random() * (number + 1))
}

var insertion_sort_start = new Date().getTime();
var insertion_sort_result = insertionSort(data.slice());
var insertion_sort_stop = new Date().getTime();
var insertion_sort_elapsed = insertion_sort_stop - insertion_sort_start;

console.log("插入排序法");
console.log("原始資料: " + data );
console.log("排序結果: " + insertion_sort_result );
console.log("花費時間: " + insertion_sort_elapsed + " 毫秒" );

function insertionSort(data) {
var temp, inner;
for (var outer = 1; outer <= data.length - 1 ; ++outer) {
temp = data[outer];
inner = outer;
while (inner > 0 && data[inner - 1] >= temp) {
data[inner] = data[inner - 1];
--inner;
}
data[inner] = temp;
}
return data;
}

執行程式

1
$ node algorithm.js

執行結果

1
2
3
4
插入排序法
原始資料: 343,479,136,358,299,408,11,453,404,430,41,203,272,259,336,61,109,83,322,433,168,72,481,246,284,52,64,233,85,310,427,357,454,172,472,220,498,329,211,283,308,470,308,209,319,179,96,198,454,426,399,396,418,24,408,79,180,168,79,215,256,388,428,132,75,109,463,258,276,178,317,355,238,314,40,385,425,160,159,322,261,184,419,391,214,359,184,374,48,14,20,402,371,113,347,194,10,91,428,372,215,459,174,61,151,446,454,226,411,390,213,399,159,272,7,132,308,428,428,196,313,189,215,301,110,82,252,478,277,440,218,406,1,308,214,8,37,352,102,410,79,422,213,75,455,381,354,223,249,6,166,269,168,137,322,33,54,338,122,306,410,420,337,172,164,438,464,354,266,451,378,222,208,147,469,309,88,443,229,357,86,330,110,90,288,436,425,168,122,220,227,185,389,243,383,500,44,45,9,13,276,398,14,383,248,201,440,173,350,495,159,492,364,466,229,416,0,52,428,390,444,128,374,297,185,119,136,228,84,117,10,205,111,77,496,125,66,391,29,388,4,111,410,110,449,423,60,467,41,113,299,451,343,322,376,99,46,204,55,452,38,36,57,31,90,6,58,426,405,220,286,181,26,27,362,209,6,256,383,141,449,379,264,100,42,317,401,7,124,152,182,16,324,108,81,31,333,17,322,106,468,163,479,414,19,226,253,468,382,438,58,455,415,92,264,270,391,249,496,177,182,143,33,226,54,142,220,44,242,453,12,219,246,56,72,329,377,431,163,122,213,117,166,58,288,43,224,261,431,20,214,48,100,386,108,31,287,215,35,158,72,294,158,428,164,52,369,96,314,391,354,111,474,348,31,363,204,101,304,493,201,223,95,67,37,478,110,348,316,57,264,444,195,21,248,471,108,6,337,322,379,189,146,185,357,377,491,147,8,327,289,184,375,355,418,422,293,281,89,289,146,267,430,485,426,60,107,361,94,333,319,343,257,177,24,220,243,326,351,280,257,265,136,289,15,67,155,485,234,71,490,137,268,112,131,475,406,274,87,30,379,13,361,275,440,498,6,476,52,369,265,394,196,387,283,309,122,296,48,74,5,336,348,182,499,33,47,291,256,134,130,159,477,382,392,415,37,118,144,341
排序結果: 0,1,4,5,6,6,6,6,6,7,7,8,8,9,10,10,11,12,13,13,14,14,15,16,17,19,20,20,21,24,24,26,27,29,30,31,31,31,31,33,33,33,35,36,37,37,37,38,40,41,41,42,43,44,44,45,46,47,48,48,48,52,52,52,52,54,54,55,56,57,57,58,58,58,60,60,61,61,64,66,67,67,71,72,72,72,74,75,75,77,79,79,79,81,82,83,84,85,86,87,88,89,90,90,91,92,94,95,96,96,99,100,100,101,102,106,107,108,108,108,109,109,110,110,110,110,111,111,111,112,113,113,117,117,118,119,122,122,122,122,124,125,128,130,131,132,132,134,136,136,136,137,137,141,142,143,144,146,146,147,147,151,152,155,158,158,159,159,159,159,160,163,163,164,164,166,166,168,168,168,168,172,172,173,174,177,177,178,179,180,181,182,182,182,184,184,184,185,185,185,189,189,194,195,196,196,198,201,201,203,204,204,205,208,209,209,211,213,213,213,214,214,214,215,215,215,215,218,219,220,220,220,220,220,222,223,223,224,226,226,226,227,228,229,229,233,234,238,242,243,243,246,246,248,248,249,249,252,253,256,256,256,257,257,258,259,261,261,264,264,264,265,265,266,267,268,269,270,272,272,274,275,276,276,277,280,281,283,283,284,286,287,288,288,289,289,289,291,293,294,296,297,299,299,301,304,306,308,308,308,308,309,309,310,313,314,314,316,317,317,319,319,322,322,322,322,322,322,324,326,327,329,329,330,333,333,336,336,337,337,338,341,343,343,343,347,348,348,348,350,351,352,354,354,354,355,355,357,357,357,358,359,361,361,362,363,364,369,369,371,372,374,374,375,376,377,377,378,379,379,379,381,382,382,383,383,383,385,386,387,388,388,389,390,390,391,391,391,391,392,394,396,398,399,399,401,402,404,405,406,406,408,408,410,410,410,411,414,415,415,416,418,418,419,420,422,422,423,425,425,426,426,426,427,428,428,428,428,428,428,430,430,431,431,433,436,438,438,440,440,440,443,444,444,446,449,449,451,451,452,453,453,454,454,454,455,455,459,463,464,466,467,468,468,469,470,471,472,474,475,476,477,478,478,479,479,481,485,485,490,491,492,493,495,496,496,498,498,499,500
花費時間: 2 毫秒

相關資源