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

資訊專欄INFORMATION COLUMN

js數(shù)據(jù)結(jié)構(gòu)-散列表(哈希表)

call_me_R / 442人閱讀

摘要:散列表散列表,也叫哈希表,是根據(jù)鍵而直接訪問在內(nèi)存存儲位置的數(shù)據(jù)結(jié)構(gòu)。這個映射函數(shù)稱做散列函數(shù),存放記錄的數(shù)組稱做散列表。

散列表
散列表(Hash table,也叫哈希表),是根據(jù)鍵(Key)而直接訪問在內(nèi)存存儲位置的數(shù)據(jù)結(jié)構(gòu)。也就是說,它通過計(jì)算一個關(guān)于鍵值的函數(shù),將所需查詢的數(shù)據(jù)映射到表中一個位置來訪問記錄,這加快了查找速度。這個映射函數(shù)稱做散列函數(shù),存放記錄的數(shù)組稱做散列表。

我們從上圖開始分析

有一個集合U,里面分別是1000,10,152,9733,1555,997,1168

右側(cè)是一個10個插槽的列表(散列表),我們需要把集合U中的整數(shù)存放到這個列表中

怎么存放,分別存在哪個槽里?這個問題就是需要通過一個散列函數(shù)來解決了。我的存放方式是取10的余數(shù),我們對應(yīng)這圖來看

1000%10=0,10%10=0 那么1000和10這兩個整數(shù)就會被存儲到編號為0的這個槽中

152%10=2那么就存放到2的槽中

9733%10=3 存放在編號為3的槽中

通過上面簡單的例子,應(yīng)該會有一下幾點(diǎn)一個大致的理解

集合U,就是可能會出現(xiàn)在散列表中的鍵

散列函數(shù),就是你自己設(shè)計(jì)的一種如何將集合U中的鍵值通過某種計(jì)算存放到散列表中,如例子中的取余數(shù)

散列表,存放著通過計(jì)算后的鍵

那么我們在接著看一般我們會怎么去取值呢?

比如我們存儲一個key為1000,value為"張三" ---> {key:1000,value:"張三"}
從我們上述的解釋,它是不是應(yīng)該存放在1000%10的這個插槽里。
當(dāng)我們通過key想要找到value張三,是不是到key%10這個插槽里找就可以了呢?到了這里你可以停下來思考一下。

散列的一些術(shù)語(可以簡單的看一下)

散列表中所有可能出現(xiàn)的鍵稱作全集U

用M表示槽的數(shù)量

給定一個鍵,由散列函數(shù)計(jì)算它應(yīng)該出現(xiàn)在哪個槽中,上面例子的散列函數(shù)h=k%M,散列函數(shù)h就是鍵k到槽的一個映射。

1000和10都被存到了編號0的這個槽中,這種情況稱之為碰撞。

看到這里不知道你是否大致理解了散列函數(shù)是什么了沒。通過例子,再通過你的思考,你可以回頭在讀一遍文章頭部關(guān)于散列表的定義。如果你能讀懂了,那么我估計(jì)你應(yīng)該是懂了。

常用的散列函數(shù)

處理整數(shù) h=>k%M (也就是我們上面所舉的例子)

處理字符串:

    function h_str(str,M){
        return [...str].reduce((hash,c)=>{
            hash = (31*hash + c.charCodeAt(0)) % M
        },0)
    }

hash算法不是這里的重點(diǎn),我也沒有很深入的去研究,這里主要還是去理解散列表是個怎樣的數(shù)據(jù)結(jié)構(gòu),它有哪些優(yōu)點(diǎn),它具體做了怎樣一件事。
而hash函數(shù)它只是通過某種算法把key映射到列表中。

構(gòu)建散列表

通過上面的解釋,我們這里做一個簡單的散列表

散列表的組成

M個槽

有個hash函數(shù)

有一個add方法去把鍵值添加到散列表中

有一個delete方法去做刪除

有一個search方法,根據(jù)key去找到對應(yīng)的值

初始化
- 初始化散列表有多少個槽
- 用一個數(shù)組來創(chuàng)建M個槽
    class HashTable {
        constructor(num=1000){
            this.M = num;
            this.slots = new Array(num);
        }
    }
散列函數(shù)

處理字符串的散列函數(shù),這里使用字符串是因?yàn)椋瑪?shù)值也可以傳換成字符串比較通用一些

先將傳遞過來的key值轉(zhuǎn)為字符串,為了能夠嚴(yán)謹(jǐn)一些

將字符串轉(zhuǎn)換為數(shù)組, 例如"abc" => [..."abc"] => ["a","b","c"]

分別對每個字符的charCodeAt進(jìn)行計(jì)算,取M余數(shù)是為了剛好對應(yīng)插槽的數(shù)量,你總共就10個槽,你的數(shù)值%10 肯定會落到 0-9的槽里

    h(str){
        str = str + "";
        return [...str].reduce((hash,c)=>{
            hash = (331 * hash + c.charCodeAt()) % this.M;
            return hash;
        },0)
    }
添加

調(diào)用hash函數(shù)得到對應(yīng)的存儲地址(就是我們之間類比的槽)

因?yàn)橐粋€槽中可能會存多個值,所以需要用一個二維數(shù)組去表示,比如我們計(jì)算得來的槽的編號是0,也就是slot[0],那么我們應(yīng)該往slot[0] [0]里存,后面進(jìn)來的同樣是編號為0的槽的話就接著往slot[0] [1]里存

    add(key,value) {
        const h = this.h(key);
        // 判斷這個槽是否是一個二維數(shù)組, 不是則創(chuàng)建二維數(shù)組
        if(!this.slots[h]){
            this.slots[h] = [];
        }
        // 將值添加到對應(yīng)的槽中
        this.slots[h].push(value);
    }  
刪除

通過hash算法,找到所在的槽

通過過濾來刪除

    delete(key){
        const h = this.h(key);
        this.slots[h] = this.slots[h].filter(item=>item.key!==key);
    }
查找

通過hash算法找到對應(yīng)的槽

用find函數(shù)去找同一個key的值

返回對應(yīng)的值

    search(key){
        const h = this.h(key);
        const list = this.slots[h];
        const data = list.find(x=> x.key === key);
        return data ? data.value : null;    
    }
總結(jié)

講到這里,散列表的數(shù)據(jù)結(jié)構(gòu)已經(jīng)講完了,其實(shí)我們每學(xué)一種數(shù)據(jù)結(jié)構(gòu)或算法的時(shí)候,不是去照搬實(shí)現(xiàn)的代碼,我們要學(xué)到的是思想,比如說散列表它究竟做了什么,它是一種存儲方式,可以快速的通過鍵去查找到對應(yīng)的值。那么我們會思考,如果我們設(shè)計(jì)的槽少了,在同一個槽里存放了大量的數(shù)據(jù),那么這個散列表它的搜索速度肯定是會大打折扣的,這種情況又應(yīng)該用什么方式去解決,又或者是否用其他的數(shù)據(jù)結(jié)構(gòu)的代替它。

補(bǔ)充一個小知識點(diǎn)

v8引擎中的數(shù)組 arr = [1,2,3,4,5] 或 new Array(100) 我們都知道它是開辟了一塊連續(xù)的空間去存儲,而arr = [] , arr[100000] = 10 這樣的操作它是使用的散列,因?yàn)檫@種操作如果連續(xù)開辟100萬個空間去存儲一個值,那么顯然是在浪費(fèi)空間。

后續(xù)

后續(xù)可能會去介紹一下二叉樹,另外對于文章有什么寫錯或者寫的不好的地方大家都可以提出來。我會持續(xù)的去寫關(guān)于前端的一些技術(shù)文章,如果大家喜歡的話可以關(guān)注一下,點(diǎn)個贊哦謝謝

文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/100590.html

相關(guān)文章

  • js數(shù)據(jù)結(jié)構(gòu)和算法(五)字典和列(hash)

    摘要:哈希表也是種數(shù)據(jù)結(jié)構(gòu),它可以提供快速的插入操作和查找操作。一個更好的散列函數(shù)為了避免碰撞,首先要確保散列表中用來存儲數(shù)據(jù)的數(shù)組其大小是個質(zhì)數(shù),這和計(jì)算散列值時(shí)使用的取余運(yùn)算有關(guān)。散列函數(shù)將學(xué)生里的數(shù)字相加,使用函數(shù)計(jì)算出散列值。 什么是字典結(jié)構(gòu)? 字典是以鍵值對形式存儲數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu),就像電話號碼薄里的名字和電話號碼那樣的一一對應(yīng)的關(guān)系。 javascript的Object類就是以...

    Hegel_Gu 評論0 收藏0
  • 《Javascript數(shù)據(jù)結(jié)構(gòu)和算法》筆記-「字典和

    摘要:我經(jīng)常在業(yè)務(wù)代碼中把數(shù)據(jù)處理成這種字典的數(shù)據(jù)結(jié)構(gòu)獲取的方法哈希表在學(xué)習(xí)了類之后,我們會學(xué)習(xí)散列表,也就是哈希表。 《Javascript數(shù)據(jù)結(jié)構(gòu)和算法》筆記-「字典和散列表」 集合、字典、散列表存儲的都是「不重復(fù)」的數(shù)據(jù)結(jié)構(gòu) 集合:我們更關(guān)注每一個元素的值,并把其作為主要元素 字典:我們用[鍵,值]的形式來存儲數(shù)據(jù) 散列表: 跟字典類似,也會是用[鍵,值]的形式來存儲數(shù)據(jù) 但是「字...

    wenyiweb 評論0 收藏0
  • js算法入門(2)--哈希

    摘要:簡介哈希表又被稱為散列表,可能是翻譯的問題好多書上一會兒稱散列一會兒稱哈希,更有甚者煞有介事的對此進(jìn)行區(qū)分。實(shí)現(xiàn)哈希表我們將要實(shí)現(xiàn)這個類分別實(shí)現(xiàn)插入查找刪除打印等方法。 1.簡介 哈希表(hash table)又被稱為散列表,可能是翻譯的問題好多書上一會兒稱散列一會兒稱哈希,更有甚者煞有介事的對此進(jìn)行區(qū)分。經(jīng)過簡單的搜索(wiki鏈接)發(fā)現(xiàn)這兩個詞是一回事。由此可見學(xué)好英語是多么重要。...

    Lavender 評論0 收藏0
  • 數(shù)據(jù)結(jié)構(gòu)與算法——

    摘要:散列表其實(shí)是基于數(shù)組實(shí)現(xiàn)的,可以說,沒有數(shù)組就沒有散列表。根據(jù)下圖你更能理解散列表哈希函數(shù)結(jié)合上面的理解,你應(yīng)該可以想到,其實(shí)散列表的關(guān)鍵就在于哈希函數(shù)的實(shí)現(xiàn)。 1. 什么是散列表? 散列表(Hash Table)又叫做哈希表,是一種很常用的數(shù)據(jù)結(jié)構(gòu)。散列表其實(shí)是基于數(shù)組實(shí)現(xiàn)的,可以說,沒有數(shù)組就沒有散列表。先來舉一個簡單的例子,來認(rèn)識一下什么是散列表。 假如在學(xué)校的運(yùn)動會上,每個運(yùn)動...

    VincentFF 評論0 收藏0
  • 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之字典和

    摘要:小結(jié)實(shí)現(xiàn)了字典和哈希表感覺沒有想象中那么困難,當(dāng)然這還是開始。 本系列所有文章:第一篇文章:學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之棧與隊(duì)列第二篇文章:學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之鏈表第三篇文章:學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之集合第四篇文章:學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之字典和散列表第五篇文章:學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之二叉搜索樹 字典 不是新華字典哦,這里的字典也稱作_映射_,是一種數(shù)據(jù)結(jié)構(gòu),跟set集合很相似的一種數(shù)據(jù)結(jié)構(gòu),都可以用來...

    Heier 評論0 收藏0

發(fā)表評論

0條評論

call_me_R

|高級講師

TA的文章

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