[音樂播放] 道格·勞埃德:現在你 知道了很多關於陣列, 你也知道了很多關於鍊錶。 我們已經討論 利弊,我們 討論了鍊錶 可以越做越小, 但他們需要更多的大小。 數組是更直接 用,但他們限制在盡可能多 因為我們要設置的大小 在陣列中,最開始 然後我們堅持了下來。 但是,這是,我們已經差不多 用盡我們所有的主題 有關鏈接列表和數組。 或者我們? 也許我們可以做一些事情 更具創造性。 而那種貸出的 哈希表的想法。 因此,在哈希表中,我們要嘗試 結合的陣列與一個鍊錶。 我們將採取優勢 陣列,如隨機訪問, 能夠只是去陣列 單元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。