[音樂播放]
>> 道格·勞埃德：現在你 知道了很多關於陣列，
你也知道了很多關於鍊錶。
我們已經討論 利弊，我們
討論了鍊錶 可以越做越小，
但他們需要更多的大小。
數組是更直接 用，但他們限制在盡可能多
因為我們要設置的大小 在陣列中，最開始
然後我們堅持了下來。
>> 但是，這是，我們已經差不多 用盡我們所有的主題
有關鏈接列表和數組。
或者我們？
也許我們可以做一些事情 更具創造性。
而那種貸出的 哈希表的想法。
>> 因此，在哈希表中，我們要嘗試 結合的陣列與一個鍊錶。
我們將採取優勢 陣列，如隨機訪問，
能夠只是去陣列 單元4或數組元素8
而不必遍歷整個。
這是相當快的，對不對？
>> 但是，我們也希望有我們的數據 結構能夠增大和縮小。
我們不需要，我們不 要進行限制。
我們希望能夠 添加和刪除的東西
很容易，而如果你還記得， 是與一個陣列很複雜。
我們可以把這種 新事物的哈希表。
>> 如果正確實施， 樣的，我們正在做
兩個數據的優點 你已經看到了結構，
數組和鍊錶。
插入可以開始 趨向THETA 1。
西塔我們還沒有真正討論過， 但THETA只是平均情況下，
什麼實際將要發生。
你不會總是會 有最壞的情況下，
而你並不總是有 在最好的情況下，有啥
一般情況下？
>> 那麼平均的插入 為哈希表
可以開始接近恆定的時間。
和刪除可以得到 接近恆定的時間。
和查找可以得到 接近恆定的時間。
That's--我們沒有一個數據 結構尚未能做到這一點，
所以這已經聽上去 像一個非常偉大的事情。
我們真的減輕了 每個自身的缺點。
>> 要達到這種性能 升級雖然，我們
需要重新思考我們如何加入 數據到該結構。
具體來說，我們要的 數據本身告訴我們
它應該在的結構。
如果我們再需要看它是否在 結構，如果我們需要找到它，
我們想看看數據 再次，並能夠有效地，
使用數據，隨機訪問它。
只是通過查看 數據，我們應該有
那裡正是我們的想法 會發現它在散列表中。
>> 散列現在的缺點 表是，他們是真的
非常糟糕的訂購或排序數據。
而事實上，如果你開始 用它們來訂貨或排序
數據你失去所有的 優點以前
有在插入和刪除的條款。
的時間變得更接近 THETA的n，我們已經基本上
退步成一個鍊錶。
因此，我們只希望使用哈希 如果我們不關心表
數據是否被排序。
對於上下文中 你會使用他們在CS50
你可能不關心 該數據排序。
>> 所以一個哈希表是一個組合 的兩個不同的片
與我們熟悉。
第一個是一個函數，它 我們通常所說的哈希函數。
並且散列函數是要 返回一些非負整數，其
我們通常所說的哈希碼，好不好？
第二件是一個數組，這是 有能力的類型，我們的存儲數據
要放置到數據結構中。
我們將暫緩對 鍊錶元素現在
和剛開始的基本知識 哈希表來讓你的頭周圍，
然後我們將可能打擊 你的心一點點，當我們
結合數組和鍊錶在一起。
>> 其基本思路雖然 是我們採取了一些數據。
我們通過運行數據 散列函數。
和因此數據被處理 它吐出一個數字，好不好？
然後用這個數字 我們只存儲數據
我們要存儲在 陣列在那個位置。
因此，例如，我們有可能 串該哈希表。
它有它10個元素，所以 我們可以在上面安裝10串。
>> 比方說，我們要散列約翰。
因此，約翰的數據，我們要插入 這個哈希表的地方。
我們在哪裡放呢？
那麼通常與 陣列到目前為止，我們可能
將其放在數組位置0。
但是現在我們有了這個新的散列函數。
>> 而且，我們說，我們跑約翰 通過這個哈希函數
並且它吐出4。
那麼這就是我們 會希望把約翰。
我們希望把約翰數組位置 4，因為如果我們散列約翰again--
讓我們後來說，我們 要搜索，看看
如果約翰存在於該散列 table--所有我們需要做的
通過相同的散列運行它 功能，讓4號出來，
並且能夠找到John 立即在我們的數據結構。
這是相當不錯的。
>> 比方說，我們現在做的這個 再次，我們要散列保羅。
我們想增加保 到這個哈希表。
比方說，我們這次運行 保羅通過散列函數，
生成的哈希碼為6。
現在好了，我們可以把保羅 在陣列位置6。
如果我們需要仰視是否 保羅是該哈希表中，
我們需要做的就是運行保 通過散列函數再次
我們會得到6出來了。
>> 然後我們只要看看 在數組位置6。
保羅嗎？
如果是這樣，他的哈希表中。
保羅不是嗎？
他不是哈希表所示。
這是非常簡單的。
>> 現在，你如何定義一個散列函數？
那麼真的沒有限制的 可能的散列函數的數量。
其實有一些真的， 真正好的在互聯網上。
有一些真的， 真正糟糕的在互聯網上。
它也很容易 寫一個壞的。
>> 是什麼讓一個很好的 散列函數，對不對？
好一個良好的散列函數應該 只使用被散列數據，
和所有的數據被散列。
所以，我們不希望使用anything-- 我們不會將任何東西
別人比數據等。
我們要使用的所有數據。
我們不希望只使用了一塊 這一點，我們要使用它的全部。
哈希函數應該 同樣是確定性的。
這是什麼意思？
那麼這意味著我們每一次 通過完全相同的數據片
到哈希函數，我們總是 得到相同的哈希碼了。
如果我通過約翰進入 散列函數，我得到了4。
我應該能夠做到一萬 次，我會永遠得到4。
因此，沒有隨機數有效 可以參與我們的散列tables--
在我們的哈希函數。
>> 散列函數也應 均勻地分佈數據。
如果每次通過運行數據 哈希函數你得到的哈希碼0，
這可能沒那麼大吧？
你可能想大 一系列的散列碼。
同樣的事情可以傳播 從整個表。
並且也將是巨大的，如果真的 類似的數據，像約翰和喬納森，
也許被攤開來衡量 在散列表中的不同位置。
這將是一個很好的優勢。
>> 這裡有一個散列函數的例子。
我前面寫了這一個。
這不是一個特別 好的哈希函數
其原因並不真的 熊進入現在。
但是你看這是怎麼回事呢？
好像我們在聲明一個變量 稱為sum並將其設置等於0。
然後，顯然我在做什麼 只要的strstr [J]不等於
反斜杠0。
我在做什麼呢？
>> 這基本上只是一個 實施[的方法是什麼？ STRL？]
並檢測當你 達到串的結尾。
所以我沒有真正 計算字符串的長度，
我只是用我的時候我打的 反斜杠字符0我知道
我已經到達字符串的結尾。
然後，我會繼續 通過該字符串迭代，
加入的strstr [j]的概括，然後再在 到頭來會返回一個總和模
HASH_MAX。
>> 基本上所有該散列 功能正在做的是加入了
所有的ASCII值 我的字符串，然後它的
返回一些哈希碼 通過HASH_MAX改裝成。
這可能是大小 我的數組，對不對？
我不希望是越來越哈希 如果我的數組大小​​為10的代碼，
我不希望得到 出散列碼11，12，
13，我不能把東西放進 陣列的那些位置，
這將是非法的。
我遭受分段錯誤。
>> 現在，這裡是另一種快速的一邊。
通常你可能不會 要編寫自己的散列函數。
它實際上是一個有點 一門藝術，而不是一門科學。
而且有很多是進入他們。
互聯網，就像我說的，是全 真正好的哈希函數，
你應該使用互聯網 找到散列函數，因為它是真的
只是一種不必要的 浪費時間來創建自己的。
>> 你可以寫簡單的人 用於測試目的。
但是，當你真正要 開始散列數據和將其存儲
到一個哈希表你 可能會想
使用中生成的一些功能 對你來說，存在於互聯網上。
如果你只是確保 舉你的源代碼。
有沒有理由 這裡抄襲任何東西。
>> 計算機科學界是 肯定是增長的，真值
開源的，這真的很重要 舉你的源代碼，使人們
可以歸屬為 他們是工作
做對社會的利益。
所以，永遠是sure-- 而不是只為哈希
功能，但一般當 使用代碼從外部源，
始終引用源。
給予信貸是誰做的人 一些工作，所以你不必。
>> 好讓我們重溫這 哈希表一秒鐘。
這是我們離開 我們關閉後插入
約翰和保羅到這個哈希表。
你在這裡看到的一個問題？
您可能會看到兩個。
但是，在特殊的，你 看到這個可能出現的問題？
>> 如果我湊林戈，它 事實證明，處理後
通過散列函數數據 林戈也產生了哈希碼6。
我已經在有數據 hashcode--陣列位置6。
因此，它可能會成為一個位 現在我的問題，對不對？
>> 我們把這種衝突。
和碰撞發生當兩個 數據塊通過相同的散列運行
函數產生相同的哈希碼。
想必大家仍然希望得到既 個數據到哈希表中，
否則我們也不會運行林戈 任意地通過散列函數。
我們大概是想獲得 林戈到該陣列。
>> 我們是如何做到的，雖然，如果他 和保羅這兩個產量哈希碼6？
我們不希望覆蓋保羅， 我們希望保羅在那裡了。
因此，我們需要找到一種方式來獲得 元素融入到哈希表
仍然保留我們的快速 插入和快速查找。
而對付它的方法之一是 做一些所謂的線性探測。
>> 使用這種方法，如果我們有一個 碰撞，好了，我們怎麼辦？
嗯，我們不能把他放在數組位置 6，或生成任何哈希碼，
讓我們把他的哈希碼加1。
如果這完全讓我們 把他放在哈希碼加2。
這之中的好處，如果他 不完全是，我們認為他是，
而且我們要開始搜索， 也許我們不必走得太遠。
或許我們不必以搜索 哈希表的所有n個元素。
也許我們需要搜索 他們夫婦。
>> 所以我們仍然趨向 即平均情況是接近1比
接近N，所以也許這會工作。
因此，讓我們看看這個 可能工作在現實中。
而讓我們看看，也許我們可以檢測 這裡可能出現的問題。
>> 比方說，我們湊巴特。
所以，現在我們要運行一個新的集 通過哈希函數的字符串，
我們通過哈希運行巴特 函數，我們得到哈希碼6。
我們來看看，我們看到6 空的，所以我們可以把巴特那裡。
>> 現在，我們哈希麗莎和 還生成散列碼6。
現在好了，我們正在使用這種 線性探測，我們開始在6方法，
我們看到，6已滿。
我們不能把麗莎6。
因此，我們下一步怎麼走？
讓我們去7。
7的空白，使作品。
所以，讓我們把麗莎那裡。
>> 現在，我們哈希荷馬，我們得到7。
確定好我們知道，7的全 現在，所以我們不能把荷馬那裡。
因此，讓我們去8。
8可用？
是啊，和8的接近7，因此，如果 我們要開始尋找我們
不會有走的太遠。
因此，讓我們把荷馬在8。
>> 現在，我們哈希Maggie和 返回3，謝天謝地
我們能夠只把馬吉在那裡。
我們沒有做任何 那種探測的。
現在，我們哈希瑪吉，和 瑪吉也返回6。
>> 那麼6已滿，7已滿，8已滿， 9，沒事感謝上帝，9是空的。
我可以把瑪吉9。
我們已經能夠看到，我們開始 有這樣的問題，即現在我們
開始舒展的東西那種 對遠離他們的哈希碼。
與1的THETA，即平均 案件是恆定的時間，
開始變得有點緩慢 - 開始傾向於多一點
對n個THETA。
我們開始失去 利用哈希表。
>> 這個問題，我們剛才看到 一些所謂的集群。
而什麼是真正不好 集群是，一旦你現在
有兩個要素是並排 方面，它使得它更容易，
你有雙倍的 偶然的機會，你要去
有另一個碰撞 與該集群，
和群集將由一個生長。
你會不斷擴張 你具有碰撞可能性。
而最終它只是糟糕 作為不排序的數據在所有。
>> 另一個問題是，雖然我們 不過，到目前為止了這一點，
我們剛剛排序 了解什麼是哈希表，
我們仍然只有空間10串。
如果我們想繼續哈希 斯普林菲爾德的公民，
我們只能拿到其中10個在那裡。
如果我們嘗試添加一個11或12， 我們沒有地方放了。
我們可能只是在不停的旋轉 圈試圖找到一個空白點，
我們也許卡住 在無限循環。
>> 因此，這種借給想法 一種叫做鏈接。
而這正是我們要帶給 鍊錶放回圖片。
如果有什麼，而不是僅僅存儲 數據本身的陣列中，
該數組的每個元素可以 持多個數據？
嗯，這是沒有意義的，對不對？
我們知道，一個數組只能 hold--一個陣列的每個元素
只能容納一塊 的該數據類型的數據。
>> 但是，如果該數據類型 是一個鍊錶，對吧？
那麼，如果每 數組的元素是
的指針的一個鍊錶頭？
然後我們可以建立 這些鍊錶
和他們成長隨意， 因為鍊錶允許
我們擴大和縮小了很多 靈活不是一個數組一樣。
因此，如果我們現在用的是什麼， 我們利用這一點，對不對？
我們開始種植這些鏈 這些陣列單元。
>> 現在我們可以容納無限 的數據量，或不無限的，
的任意量 數據，到我們的哈希表
而沒有運行到 碰撞的問題。
我們還淘汰 集群做這個。
而同時我們知道，當我們插入 成一個鍊錶，如果你還記得
從我們的視頻鏈接列表，單 鍊錶和雙向鍊錶，
這是一個固定時間操作。
我們只是增加了前面。
>> 而對於查查，還有我們所知道的 在鍊錶查找
可能是一個問題，對不對？
我們必須通過搜索 它從開始到結束。
有沒有隨機 訪問在一個鍊錶。
但是，如果不是有一個鏈接 列表，查找會為O n個，
我們現在有10鍊錶， 或1000鍊錶，
現在它除以10，O n的， 或N鄰除以1,000。
>> 雖然我們談論 理論上約複雜性
不顧常數，在現實 世界這些事情實際上很重要，
對不對？
事實上，我們會發現 這種情況的發生
運行速度快10倍， 或快1000倍，
因為我們分配一個長 鏈跨越1000小型連鎖店。
所以，每次我們有時間來搜​​索 通過這些鏈，我們可以之一
無視999鏈，我們不關心 約，只是尋找一​​個。
>> 這是對平均 是1000倍更短。
因此，我們仍然有幾分 趨向於這種平均情況
的是恆定時間，但 只是因為我們正在利用
由一些巨大的常數因子分。
讓我們來看看，這可能 實際上看起來雖然。
因此，這是哈希表，我們有 之前我們宣布一個哈希表
是能夠存儲10串。
我們不打算這樣做了。
我們已經知道了 該方法的局限性。
現在，我們的哈希表將是 10個節點，指針數組
到鍊錶的頭。
>> 而現在它是空。
這10個三分球中的每一個為空。
有沒有在我們的 哈希表現在。
>> 現在，讓我們開始把一些 事情到這個哈希表。
而讓我們看看這種方法是 將有利於我們一點點。
現在，讓我們湊喬伊。
我們將運行字符串喬伊通過 散列函數和我們返回6。
那麼我們現在做什麼？
>> 現在好了，正與鍊錶， 我們不是在與陣列。
當我們正在努力 用鍊錶我們
知道我們需要動態地啟動 分配空間和建築鏈。
這就是那種how--這些都是核心 建立一個鍊錶的元素。
因此，讓我們動態 分配空間，容祖儿，
然後讓我們把他加為鏈條。
>> 所以，現在看看我們所做的。
當我們哈希喬伊，我們得到了哈希碼6。
現在指針數組位置6 指向的鏈接的列表的頭部，
而現在它是唯一 鍊錶元件。
並且在該節點 鍊錶是喬伊。
>> 因此，如果我們需要仰視喬伊 後來，我們只需再次散列喬伊，
我們再次拿到6，因為我們的 散列函數是確定性的。
然後我們開始在頭 鍊錶指出
由數組位置 6，我們可以遍歷
跨越，試圖找到喬伊。
如果我們建立我們 有效哈希表，
而我們的散列函數有效 很好地分發數據，
平均每個那些鏈接 在每個數組位置列表
將1/10如果尺寸我們 剛它作為一個巨大的
鍊錶中的一切。
>> 如果我們分發巨額鏈接 在10個鏈接列表清單
每個列表將大小的1/10。
就這樣，10次快 進行搜索。
因此，讓我們再次做到這一點。
現在，讓我們湊羅斯。
>> 而我們說羅斯，當我們做到這一點 我們得到的哈希碼為2。
現在好了，我們動態地分配 新的節點，我們把羅斯在那個節點，
我們現在說的數組位置 2，而不是指向空，
指向的鏈接頭 名單的唯一節點是羅斯。
我們可以這樣做一個更多的時間，我們 可以散列Rachel和獲得哈希碼4。
malloc的一個新的節點，把瑞秋 節點，並說一個數組位置
4現在指向頭部 鍊錶的
唯一的元素恰好是瑞秋。
>> OK，但如果發生了什麼 我們有一個碰撞？
讓我們來看看我們是如何處理衝突 採用獨立鏈接方法。
讓我們湊菲比。
我們得到的哈希碼6。
在前面的例子中，我們只是 存儲陣列中的字符串。
這是一個問題。
>> 我們不希望給揍 喬伊，我們已經
可見，我們可以得到一些集群 如果我們試圖和問題的步驟
通過和探頭。
但是，如果我們只是種 這種對待同樣的道理，對不對？
這就像將一個元素 到的一個鍊錶的頭部。
讓菲比的只是malloc的空間。
>> 我們會說菲比的下一個指針指向 到舊頭鍊錶，
然後6只指向 鏈接列表的新掌門人。
而現在看，我們已經在改變了菲比。
現在，我們可以存儲兩個 與hashCode 6個元素，
我們沒有任何問題。
>> 這幾乎是所有 還有就是鏈接。
而且鏈接是絕對 該方法是
將是最有效的你，如果 你是存儲在一個哈希表中的數據。
但這種組合 數組和鍊錶
在一起，以形成一個哈希表真 極大地提高你的能力
來存儲大量的數據，和 非常迅速和有效地搜索
通過該數據。
>> 但還有一個更 數據結構在那裡
甚至可能會有點 在保障方面更好
我們的插入，缺失，和 仰望倍甚至更快。
我們會看到，在嘗試視頻。
我是道格·勞埃德，這是CS50。