Collections, hashcode, equals

Collections&Arrays
兩者都有提供method搜尋特定元素，搜尋使用的是binarySearch()

1. 成功會回傳找到的element int index
2. 不成功會回傳insertion point的int值 （維持排序的順序下，應該被插入的地方）
3. 正值和0都表示成功搜尋，第一個可以用的插入點為-1，實際的插入點為(-(insertion point) -1)

如：

key map marble pen 
Search apple: -1 //插入點為0，所以是(-(0)-1)=-1

key map marble pen 
Search map: 1 //第一個index找到

key map marble pen 
Search zibra: -5 //插入點為4，所以是(-(4)-1)=-5

Priority Queue
排序方式：用來依照優先權進出的Queue，element優先順序代表被取出的順序

1. 根據element的基本順序
2. 根據Comparator override決定

- offer method和add method是一樣的，都是加資料到queue：

boolean offer(E e)
Inserts the specified element into this priority queue.

boolean add(E e)
Inserts the specified element into this priority queue.

- pool是取queue優先權最高的，且移除，若queue是空的則會回傳null：
Element poll()
Retrieves and removes the head of this queue, or returns null if this queue is empty.

TreeSet/TreeMap (分別實作SortedSet/SortedMap (interface)）
使用自然順序(natural order)排序
在新增element的時候就會使用紅黑樹的吃料結構，保證所有元素都能夠根據自然順序，以升冪排序。也可以藉由Comparable或Comparator來排序。

public class Test3 {
    public static void main(String[] args){
        Set s = new TreeSet(); //Cannot add string and int to the same TreeSet, but HashSet is ok.
        s.add("2");
        s.add(3); //TreeSet is trying do sort, so ClassCastException shows
        s.add("1");
        Iterator it = s.iterator();
        while(it.hasNext()){
            System.out.print(it.next() + " ");
        }
    }
}

以上的範例當新增節點的時候就會有ClassCastException，原因是新增節點的時候就會試著排序。當新增一個String時，TreeSet就會預設這是一顆只會有String的樹，並且以String default的排序法排序。(若今天s是HashSet或LinkedHashSet則不會有任何Exception)
Java1.6版後TreeSet有實作NavigableSet，也就是可以指定其他set來定當原set的backup set

HashSet/HashMap

使用hashcode判斷object要如何被儲存在collections中，用來協助對object的定位

Hashcode&equals
使用“怦然鐔跳整理法”一書來解釋hashcode&equals:
想像你今天要整理房間，根據近藤麻理惠傳授的整理定義，你必須先把東西做分類，比如今天要整理衣服，你就需要把房間所有的衣服拿出來放在衣服堆; 今天要整理書本，你就要把所有的書本拿出來放在書本堆。為了加速等下找到的速度，你不只把衣服拿出來，你還會把衣服簡單分類，比如依照衣服的長度及顏色分成短淺、短深、長淺、長深四種。

而依照衣服的長度及顏色分到哪一堆，這就是一種hascode的實作。
把所有衣服都丟到同一堆，這是hashcode的實作，不過要找到你想要的衣服的時候就會變得非常的慢。所以hascode的實作跟之後找到物品的效率也非常的有關聯。

當你在分類的時候，你可能會發現手上剛剛才把一件“無肩帶美背小可愛-白色”放到短淺類別中，怎麼現在手上又拿著“無肩帶美背小可愛-白色”？這時候你會事不宜遲的把剛剛放進去的那件“無肩帶美背小可愛-白色”丟棄，並把手上的那件放到分類中。因為你對衣服的心動指數在於，一樣的衣服（同樣的名字，這邊每個人可以有不同的定義，也就是equals())只能在一個類別出現一次！！
假設今天都分好類了，接著你開始要做將衣服掛在衣櫃上。當你開始要整理衣服做心動分類的時候，你的姊姊進來問你『欸，你上次跟我借的那件”粉色雪紡碎花荷葉邊短袖開釦V領上衣“是不是還沒還我！？限你三分鐘找出來！』
這時候你會慶幸好險剛剛有先使用衣服長度及深淺分四大類，好險不是只有做衣服堆。所以你開始思考那件短的淺的的“粉色雪紡碎花荷葉邊短袖開釦V領上衣”在哪

1. 你蹲到衣服短淺堆前
2. 你開始一件一件翻，找那間叫做“粉色雪紡碎花荷葉邊短袖開釦V領上衣”的衣服在不在裡面

這兩件事情的翻譯其實是

1. 重新做一次hashcode()(衣服的長度及顏色分類)找出是哪一堆(因此找到了短淺堆)
2. 執行equals()找到自己要的衣服

而這邊的equals就會是衣服的名字。當你在實作equals的時候，裡面的程式碼可能就會是this.name == (cloth(object)).getName()。如此，你就能找到那件“粉色雪紡碎花荷葉邊短袖開釦V領上衣“。當然也有可能找不到，那麽得到就會是null。hashcode（分類）只是告訴你在哪找，沒有保證一定找得到。

以下總結存入讀取步驟：

放入hashtable:

1. 執行hashtable()決定分類
2. 執行equals()看是否在分類有一樣的object

讀取特定物品:

1. 執行hashtable()找出分類
2. 對裡面的每個object執行equals()，若==true代表找到了！