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

資訊專欄INFORMATION COLUMN

學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之字典和散列表

Heier / 1248人閱讀

摘要:小結(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),都可以用來存儲(chǔ)無序不重復(fù)的數(shù)據(jù)。不同的地方是集合以[值,值]的形式存儲(chǔ),而字典則是以[鍵,值]或者叫作{key: value}的形式。

用JavaScript實(shí)現(xiàn)字典

先實(shí)現(xiàn)一個(gè)構(gòu)造函數(shù):

function Dictionary () {
  var items = {}
}

字典需要實(shí)現(xiàn)以下方法:

set(key, value):向字典中添加新元素

remove(key):通過使用key來從字典中移除對應(yīng)元素

has(key):通過key來判斷字典中是否有該元素

get(key):通過key來找到特定的數(shù)值并返回

clear():清空字典

size():返回字典包含元素的數(shù)量

keys():返回字典所包含的所有鍵名,以數(shù)組形式返回

values():同上一個(gè)方法一樣,只不過鍵名換成了數(shù)值,也是以數(shù)組形式返回

實(shí)現(xiàn)has

因?yàn)楹竺娴姆椒ǘ家玫絟as,所以先實(shí)現(xiàn)這個(gè)方法

this.has = function (key) {
  // 書上用的是in操作符來判斷,但是in對于繼承來的屬性也會(huì)返回true,所以我換成了這個(gè)
  return items.hasOwnProperty(key)
}
實(shí)現(xiàn)set

沒啥好說的,簡單的賦值

this.set = function (key, value) {
  items[key] = value
}
實(shí)現(xiàn)remove

首先判斷key是否屬于該字典,然后再刪除

this.remove = function (key) {
  if (this.has(key)) {
    delete items[key]
    return true
  }
  return false
}
實(shí)現(xiàn)values

返回由數(shù)值組成的數(shù)組

this.values = function () {
  var values = []
  for (var k in items) {
    if (items.has(k)) {
      values.push(items[k])
    }
  }
  return values
}
實(shí)現(xiàn)其他的方法

其他的比較簡單,和集合的方法實(shí)現(xiàn)類似,我就直接貼源代碼了

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

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

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

this.getItems = function () {
  return items
}

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

源代碼在此:

字典的實(shí)現(xiàn)-源代碼

散列表

關(guān)于散列表的定義,這里摘抄一下維基百科的解釋:

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

可以理解為,數(shù)據(jù)中的鍵通過一個(gè)散列函數(shù)的計(jì)算后返回一個(gè)數(shù)據(jù)存放的地址,因此可以直接通過地址來訪問它的值,這樣的查找就非常快。

用JavaScript實(shí)現(xiàn)散列表

先看這個(gè)構(gòu)造函數(shù),注意:存儲(chǔ)數(shù)據(jù)用的是數(shù)組,因?yàn)閷ぶ吩L問元素最方便的還是數(shù)組了。

function HashTable () {
    var table = []
}

需要實(shí)現(xiàn)的方法:

put(key, value):向散列表增加一個(gè)新的項(xiàng)

remove(key):根據(jù)鍵值從散列表中移除值

get(key):返回根據(jù)鍵值檢索到的特定的值

先實(shí)現(xiàn)散列函數(shù)

把鍵名的每個(gè)字母轉(zhuǎn)成ASCII碼再相加起來,最后和一個(gè)任意的數(shù)求余,得到數(shù)據(jù)存儲(chǔ)的地址。

var loseloseHashCode = function (key) {
  var hash = 0
  for (var i = 0; i < key.length; i++) {
    hash += key.charCodeAt(i)
  }
  return hash % 37
}
簡單實(shí)現(xiàn)

因?yàn)檫@里的方法比較簡單,我就直接全貼上來了

this.put = function (key, value) {
  var position = loseloseHashCode(key)
  console.log(position + " - " + key)
  table[position] = value
}

this.remove = function (key) {
  table[loseloseHashCode(key)] = undefined
}

this.get = function (key) {
  return table[loseloseHashCode(key)]
}

// 用來輸出整個(gè)散列表,查看結(jié)果用的
this.print = function () {
  for (var i = 0; i < table.length; i++) {
    if (table[i] !== undefined) {
      console.log(i + ": " + table[i])
    }
  }
}

稍等,還沒完呢,現(xiàn)在看似很完美,我們調(diào)用一下剛才寫的:

var hash = new HashTable()
hash.put("Gandalf", "gandalf@email.com")
hash.put("John", "johnsnow@email.com")
hash.put("Tyrion", "tyrion@email.com")

// 輸出結(jié)果
// 19 - Gandalf
// 29 - John
// 16 - Tyrion

好像沒什么不對,但是仔細(xì)想想:如果在某些情況下,散列函數(shù)根據(jù)傳入的鍵計(jì)算得到的地址是一樣的會(huì)怎么樣呢?

看看下面這個(gè)例子:

var hash = new HashTable()

hash.put("Gandalf", "gandalf@email.com")
hash.put("John", "john@email.com")
hash.put("Tyrion", "tyrion@email.com")
hash.put("Aaron", "aaron@email.com")
hash.put("Donnie", "donnie@email.com")
hash.put("Ana", "ana@email.com")
hash.put("Jonathan", "jonathan@email.com")
hash.put("Jamie", "jamie@email.com")
hash.put("Sue", "sue@email.com")
hash.put("Mindy", "mindy@email.com")
hash.put("Paul", "paul@email.com")
hash.put("Nathan", "nathan@email.com")

// 輸出結(jié)果
// 19 - Gandalf
// 29 - John
// 16 - Tyrion
// 16 - Aaron
// 13 - Donnie
// 13 - Ana
// 5 - Jonathan
// 5 - Jamie
// 5 - Sue
// 32 - Mindy
// 32 - Paul
// 10 - Nathan

這種情況就比較復(fù)雜了:Tyrion和Aaron的值都是16,Donnie和Ana都是13,還有其他很多重復(fù)的值,這時(shí)散列表表中是什么情況呢

hash.print()

// 輸出結(jié)果
// 5: sue@email.com
// 10: nathan@email.com
// 13: ana@email.com
// 16: aaron@email.com
// 19: gandalf@email.com
// 29: john@email.com
// 32: paul@email.com

很明顯,后面的元素會(huì)覆蓋前面的元素,但這樣是不行的,要想辦法解決沖突

解決沖突

目前主流的方法主要是兩種:分離鏈接法和線性探查法,這里就簡單介紹一下分離鏈接法。

分離鏈接法

思路很簡單:你不是重復(fù)了嗎,那我就在同一個(gè)位置里面放一個(gè)鏈表,重復(fù)的數(shù)據(jù)全都放在鏈表里面,你要找數(shù)據(jù)就在鏈表里面找。

如果不理解,可以參見下圖:

(圖片來源谷歌搜索,侵刪)

根據(jù)這個(gè)思路,我們重新實(shí)現(xiàn)一下三個(gè)方法,不過在這之前,我們需要一個(gè)對象來保存鍵值對

var ValuePair = function (key, value) {
  this.key = key
  this.value = value
  
  // 重寫toString主要是方便輸出查看
  this.toString = function () {
    return "[" + this.key + " - " + this.value + "]"
  }
}

接下來就是重寫方法了

this.put = function (key, value) {
  var position = loseloseHashCode(key)
  // 如果發(fā)現(xiàn)該位置還沒有元素,就先放一個(gè)鏈表,再用append加進(jìn)去
  if (table[position] === undefined) {
    // 因?yàn)槭褂胣ode執(zhí)行文件,這里L(fēng)inkedList是我在頂部用require引入的LinkedList.js
    table[position] = new LinkedList()
  }
  table[position].append(new ValuePair(key, value))
}

this.get = function (key) {
  var position = loseloseHashCode(key)

  if (table[position] !== undefined) {
    var current = table[position].getHead()

    // 遍歷鏈表查找值
    while (current.next) {
      if (current.element.key === key) {
        return current.element.value
      }
      current = current.next
    }

    // 檢查元素如果是最后一個(gè)的情況
    if (current.element.key === key) {
      return current.element.value
    }
  }

  return undefined
}

this.remove = function (key) {
  var position = loseloseHashCode(key)

  if (table[position] !== undefined) {
    var current = table[position].getHead()

    // 遍歷查找值
    while (current.next) {
      if (current.element.key === key) {
        // 使用鏈表的remove方法
        table[position].remove(current.element)
        // 當(dāng)鏈表為空了,就把散列表該位置設(shè)為undefined
        if (table[position].isEmpty()) {
          table[position] = undefined
        }
        return true
      }
      current = current.next
    }

    if (current.element.key === key) {
      table[position].remove(current.element)
      if (table[position].isEmpty()) {
        table[position] = undefined
      }
      return true
    }
  }

  return false
}

以上就是用分離鏈接法重寫的哈希表。

線性探查法

第二種辦法思路更粗暴:你不是占了這個(gè)位置嘛,那我就占下一個(gè),下個(gè)位置還被占了?那就占再下一個(gè)~

具體的實(shí)現(xiàn)我就不貼出來了,讀者可以自行思考并實(shí)現(xiàn),然后對照代碼看看。

這里先把源代碼放出來了

哈希表的實(shí)現(xiàn)-源代碼

創(chuàng)建更好的散列函數(shù)

以上是哈希表的兩個(gè)沖突解決辦法,但實(shí)際上應(yīng)用哈希表的時(shí)候能避免沖突就盡量避免沖突,一開始的散列函數(shù)不是一個(gè)好的函數(shù),因?yàn)闆_突太多了,這里就貼書上的一個(gè)不錯(cuò)的散列函數(shù)(社區(qū)),原理大致是:相加所得的hash數(shù)要夠大,且盡量為質(zhì)數(shù),用hash與另一個(gè)大于散列表大小的質(zhì)數(shù)做求余,這樣得到的地址也能盡量不重復(fù)。

var djb2HashCode = function (key) {
  var hash = 5381
  for (var i = 0; i < key.length; i++) {
    hash = hash * 33 + key.charCodeAt(i)
  }
  return hash % 1013
}
小結(jié)

實(shí)現(xiàn)了字典和哈希表感覺沒有想象中那么困難,當(dāng)然這還是開始。

不過,這幾天自己不斷地研究數(shù)據(jù)結(jié)構(gòu),也讓自己對于JS的理解進(jìn)一步加深了。繼續(xù)努力吧~

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

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

相關(guān)文章

  • 《Javascript數(shù)據(jù)結(jié)構(gòu)算法》筆記-「字典和散列表

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

    wenyiweb 評論0 收藏0
  • 《JavaScript數(shù)據(jù)結(jié)構(gòu)算法》筆記——第7章 字典和散列表

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

    zorro 評論0 收藏0
  • 每周一練 數(shù)據(jù)結(jié)構(gòu)算法(Dictionary 和 HashTable)

    摘要:什么是散列表和散列函數(shù)哈希表,也叫散列表,是根據(jù)關(guān)鍵碼值而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。根據(jù)鍵值從散列表中移除值。請實(shí)現(xiàn)散列表將和存在一個(gè)對象中即可定義一個(gè)包含和屬性的類并分配到散列表。 showImg(https://segmentfault.com/img/remote/1460000019005270); 這是第五周的練習(xí)題,上周忘記發(fā)啦,這周是復(fù)習(xí) Dictionary 和 Hash...

    eternalshallow 評論0 收藏0
  • 每周一練 數(shù)據(jù)結(jié)構(gòu)算法(Dictionary 和 HashTable)

    摘要:什么是散列表和散列函數(shù)哈希表,也叫散列表,是根據(jù)關(guān)鍵碼值而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。將字典的所有鍵名以數(shù)組的形式返回。根據(jù)鍵值從散列表中移除值。這是第五周的練習(xí)題,上周忘記發(fā)啦,這周是復(fù)習(xí) Dictionary 和 HashTable。 下面是之前分享的鏈接: 1.每周一練 之 數(shù)據(jù)結(jié)構(gòu)與算法(Stack) 2.每周一練 之 數(shù)據(jù)結(jié)構(gòu)與算法(LinkedList) 3.每周一練 之 數(shù)據(jù)結(jié)構(gòu)...

    ingood 評論0 收藏0
  • CSS技巧

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

    DangoSky 評論0 收藏0

發(fā)表評論

0條評論

最新活動(dòng)
閱讀需要支付1元查看
<