ArrayList和LinkedList。

ArrayList 就是個(gè)動(dòng)態(tài)數(shù)組兵钮， 它的大小是會(huì)一直變化的霹疫。當(dāng)你放進(jìn)去的東西達(dá)到當(dāng)前容量50% 或者 75%?的時(shí)候，它會(huì)自動(dòng)擴(kuò)大一倍邪意。然后在動(dòng)態(tài)數(shù)組里面找東西什么的非常容易九妈，直接給一個(gè)index，就可以找到那個(gè)東西雾鬼。?

Linkedlist是 分散的內(nèi)存塊萌朱。一個(gè)東西可能存在內(nèi)存0， 另一個(gè)可能存在內(nèi)存100策菜，然后直接用指針指著晶疼，才能準(zhǔn)確知道下一個(gè)數(shù)據(jù)藏在哪個(gè)內(nèi)存里酒贬。Linkedlist 要找東西沒(méi)有那么容易，你沒(méi)辦法給一個(gè)index來(lái)找翠霍，必須從第一個(gè)跳到第二個(gè)跳到第三個(gè)同衣，。壶运。耐齐。才能找到。 但是蒋情，linkedlist刪東西/加進(jìn)新的東西非常簡(jiǎn)單埠况，只要把前一個(gè)節(jié)點(diǎn)的指針指向新來(lái)的東西，新來(lái)的東西指向本來(lái)下一個(gè)節(jié)點(diǎn)就可以了

HashTable, HashMap, HashSet

HashTable和HashMap的區(qū)別棵癣，什么時(shí)候有collision? ??

區(qū)別：One of the major differences between HashMap and Hashtable is that HashMap is non-synchronized whereas Hashtable is synchronized, which means Hashtable is thread-safe and can be shared between multiple threads but HashMap can not be shared between multiple threads without proper synchronization. 【這是一個(gè)很深的概念辕翰，之后慢慢搞”芬辏】

當(dāng)hash function translate two items into the same index (也就是有同樣的hashcode)的時(shí)候喜命， 會(huì)有Collision。 有許多方法來(lái)handle collision, 比如說(shuō)我們可以用Separate Chaining, 也就是放一個(gè)list 在那個(gè)index河劝。 所有hashcode到這個(gè)index的壁榕，往這個(gè)list上面放。 ?還有赎瞎，我們可以用linear 或者 quartic probing, double-hashing.

separate-chaining

然后Hashing里還有一個(gè)很重要的概念牌里，叫做Load Factor.

首先， HashTable會(huì)有兩個(gè)屬性變量务甥，一個(gè)是size牡辽， 一個(gè)是Table Size。 這兩個(gè)很容易混起來(lái) 畢竟都叫做size敞临。

size呢表示Hash Table當(dāng)前裝的東西的數(shù)量态辛。 Table Size 為 Hash Table能夠裝的hashcode的極限容量。不過(guò)size是可以大于Table Size的挺尿！ 因?yàn)楸热鏣able Size 101, 可以放101種Hash code. 而我現(xiàn)在要裝200個(gè)東西進(jìn)去奏黑。 如果Hash function設(shè)計(jì)的好，應(yīng)該會(huì)讓平均每個(gè)Hash code bucket能裝大概2個(gè)東西票髓。

Load Factor 就是 size/TableSize 表示這個(gè)Hash Table平均每個(gè)Bucket 裝多少個(gè)東西攀涵。 就像剛剛那個(gè)例子: 200/101 ≈ 2. ?我們可以設(shè)置一個(gè)mMaxLambda 限制說(shuō)每個(gè)bucket最多只能裝幾個(gè)。

那么Load Factor有什么用洽沟？其實(shí)以故，這個(gè)都是為了盡量避免collision而設(shè)計(jì)的。 比如裆操，我們?nèi)绻幌胍魏蔚腸ollision怒详， 我們?cè)O(shè)置mMaxLambda = 1. 那么Load Factor 只能夠每個(gè)bucket裝一個(gè)東西炉媒。 這樣不就沒(méi)有Collision了嗎。?

但是你table size 100, 我要放200個(gè)昆烁，肯定得一個(gè)bucket裝2個(gè)呀吊骤，然后你mMaxLambda還不讓每個(gè)bucket裝兩個(gè)。 那剩下100個(gè)怎么辦静尼？白粉？？鼠渺？ 這個(gè)時(shí)候鸭巴，HashTable就要resize 自己的大小了。把大小放大一倍拦盹。

當(dāng)然鹃祖，并不一定要限制每一個(gè)bucket 平均裝幾個(gè)。根據(jù)具體問(wèn)題具體實(shí)現(xiàn)普舆。一般裝個(gè)2恬口，3個(gè)平均不是太大的問(wèn)題。在Hash Table里找東西的時(shí)候沼侣， 先hash到一個(gè)bucket的位置祖能，然后順著bucket里的linkedlist找東西。

Linear-probing:?

Quartic Probing:

HashTable和Binary Search Tree华临，什么時(shí)候用哪個(gè)芯杀？當(dāng)你想要根據(jù)一個(gè)數(shù)字范圍找東西的時(shí)候，用BST比較好雅潭，因?yàn)锽ST 結(jié)構(gòu)上來(lái)說(shuō)所有東西都是有一個(gè)大小順序排列的。我們可以用in-order來(lái)按順序拿東西從BST. 但是Hashtable 是沒(méi)有order的却特。

Hashtable是怎么做的呢扶供？HashMap maintains an array of bucket, each bucket has a Entry object which stores key-value pair information. And each entry object also has a Next pointer that goes to the same key different value Entry in linkedlist. ? Whenever the element count of the hashmap reaches the load factor fraction of capacity, the map is resized and capacity is doubled

To find index of bucket, you hash the object first then mod how many buckets to get the index.

HashTable的小實(shí)現(xiàn)：

Constructor 里面初始化table. 一個(gè)List的myTable, 每個(gè)位置里裝一個(gè)linkedlist.

比較Tricky的地方就是Table的定義了。如果是ArrayList裂明， 他的type是什么椿浓？

ArrayList<?> Table = new ArrayList<?>(); 是一個(gè)linkedList. okay。

ArrayList<LinkedList<?>> Table = new ArrayList(LinkedList<?>)

那linkedList又特么是什么類型的闽晦？扳碍？ 這邊就要涉及到Genric 的東西了。

這個(gè)LinkedList 跟普通的linkedlist不太一樣仙蛉，是一個(gè)自定義版本的linkedlist笋敞。

Hash是一個(gè)超級(jí)復(fù)雜的topic：

有兩種hashCode不用自己做。 Integer?and?String?hashCode(). ?但是還是看一下他是怎么實(shí)現(xiàn)的：

Generic Hash Code:

個(gè)人覺(jué)得自己做的HashTable有put, containsKey, remove, hash 這幾個(gè)小功能就可以了荠瘪。?

由于我已經(jīng)完全忘記泛型類的具體語(yǔ)法夯巷，所以copy paste一個(gè)例子作為參考以后：

所以class HashTable<E, V>{..}定義好后赛惩， HashTable<Integer, String> table = new HashTable<Integer, String>(); 就可以造一個(gè)指定類型的Table了。

我比較不確定的是constructor里放些啥東西趁餐，不過(guò)感覺(jué)弄個(gè)自動(dòng)弄個(gè)初始大小就可以了喷兼，也不需要弄什么參數(shù)進(jìn)來(lái)。

我自己草草的做了一個(gè)HashTable后雷， code沒(méi)怎么優(yōu)化季惯，有個(gè)別function甚至直接沒(méi)有調(diào)用。不過(guò)大概的邏輯在臀突，也可以運(yùn)行星瘾。?

幾個(gè)比較重要的點(diǎn)：hash的時(shí)候要mod 一下tableSize，否則hashcode可能會(huì)超出table的range惧辈。

Table的List初始化的時(shí)候是LinkedList<LinkedList<V>> 比如裝String琳状。每一個(gè)bucket是a list of string。我一開始寫一半忘了盒齿，只寫了LinkedList<V> 找錯(cuò)找半天念逞。 還有就是因?yàn)閔ashcode本身就是int，剛好符合array的index边翁。

還有一個(gè)就是ArrayList.size() 取的是實(shí)際的數(shù)量翎承。 我一開始以為取的是capacity。符匾。?

Heap, Stack, PriorityQueue, Queue.

Stack的結(jié)構(gòu)是 先進(jìn)后出叨咖。[很多用處]

Stack的實(shí)現(xiàn)：

Queue: 先進(jìn)先出“〗海【比如可以用在BFS implementation】

Queue 可能的考法是用Stack來(lái)實(shí)現(xiàn)一個(gè)Queue：

實(shí)現(xiàn)的過(guò)程要先知道甸各，queue是先進(jìn)先出的，stack是先進(jìn)后出焰坪，最好腦海里有一個(gè)圖片的樣子到底是個(gè)什么意思趣倾。

其實(shí)很簡(jiǎn)單， 想一個(gè)容器某饰，里面疊一堆書儒恋。 Stack的話就是后放進(jìn)去的先從上面拿出來(lái)。

那么我們要讓先放進(jìn)去的出來(lái)其實(shí)就是把這個(gè)容器反扣在另一個(gè)容器里黔漂。 這樣先進(jìn)stack的書本在反扣中反而會(huì)成為后進(jìn)第二個(gè)stack的诫尽。

Heap 有min Heap以及max Heap:?

min-heap:

max-heap:

我曾經(jīng)覺(jué)得Heap沒(méi)什么大不了的，easy concept對(duì)吧炬守。 結(jié)果面amazon的時(shí)候 烙印直接叫我現(xiàn)場(chǎng)寫一個(gè)Heap...當(dāng)時(shí)直接懵逼牧嫉。 所以，我算是記住這個(gè)東西了劳较，下次再面 什么數(shù)據(jù)結(jié)構(gòu)都可以忘驹止，但是Heap肯定不能忘浩聋。

我當(dāng)時(shí)回答的答案無(wú)比的可笑，我說(shuō)“max Heap就是root永遠(yuǎn)比children 大的結(jié)構(gòu)” ?實(shí)際上臊恋，不止比children大衣洁，比所有subtree都大！ 應(yīng)該準(zhǔn)確的說(shuō)所有node都保持著比sub tree大的屬性抖仅。Also, 記追环颉！３仿环凿！It's binary Tree的Structure！

“In a max heap, the keys of parent nodes are always greater than or equal to those of the children and the highest key is in the root node. In a min heap, the keys of parent nodes are less than or equal to those of the children and the lowest key is in the root node.”

Heap的實(shí)現(xiàn)其實(shí)挺復(fù)雜的放吩，比Hash Table復(fù)雜很多智听，涉及到很多Node pointer之間的調(diào)整。因?yàn)槊看蝘nsert/delete 一個(gè)元素的時(shí)候渡紫，整個(gè)樹的結(jié)果也許都會(huì)發(fā)生變化到推。需要Bubble up/down。

具體來(lái)說(shuō)：

Bubble down:

假設(shè)我要插入一個(gè)東西到min-heap. 一開始我放在leaf. 但是這個(gè)東西如果比parent還小惕澎，他得放在更高一點(diǎn)的位置莉测。所以要一個(gè)一個(gè)check，然后移動(dòng)上去唧喉。所以Heap的插入總是伴隨著run time O(logn) = Height的高度

實(shí)現(xiàn)Heap有兩種方式捣卤。 一種是用array的方式。

一種是用Node八孝， Pointer的方式董朝。 但是兩種方式都是一個(gè)挺龐大的工程。唆阿。

PriorityQueue is implemented using Heap益涧。【我覺(jué)得PriorityQueue跟Heap就是一個(gè)東西驯鳖。。久免。只是priority具體是什么 采用到底是max Heap or min Heap 】