国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

《Javascript數據結構和算法》筆記-「字典和散列表」

wenyiweb / 2255人閱讀

摘要：我經常在業務代碼中把數據處理成這種字典的數據結構獲取的方法哈希表在學習了類之后，我們會學習散列表，也就是哈希表。

《Javascript數據結構和算法》筆記-「字典和散列表」

集合、字典、散列表存儲的都是「不重復」的數據結構

集合：我們更關注每一個元素的值，并把其作為主要元素

字典：我們用[鍵,值]的形式來存儲數據

散列表： 跟字典類似，也會是用[鍵,值]的形式來存儲數據

但是「字典」和「散列表」的實現方式略有不同。

字典

字典也稱作映射。我覺得這種數據結構，其實在業務代碼中的應用很常見。

與Set類似，ES6同樣實現了一個Map類，即我們所說的字典

字典的大致骨架

    function Dictionary(){
        var items = {}
    }

    this.set = function(key,value){}
    this.get = function(key){}
    this.delete = function(key){}
    this.has = function(key){}
    this.clear = function(){}
    this.size = function(){}
    this.keys = function(){}  // 將字典所包含的所有鍵，以一個數組返回
    this.values = function(){}  // 將字典所包含的所有值，以一個數組返回

字典類的實現，十分簡單就直接粘貼全部代碼了。

我覺得在JS中，對象本身就可以作為字典來使用。我經常在業務代碼中把數據處理成這種字典的數據結構

        function Dictionary() {
            var items = {}

            this.has = function ( key ) {
                return items.hasOwnProperty( key )
            }

            this.set = function ( key, value ) {
                items[ key ] = value
            }

            this.delete = function ( key ) {
                if ( this.has( key ) ) {
                    delete items[ key ]
                    return true
                }
                return false
            }

            this.get = function ( key ) {
                if ( this.has( key ) ) {
                    return items[ key ]
                } else {
                    return undefined
                }
            }

            this.values = function(){
                return Object.values(items)
            }

            this.keys = function(){
                return Object.keys(items)
            }

            this.clear = function(){
                this.items = {}
            }

            this.size = function(){
                return this.keys().length
            }

            this.getItems = function(){   // 獲取items的方法
                return items
            }
        }

        var dictionary = new Dictionary()

        dictionary.set("Gandalf","gandalf@email.com")
        dictionary.set("John","johnsnow@email.com")
        dictionary.set("Tyrion","tyrion@email.com")

        console.log(dictionary.has("Gandalf"))
        console.log(dictionary.size())
        console.log(dictionary.keys())
        console.log(dictionary.values())
        console.log(dictionary.get("Tyrion"))
        dictionary.delete("John")
        console.log(dictionary.keys())
        console.log(dictionary.values())
        console.log(dictionary.getItems())
哈希表

在學習了Dictionary類之后，我們會學習散列表，也就是哈希表。它是Dictionary類的另外一種實現方式

我在讀到這里時，對于「字典」和「哈希表」2個慨念之間的區別還沒弄清，當然書中也沒有太多解釋。

所以這里，我寫記錄一下自己查閱資料后的個人理解

「字典」指的是Key-Value這種存儲數據的結構

那么哈希表也是字典，但是它是用另外的一種實現方式來做的。

那么我們我為什么要使用這種方式來實現「字典」呢，是不是字典存在某種缺點呢？

是的，比如說這樣的一組字典數據

k1, k2, k3, k4, k4 ....
v1, v2, v3, v4, v5 ....

當你輸入key，命令電腦查詢key對應的value時，電腦其實是沒法立刻找到key所對應的value呢

看上去是直接根據key得到value，但實際上電腦還是需要遍歷k1、k2、k3去比較kn是否等于key。如果是的話就取出對應的值

那么為了省去這個遍歷的過程，才想到用哈希表來實現「字典」

哈希表利用數組實現「字典」這種數據結構，那么用數組來實現字典的話，用戶傳入的key對應哪個索引呢？所以我們需要一個「散列算法」

「散列算法」，可以求出這個key在數組里對應的位置，用哈希表實現的目的就是盡可能快地在字典中找到一個值。

function HashTable(){
    let table = []

    // 散列算法
    var loseloseHashCode = function(key){
        var hash = 0;
        for(var i = 0 ; i
哈希表的key值沖突

我們哈希表的散列算法，是為求出用戶傳入的key所對應的一個索引


那么這個索引是有可能重復的，一旦重復就會導致后面的值覆蓋前面的值。


這種情況，叫做哈希表的沖突。所以我們了解2種處理沖突的方法原理



分離鏈接: 把數組的每一個元素都實例成鏈表結構。這樣key相同的值，也可以用單鏈表的形式不斷存儲。不會覆蓋


線性探查: 當用散列算法求出的這個索引index重復時，就index++，直到index不重復為止。


實現更好的散列函數

之前實現的"lose lose"散列函數，用來求值其實是非常容易產生key沖突的。


如果經常沖突的話，那么插入和查詢一個元素的時間就會變慢(性能變差)


所以一個優秀的散列算法，應該是可以盡可能少出現沖突的


這里給出一個比較好的社區的實現。至于為什么這種算法,可以減少沖突我也不太理解，


可能是hash是質數，然后質數*33,最后在跟1013取模的話，不太會產生一樣的余數，這個感覺是數學問題。


var djb2HashCode = function(key){
    var hash = 5381

    for(var i = 0 ; i < key.length ; i++){
        hash = hash*33 + key.charCodeAt(i)
    }

    return hash % 1013
}



簡單回顧一下，集合、字典、哈希表吧


首先他們的元素都是不重復的



集合： 是無序的，[value value]的形式的一組數據結構


字典： 是由一對對 [key-value] 組成的數據結構


哈希表： 是字典的另外一種實現方式，優點在于可能更快的根據key取到value



記錄一下書中沒搞清楚的小疑問：


《javascript數據結構和算法》中多次提到「順序數據結構」和「非順序數據結構」的慨念，并表示

- 「順序數據結構」：棧、隊列、數組、鏈表、集合
- 「非順序數據結構」: 散列表 、 樹

可是我覺得鏈表、集合是無序的，數組是有序的呀

這個「順序數據結構」似乎并不是指的在內存中存儲形式。問題先記下，回頭再查把

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/108733.html

相關文章

  • 《JavaScript數據結構與算法》筆記——第7章 字典和散列表

    摘要：在字典中，存儲的是鍵，值，集合可以看作值，值的形式存儲元素，字典也稱為映射方法描述備注向字典中添加新元素通過某個鍵值從字典中移除對應的數據值判斷某個鍵值是存在于這個字典中通過鍵值獲取對應的數據值返回字典所有元素的數量刪除字典中所有元素將字典 在字典中，存儲的是[鍵，值]，集合可以看作[值，值]的形式存儲元素，字典也稱為映射 方法 描述 備注 set(key,...

    zorro 評論0 收藏0

  • CSS技巧

    摘要：技巧使你的更加專業這是上關于技巧的一篇譯文，另外你也可以在本項目看到原文。列舉了一些很實用的技巧，比如給空內容的標簽添加內容，逗號分隔列表等等。排序算法看源碼，把它背下來吧排序算法的封裝。主要幫助初學者更好的掌握排序算法的實現。 成為專業程序員路上用到的各種優秀資料、神器及框架 成為一名專業程序員的道路上，需要堅持練習、學習與積累，技術方面既要有一定的廣度，更要有自己的深度。 Java...

    DangoSky 評論0 收藏0

  • CSS技巧

    摘要：技巧使你的更加專業這是上關于技巧的一篇譯文，另外你也可以在本項目看到原文。列舉了一些很實用的技巧，比如給空內容的標簽添加內容，逗號分隔列表等等。排序算法看源碼，把它背下來吧排序算法的封裝。主要幫助初學者更好的掌握排序算法的實現。 成為專業程序員路上用到的各種優秀資料、神器及框架 成為一名專業程序員的道路上，需要堅持練習、學習與積累，技術方面既要有一定的廣度，更要有自己的深度。 Java...

    zgbgx 評論0 收藏0

  • CSS技巧 - 收藏集 - 掘金

    摘要：筆者作為一位，將工作以來用到的各種優秀資料神器及框架整理在此，畢竟好記性不如爛鍵盤，此前端知識點大百科全書前端掘金，，不定期更新技巧前端掘金技巧，偶爾更新。計算數組的極值技巧使你的更加專業前端掘金一個幫你提升技巧的收藏集。 CSS 樣式畫各種圖形 - 前端 - 掘金下面是一些我在 CSS 中經常用到的圖案，還有一些是在css-tricks看到的。記錄一下，以后會用到。會持續更新… 一、...

    Jonathan Shieber 評論0 收藏0

  • CSS技巧 - 收藏集 - 掘金

    摘要：筆者作為一位，將工作以來用到的各種優秀資料神器及框架整理在此，畢竟好記性不如爛鍵盤，此前端知識點大百科全書前端掘金，，不定期更新技巧前端掘金技巧，偶爾更新。計算數組的極值技巧使你的更加專業前端掘金一個幫你提升技巧的收藏集。 CSS 樣式畫各種圖形 - 前端 - 掘金下面是一些我在 CSS 中經常用到的圖案，還有一些是在css-tricks看到的。記錄一下，以后會用到。會持續更新… 一、...

    SHERlocked93 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<