tags: 說明

筆記內容用於個人學習，大都整理自公開的網路資訊，再加上自己的學習心得

---

• 程式設計
  • C 語言的巨集與函數比較
  • 設計模式(design pattern)
  • public,protected,private
  • Visual Basic 的迴圈 do,while,until,loop
  • C 語言的 pointer 跟 data 與 memory 範例
  • 物件導向三大特色
  • 程式基本結構
    • 結構化程式三要素
  • call by value,address(pointer),reference
    • call by value
    • call by address(pointer)
    • call by reference
  • 移位運算
    • <<（左移)
    • >>（右移)
  • C語言 putchar,puts
    • putchar
    • puts
  • Verilog
    • Verilog blocking
    • Verilog non-blocking
  • javac 編譯器
  • 邏輯閘
    • AND
    • OR
    • XOR
    • 萬用邏輯閘
  • 組合邏輯電路
  • 序向邏輯電路
  • SR閂鎖
  • 正反器 Flip-flop
    • JK 正反器
  • 布林代數的基本定理
  • 數位邏輯-卡諾圖
  • PLA(Programmable Logic Array)
    • 可程式化邏輯陣列
  • Overload
  • Method Signature
  • Override
  • 編譯 (Compile) 和直譯 (Interprete)
    • 編譯式語言
    • 直譯式語言
  • Semaphore
    • 號誌
  • Critical section
    • 臨界區段（
  • UML()Unified Modeling Language)
    • 統一塑模語言
  • Hash
    • 雜湊
    • 雜湊方法(Hash method)
  • CFG(Context-Free Grammar)
  • if(i=0) vs if(i==0)
  • ++i VS i++
  • String == 跟 equal
    • String 沒有 new String 物件
    • String 有 new String 物件
  • 連結串列（link list) 與 陣列（array)比較

---

程式設計

---

C 語言的巨集與函數比較

巨集與函數的功能相同，但在編譯時，編譯時會以巨集取代原來的敘述，而函數則是一個跳躍敘述；在 程式執行期間，由於巨集已經展開為它所代表的敘述，程式會一行一行執行下去，而碰到函數則是跳到函數定義的副程式去執行。所以，如果將子功能以巨集撰寫，執行速度較快，但編譯後的程式碼較大；函數寫法則執行速度較慢，但是執行檔較小，如何取捨完全看程式設計的目的與需求。

巨集(macro)

• 優點：執行速度快，沒有堆疊的 push 和 pop 動作的需要，減少時間的耗損。另外使得程式易維護且可讀性高。
• 缺點：巨集被呼叫多次以後，會耗損存放及使用大量的記憶體空間。

函數(call function/call subroutine)

• 優點：即使函數被呼叫多次，在記憶體中仍只有一份實體，較節省記憶體空間。能節省存放及使用的記憶體空間。
• 缺點：執行速度較慢，需花費時間在堆疊的 push 和 pop 動作上。

設計模式(design pattern)

在軟體工程中，設計模式（design pattern）是對軟體設計中普遍存在（反覆出現）的各種問題，所提出的解決方案。這個術語是由埃里希·伽瑪（Erich Gamma）等人在1990年代從建築設計領域引入到電腦科學的。

設計模式並不直接用來完成程式碼的編寫，而是描述在各種不同情況下，要怎麼解決問題的一種方案。物件導向設計模式通常以類別或物件來描述其中的關係和相互作用，但不涉及用來完成應用程式的特定類別或物件。設計模式能使不穩定依賴於相對穩定、具體依賴於相對抽象，避免會引起麻煩的緊耦合，以增強軟體設計面對並適應變化的能力

單件設計模式	singleton pattern	單例對象的類必須保證只有一個實例存在
工廠方法設計模式	Factory method pattern	工廠物件通常包含一個或多個方法，用來建立這個工廠所能建立的各種類型的物件
樣板方法模式	Template attern	定義了一個演算法的步驟，並允許子類別為一個或多個步驟提供其實踐方式
代理人模式	Proxy pattern )	所謂的代理者是指一個類別可以作為其它東西的介面。代理者可以作任何東西的介面：網路連接、記憶體中的大物件、檔案或其它昂貴或無法複製的資源。
複合模式	Compound Pattern	結合兩個或以上的模式。

---

public,protected,private

在說明這四個關鍵字之前，我想就 class 之間的關係做一個簡單的定義

• 對於繼承自己的 class，base class可以認為他們都是自己的子女
• 而對於和自己一個目錄下的 classes，認為都是自己的朋友。

1. public：
   表明該數據成員、成員函數是對所有用戶開放，所有用戶都可以直接進行調用

2. private：
   表示私有，私有的意思就是除了 class 自己之外，任何人都不可以直接使用，私有財產神聖不可侵犯嘛，即便是子女，朋友，都不可以使用。

3. protected：
   對於子女、朋友來說，就是 public 的，可以自由使用，沒有任何限制，而對於其他的外部 class，protected 就變成 private。

private 只有跟他同一隻的 java 可以
proteced 同一個 packge 的都可以
public 都可以

---

Visual Basic 的迴圈 do,while,until,loop

---

C 語言的 pointer 跟 data 與 memory 範例

請問下列 C 語言程式執行後輸出為何？ int y[5]={2, 4, 6, 8, 10}; int* p=y+1; printf(“%dn”,p[2]);
(A) 2
(B) 4
(C) 6
(D) 8

請看下列的 code 實做與輸出結果，p[2] = 8

---

物件導向三大特色

OOP(object-oriented programming) 物件導向

1. 資料封裝(Encapsulation)
   簡單講，資料封裝就是將資料分成私用(Private)、保護(Protected)、公用(Public)等，實踐 Information hiding 概念, 避免程式各個物件互相干擾，降低程式的複雜度及維護上的困難度。

2. 繼承(Inheritance)
   有繼承的關係後，父類別 (Super class) 中的資料 (Data) 或方法 (Method) 在次子類(Subclass)就可以繼承使用，次子類別的次子類別也可以繼承使用，最後即能達到資料重覆使用的目的。

3. 多型(Polymorphism)
   多型(Polymorphism) 代表能夠在執行階段，物件能夠依照不同情況變換資料型態，換句話說，多型是指一個物件參考可以在不同環境下，扮演不同角色的特性，指向不同的物件實體，可 透過實作多個繼承或介面來實現父類別，並使用Override或Overload來達成。

---

程式基本結構

結構化程式三要素

在撰寫程式階段，必須特別留意程式的基本結構，以使程式容易閱讀，有助於程式的測試與維護。原則上，任何一個程式都可透過循序、選擇、重複三種基本控制結構表達出來。

一、循序結構(Sequence)：程式由上而下，依序一行一行執行。第四章所介紹的範例程式，都只使用到循序結構。

二、選擇結構(Selection)：或稱決策(Decision)。程式流程進入判斷的菱形符號後，會判斷測試條件是否成立。然後，依據判斷的結果選擇程式的流向。

三、重複結構(Iteration)：或稱迴圈(Loop)。部分程式片段可重複執行多次，直到某測試條件發生為止。程式重複執行部分即構成迴圈。通常迴圈又可分為前測試迴圈和後測試迴圈兩種。前測試迴圈是第一次進入迴圈程式之前，即進行測試條件判斷。後測試迴圈則是先執行一次迴圈程式之後，才進行測試條件判斷。

---

call by value,address(pointer),reference

call by value

void swap(int a, int b){
int tmp = a;
a = b;
b = tmp;
}
則呼叫 swap(x, y)後， x 和 y 的值並不會有變化。

假設函式 A 呼叫函式 swap(x, y)，則 swap 中的 x 和 y 是 「複製」 自函式 A 所傳入的參數，swap 中對 x, y 所做的任何運算都不會影響到 A 中的 x 和 y，因為 B 執行完後，並不會把複製的 x, y 存回到 A 中。這種參數傳遞方式，我們稱之為call by value。

call by address(pointer)

void swap(int* a, int* b){
int tmp = *a;
*a = *b;
*b = tmp;
}
呼叫 swap 時，要寫成 swap(&x, &y)。呼叫 swap 時，x 的指標 (x 的儲存位置) 與 y 的指標 (y 的儲存位置)會被複製一份到 swap 中，然後把該位置內所記載的值做更換。swap結束後，&x (address of x) 和 &y (address of y) 依然沒變， 只是 address of x 所記錄之變數值與 address of y 所記錄之變數值交換了 。因為 &x 和 &y 其實是利用call by value 在傳，因此，call by address 其實骨子裡就是 call by value。

利用指標來做參數傳遞，這種方法骨子裡仍是 call by value，只不過 call by value 的 value，其資料型態為指標罷了。

call by reference

swap(int &a, int &b){
int tmp = a;
a = b;
b = tmp;
}
未來使用時，只要呼叫 swap(x, y)，就可以讓 x 和 y 的值交換。在這個例子中，a 就是 x, b 就是 y。

這是C++才加進來的東西，C 本身並沒有 call by reference。call by reference 基本上是把參數做個別名 (alias)

---

移位運算

<<（左移)

左移運算符 << 使指定值的所有位都左移規定的次數。

左移的規則只記住一點：丟棄最高位，0補最低位

ex:
3 << 2 (3為int型)

1. 把 3 轉換為二進制數字
   0000 0000 0000 0000 0000 0000 0000 0011
2. 把該數字高位(左側)的兩個零移出，其他的數字都朝左平移 2 位
3. 在低位(右側)的兩個空位補零。則得到的最終結果是
   0000 0000 0000 0000 0000 0000 0000 1100

>>（右移)

右移運算符 << 使指定值的所有位都右移規定的次數。

右移的規則只記住一點：符號位不變，左邊補上符號位

ex:
3 << 2 (3為int型)

1. 把 3 轉換為二進制數字
   0000 0000 0000 0000 0000 0000 0000 0011
2. 把該數字高位(左側)的兩個零移出，其他的數字都朝左平移 2 位
3. 在低位(右側)的兩個空位補零。則得到的最終結果是
   0000 0000 0000 0000 0000 0000 0000 1100

---

C語言 putchar,puts

putchar

putchar()輸出一個字元。

puts

puts()用來輸出字串，並直接進行換行。

範例:

int main()
{
    char *p="abc"; puts(p); 
    // 會印出 abc
    char *a="abc"; putchar(*a);
    // 只印出 a
    return 0;
}

---

Verilog

Verilog 是一種用於描述、設計電子系統（特別是 數位電路 ）的硬體描述語言，主要用於在積體電路設計，特別是超大型積體電路的電腦輔助設計。Verilog是電氣電子工程師學會（IEEE）的1364號標準。[1]

在Verilog中，有兩種賦值運算，一種叫做阻塞賦值（blocking assignment），另一種叫做非阻塞賦值（non-blocking assignment）。

Verilog blocking

其運算子為 =
在順序程式碼塊中使用阻塞賦值語句，如果這一句沒有執行完成，那麼後面的語句不會執行。

Verilog non-blocking

其運算子為 <=
如果在順序程式碼塊中使用非阻塞賦值，則執行這一句的同時，並 不會阻礙下一句程式碼的執行。而且，如果後一個語句涉及前面一個非阻塞賦值語句中的變數，由於這兩個語句「同時」執行，因此後一個語句所用到的是前面一個語句執行前變數的數值。

---

javac 編譯器

• 對於每一個 Java 類別,編譯完成後都會出現一個與類別名稱相同,而副檔名為 *.class 的檔案
• 這個檔案是位元碼(byte-code)格式
• 在執行 Java 程式時,會被 Java 虛擬機器轉(JVM) 換為目標平台所認識的原生碼( Native code )。

---

邏輯閘

詳細邏輯閘請看

AND

AND 邏輯閘 ==> 圖形如 AN D

OR

OR 邏輯閘 ==> 圖形如 O 的右邊

XOR

萬用邏輯閘

• NAND
• NOR
  可以單獨使用 NOR 閘或 NAND閘來產生其他邏輯閘的所有功能

---

組合邏輯電路

在數位電路理論中，組合邏輯電路（combinatorial logic或combinational logic）是一種邏輯電路，它的任一時刻的穩態輸出，僅僅與該時刻的輸入變量的取值有關，而與該時刻以前的輸入變量取值無關。相對於組合邏輯電路，序向邏輯電路的輸出結果除了依照目前的輸入外也和先前的輸入有關係。

從電路結構分析，組合電路由各種邏輯閘組成，網絡中無記憶元件，也無回饋線。

序向邏輯電路

在數位電路理論中，序向邏輯電路是指電路任何時刻的穩態輸出不僅取決於當前的輸入，還與前一時刻輸入形成的狀態有關。這跟組合邏輯電路相反，組合邏輯的輸出只會跟目前的輸入成一種函數關係。

時序邏輯擁有 儲存元件（記憶體）來存儲信息，而組合邏輯則沒有。

SR閂鎖

閂鎖（英語：latch），或稱鎖存器，是數位電路中非同步時序邏輯電路系統中用來儲存資訊的一種電子電路。一個閂鎖可以儲存一位元的資訊，通常會有多個一起出現，有些會有特別的名稱，像是 「4位閂鎖」（可以儲存四個位元）或「8位閂鎖」（可以儲存八個位元）等等

最簡單的閂鎖是「SR閂鎖」，(又有稱為「RS閂鎖」)，其中

• 「S」 表示「設定」（Set）
• 「R」 表示「重設」（Reset）

是正反器中最簡單的一種，也是各種其他類型正反器的基本組成部分。兩個NAND或兩個NOR的輸入端輸出端進行交叉耦合或首尾相接，即可構成一個基本RS正反器。

當R與S皆為低電位，回授會讓 Q 與

$\overline{Q}$ （Q的反相）保持於一個固定的狀態。當S("Set")為高電位，R("Reset")為低電位時，輸出Q會被強制設定為高電位；相反的，當S為低電位，R為高電位時，輸出Q會被強制設定為低電位。

從以上的說明中可知，NOR R-S門栓可經由R、S的動作來決定 Q 的輸出，一旦R、S均等於0時，就可將Q的狀態保存下來，直到R、S有不同的輸入，或是電源被移除，才有可能改變Q的狀態，門栓電路有記憶位元狀態的功能已見端倪。

• NOR R-S門栓，當S、R均等於0時，Q保持原來的狀態，不做任何改變。
• NOR R-S門栓，當S、R均等於1時，Q=Q'=0產生不合乎邏輯定義的結果。

正反器 Flip-flop

正反器（英語：Flip-flop, FF），中國大陸譯作「觸發器」、臺灣及香港譯作「正反器」，是一種具有兩種穩態的用於儲存的元件，可記錄二進位數位訊號「1」和「0」。

正反器是一種雙穩態多諧振盪器（bistable multivibrator）。該電路可以通過一個或多個施加在控制輸入端的訊號來改變自身的狀態，並會有1個或2個輸出。正反器是構成序向邏輯電路以及各種複雜數位系統的基本邏輯單元。正反器和閂鎖是在電腦、通訊和許多其他類型的系統中使用的數位電子系統的基本組成部分。

JK 正反器

JK 正反器設有兩個輸入，其輸出的值由以下的算式來決定。

JK 正反器符號。J、K 是資料輸入

JK正反器和正反器中最基本的RS正反器結構相似，其區別在於，RS正反器不允許R與S同時為1，而JK正反器允許J與K同時為1。當J與K同時變為1的同時，輸出的值狀態會反轉。也就是說，原來是0的話，變成1；原來是1的話，變成0。 對應表如下:

---

布林代數的基本定理

數位邏輯-卡諾圖

---

PLA(Programmable Logic Array)

可程式化邏輯陣列

可程式化邏輯陣列（Programmable Logic Array）（PLA）是一種可以實作組合邏輯電路的可程式邏輯裝置。PLA 有一組可編程的 AND 閘，其連接到一組可編程的 OR 閘，如此可以達到：「只在合乎設定條件時才允許產生邏輯訊號輸出。」 PLA 有2^N 個 AND 閘來輸入 N 個變數，並且需要 M 個 OR 閘來輸出 M 個結果。PLA 如此的邏輯閘布局能用來規劃大量的邏輯函式，這些邏輯函式必須先以積項（有時是多個積項）的原始形式進行齊一化。

---

Overload

Overload 詳細參考
多載

簡單來說就是： 根據不同情境 『相同的模樣，擁有不同的行為』。

• 運算子多載 (Operator Overloading)

「+」、「–」在不同時候卻有不同意義 ( 加減 vs. 正負數)。

• 方法多載 (Method Overloading)

『方法的模樣』便是指方法名稱 (method’s name)，也就是：相同的方法名稱，擁有不同的實作。

需注意的是，當有人同時提及 Overload (多載) 與Override (覆寫) 時， 87% 指的都是方法多載 (MethodOverloading)，而非運算子多載唷 😲！

void test();
void test(int i);
void test(char c);
void test(String s, int i);
void test(String s, String s2);

多載 (Overlaod) 大幅地增加了程式開發的便利性，例如，Java 的 valueOf 函式，提供了多種 多載方法，使我們得以用相同的方法名稱，執行不同資料型別的轉型操作：

Method Signature

方法簽章

方法簽章 = 方法名稱 (method’s name) + 參數型別 (parameter types)

編譯器是使用方法簽章 (Method Signature)區分不同方法，而非回傳型別 (return type)，因此，不能宣告兩個具有相同簽章的方法。

下列的三個 Method Signature 都是不一樣的

• void cook()
• void cook(char meal)
• void cook(char meal, int quantity)

但是下面兩個 Method Signature 是一樣不能共用

• void cook(char meal)
• boolean cook(char meal)

class Chef {
// 回傳型別： void
// 參數型別： 無
void cook() {
... 略 ...
}

// 回傳型別： void
// 參數型別： char
void cook(char meal) {
... 略 ...
}

// 回傳型別： void
// 參數型別： char, int
void cook(char meal, int quantity) {
... 略 ...
}

boolean cook(char meal){
... 略 ...
}

}

---

Override

Override 詳細參考
覆寫 ==> 重新定義

• Override (覆寫)讓 子類別 能以異於 父類別 的方式處理訊息。
• 子類別 要能 Override (覆寫)，前提是有 父類別/介面。

使 子類別 覆寫 (重新定義)『繼承/實作自 父類別/介面 的方法 』。

例如，這是一個標準的 Override (覆寫) 範例，其中，子類別 SubClass 與 父類別 SuperClass 的 earn(int i) 方法：
方法簽章 (方法名稱 + 參數型別) 完全相同。

public class Main {

    public static void main(String[] args) {

        new SubClass().earn(500);
    }
}

class SuperClass {

    void earn(int i) {
        System.out.println("老爸賺了: " + i);
    }
}

class SubClass extends SuperClass {

    @Override
    void earn(int i) { // 方法名稱 與 參數型別 同父類別
        System.out.println("兒子賺了: " + i);
    }
}

---

編譯 (Compile) 和直譯 (Interprete)

編譯式語言

多半會是靜態語言 (static language)，它們擁有事先定義的型別，型別檢查 (type check) 與 高效能的執行速度 等特性。

C, C++, Pascal, VB 都是編譯式語言。

編譯容易將程式最佳化，較適合多次使用的程式

直譯式語言

原始的程式碼要經過 直譯器 (Interpreter) 轉換成可執行碼，由於它們不需要經由編譯器，而是在執行時才會將原始碼直譯成執行碼，所以 速度上會比編譯與連結器產生的執行碼要慢，效能會有一部份取決於直譯器的速度，而直譯式語言多半以動態語言 (dynamic language) 為主，具有靈活的型別處理 (鬆散型別)，動態生成與程式彈性，但速度會比編譯式的要慢一些。

Perl, JavaScript, Python, Ruby, PHP, ASP 都是直譯式語言。

另外 JAVA 跟 C# 為混合式

• 可以允許變數在使用前，不需要宣告該變數的形態
• 可以直接產生結果，不會產生目標代碼

---

Semaphore

號誌

又稱為旗號，是一個同步物件，用於保持在0至指定最大值之間的一個計數值。當執行緒完成一次對該semaphore物件的等待（wait）時，該計數值減一；當執行緒完成一次對semaphore物件的釋放（release）時，計數值加一。當計數值為0，則執行緒等待該semaphore物件不再能成功直至該semaphore物件變成signaled狀態。semaphore物件的計數值大於0，為signaled狀態；計數值等於0，為nonsignaled狀態.

semaphore物件適用於控制一個僅支援有限個用戶的共用資源，是一種不需要使用忙碌等待（busy waiting）的方法。

號誌的概念是由荷蘭電腦科學家艾茲赫爾·戴克斯特拉（Edsger W. Dijkstra）發明的，廣泛的應用於不同的作業系統中。在系統中，給予每一個行程一個號誌，代表每個行程目前的狀態，未得到控制權的行程會在特定地方被強迫停下來，等待可以繼續進行的訊號到來。如果號誌是一個任意的整數，通常被稱為計數號誌（Counting semaphore），或一般號誌（general semaphore）；如果號誌只有二進位的0或1，稱為二進位號誌（binary semaphore）。在linux系統中，二進位號誌（binary semaphore）又稱互斥鎖（Mutex）。

---

Critical section

臨界區段（

在同步的程式設計中，臨界區段（Critical section）指的是一個存取共用資源（例如：共用裝置或是共用記憶體）的程式片段，而這些共用資源有無法同時被多個執行緒存取的特性。

當有執行緒進入臨界區段時，其他執行緒或是行程必須等待（例如：bounded waiting 等待法），有一些同步的機制必須在臨界區段的進入點與離開點實現，以確保這些共用資源是被互斥或的使用，例如：semaphore。

---

UML()Unified Modeling Language)

統一塑模語言

是非專利的第三代塑模和規約語言。UML是一種開放的方法，用於說明、可視化、構建和編寫一個正在開發的、物件導向的、軟體密集系統的製品的開放方法。UML展現了一系列最佳工程實踐，這些最佳實踐在對大規模，複雜系統進行塑模方面，特別是在軟體架構層次已經被驗證有效。

這個語言由葛來迪·布區，伊瓦爾·雅各布森與詹姆士·蘭寶於1994年至1995年間，在Rational Software公司中開發，於1996年，又進一步發展。UML集成了Booch，OMT和物件導向軟體工程的概念，將這些方法融合為單一的，通用的，並且可以廣泛使用的塑模語言。UML打算成為可以對並發和分布式系統的標準塑模語言。

UML並不是一個工業標準，但在Object Management Group的主持和資助下，UML正在逐漸成為工業標準。OMG之前曾經呼籲業界向其提供有關物件導向的理論及實現的方法，以便製作一個嚴謹的軟體塑模語言（Software Modeling Language）。有很多業界的領袖亦真誠地回應OMG，幫助它建立一個業界標準。

在UML系統開發中有三個主要的模型：

• 功能模型：從用戶的角度展示系統的功能，包括使用個案圖。
• 物件模型：採用物件，屬性，操作，關聯等概念展示系統的結構和基礎，包括類別圖、物件圖。
• 動態模型：展現系統的內部行為。包括序列圖，活動圖，狀態圖。

---

Hash

雜湊

雜湊搜尋法是透過一個數學函數來計算或轉換一個鍵值所對應的位址，這種搜尋可以直接且快速的找到鍵值所放的位址

任何透過雜湊搜尋的檔案皆不須經過事先的排序

可以直接：鍵值－＞雜湊函數－＞位址

雜湊的相關名詞

• Bucket(桶)：
  雜湊表中儲存資料的立置，每一個位置對應到唯一的位址，稱為bucket address。一個bucket(桶)就好比是一筆記錄。

• slot(槽)：
  每一個bucket有好幾個儲存區，此儲存區就是slot(槽)。每一個 slot(槽) 即代表記錄中的某個欄位。

  

• Collision(碰撞)：
  當兩筆不同的資料，經過雜湊函數運算後對應到相同的bucket address，稱為Collision(碰撞)。

• Overflow(溢位)：
  如果資料經雜溱函數運算後，所對應的bucket已經滿了，則稱為

• Synonym(同義字)：
  當兩個識別字 I 及 J 的雜湊函數值經過運算後是相同的，則稱 I 及 J 為同義字。

• Loading Factor(載入密度)：
  雜湊空間的載入密度是指識別字的使用數目除以雜湊表內槽的總數。
  

綜觀而論，雜湊函數除了具有快速資料存取的好處外，它還兼具保密的優良效果；亦即當別人沒有你的雜湊函數時，就很難去拿到他所想要的資料了；相反的，若遺失或遺忘雜湊函數，則所有的資料即等於全部遺失了。
雜湊函數還有另外一個問題，那就是一個位址可能同時被兩個或兩個以上的鍵值所對應時，我們稱此現象為碰撞(Collision)。

雜湊方法(Hash method)

直接雜湊(Direct hashing)

鍵值就是位址

• 沒有碰撞(Collision)
  碰撞：不同的鍵值對應到相同的位址
• 問題：鍵值可能不適合當作位址值
  例如：員工號碼通常是一個很大的數字，不適合當位址
  

除法餘數雜湊(Division remainder hashing)

將鍵值除以檔案大小，利用餘數加 1 當作位址
address = key mod list_size + 1
例如，假設檔案大小為 307，員工編號 121267 的位址是：
address = 121267 mod 307 + 1 = 003

• 碰撞有可能發生
  如果檔案大小是質數，碰撞會較少

數字抽離雜湊(Digit extraction hashing)

所選擇的數字是從鍵值中抽取出來，並且用來當作位址

• 碰撞有可能發生
  如果檔案大小是質數，碰撞會較少
  
  
  

碰撞解法

1. 線性探測(Linear Probing)

   線性探測又稱為開放循序定址法(Linear Open Addressing)
   此法是將表格的空間加大以環狀方式使用。

   當發生溢位或碰撞時，則以線性方式從下一個位址繼續探測，若還有空位則將關鍵值存入，否則繼續往下搜尋

   若搜尋完一個循環仍未找到空餘的儲存區，則表示所有位址皆被填滿。

2. 二次方探測(Quadratic Probing)

   當有碰撞發生時，利用非線性的跳躍去找下一個可能的空位置。
   線性探測很容易造成相近的識別字串連在一起而形成叢聚(Cluster)，然後再繼續串連成更大的叢聚(Cluster)，因此二次方探測可以加以改善這種情形。

3. 重雜湊(Rehasing)

   以該位置函數變數在雜湊運算一次，若該位置也被佔用，再以雜湊函數運算一次，直到有空位置。

   當發生溢位或碰撞時，用另一個雜湊函數來找位置

   設置一系列的雜湊函數f1，f2，f3，…，fm；當使用f1產生溢位碰撞時，則改用f2，若又發生溢位時，則改用f3…，直到沒有溢位或碰撞發生。

---

CFG(Context-Free Grammar)

上下文無關文法（英語：context-free grammar，縮寫為CFG），在計算機科學中，若一個形式文法 G = (N, Σ, P, S) 的產生式規則都取如下的形式：V -> w，則謂之。其中 V∈N ，w∈(N∪Σ)* 。上下文無關文法取名為「上下文無關」的原因就是因為字符 V 總可以被字串 w 自由替換，而無需考慮字符 V 出現的上下文。一個形式語言是上下文無關的，如果它是由上下文無關文法生成的（條目上下文無關語言）。

V -> w : 字符 V 總可以被字串 w 自由替換，而無需考慮字符 V 出現的上下文

如文法:

S–->AB
A–->a|t
B––>+CD
C–->a
D––>a
那麼最左推導為:

S––>AB––->aB–->a+CD–->a+aD––->a+aa

例如

---

if(i=0) vs if(i==0)

if(i =0) = if(0) => always false
if(i =1) = if(1) => always true
if(i ==0) => 才會判斷 i 是否為 0來決定 true or false

---

$++$i VS i

$++$

$++$(或

$--$)放前面表示先執行

$++$(或

$--$)

$++$(或

$--$)放後面表示後執行

$++$(或

$--$)

---

String == 跟 equal

String 沒有 new String 物件

String s1 = "String";
String s2 = "String";
此時
System.out.println(s1 == s2 );
==> true
System.out.println(s1.equals(s2));
==> true

• String s1 = "String";
  這種方式，java首先會在緩衝區查找是否有"String"這個常量對象，有就直接將其地址賦給s1，沒有就創建一個"String"，然後將其賦給s1
• String s2 = "String";
  java同樣會在緩衝區中查找"String"，這次能查找到了，因為s1創建了一個"String",所以會將其地址賦給s2

如此，s1 和s2 便有了相同的地址。

• == 在 java 中是比較引用的，即在內存中的地址
  ( == operator checks to see if two objects are exactly the same object.)。

• String 的 equals() 是比較字符串的內容

String 有 new String 物件

String s3 = new String("String");
String s4 = new String("String");
System.out.println(s3 == s4);
==> false
System.out.println(s3.equals(s4));
==> true

• String s3 = new String("String");
  會直接在內存中開闢一個空間存儲一個"String"給s3
• String s2 = "String";
  會直接在內存中開闢一個空間存儲一個"String"給s4

如此，s3 和 s4 不會有相同的地址。,但是內卻是一致的

== 在 java 中是比較引用的，即在內存中的地址
( == operator checks to see if two objects are exactly the same object.)。

String 的 equals() 是比較字符串的內容

---

連結串列（link list) 與 陣列（array)比較

• 連結串列可以動態產生，因此不需要事前定義其大小；陣列需要事前宣告大小。
  使用連結串列結構可以 克服 陣列需要 預先知道資料大小的缺點。
• 連結串列的存取時間比陣列久。
• 陣列可以直接存取任何一個元素，但連結串列不行。
  連結串列失去了陣列隨機讀取的優點。
• 連結串列由於增加了結點的指標域，空間開銷比較大。

1. 當儲存一樣的元素個數且陣列宣告大小適當時，連結串列需要空間 > 陣列需要空間
2. 但在如果陣列宣告過大，就比連結串列容易造成記憶體的浪費。

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---