每周一練之數(shù)據(jù)結(jié)構(gòu)與算法（Dictionary 和 HashTable）

ingood 發(fā)布于2019-05-22 14:21 / 939人閱讀

摘要：什么是散列表和散列函數(shù)哈希表，也叫散列表，是根據(jù)關(guān)鍵碼值而直接進(jìn)行訪問(wè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)與算法（Queue）

4.每周一練之數(shù)據(jù)結(jié)構(gòu)與算法（Set）

歡迎關(guān)注我的 個(gè)人主頁(yè) &&  個(gè)人博客 && 個(gè)人知識(shí)庫(kù) && 微信公眾號(hào)“前端自習(xí)課”

本周練習(xí)內(nèi)容：數(shù)據(jù)結(jié)構(gòu)與算法 —— Dictionary 和 HashTable

這些都是數(shù)據(jù)結(jié)構(gòu)與算法，一部分方法是團(tuán)隊(duì)其他成員實(shí)現(xiàn)的，一部分我自己做的，有什么其他實(shí)現(xiàn)方法或錯(cuò)誤，歡迎各位大佬指點(diǎn)，感謝。

一、字典和散列表的概念

字典是什么？

字典和集合有什么異同？

什么是散列表和散列函數(shù)？

散列表的特點(diǎn)是什么？

解析：

字典是什么？

字典是一種以 鍵-值對(duì) 形式存儲(chǔ)數(shù)據(jù)的數(shù)據(jù)格式，其中鍵名用來(lái)查詢(xún)特定元素。

字典和集合有什么異同？

相同：都是用來(lái)存儲(chǔ)不同元素的數(shù)據(jù)格式；
區(qū)別：集合是以 值-值 的數(shù)據(jù)格式存儲(chǔ)，而字典是以 鍵-值 的數(shù)據(jù)格式存儲(chǔ)。

什么是散列表和散列函數(shù)？

哈希表（Hash table，也叫散列表），是根據(jù)關(guān)鍵碼值(·Key value·)而直接進(jìn)行訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)。也就是說(shuō)，它通過(guò)把關(guān)鍵碼值映射到表中一個(gè)位置來(lái)訪問(wèn)記錄，以加快查找的速度。這個(gè)映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。

散列表的特點(diǎn)是什么？

特點(diǎn)：數(shù)組和鏈接優(yōu)點(diǎn)的結(jié)合，查詢(xún)速度非常的快，幾乎是O(1)的時(shí)間復(fù)雜度，并且插入和刪除也容易。

二、請(qǐng)實(shí)現(xiàn)一個(gè)字典

set(key,value)：向字典中添加新元素。
delete(key)：通過(guò)使用鍵值從字典中移除鍵值對(duì)應(yīng)的值。
has(key)：如果某個(gè)鍵值存在于這個(gè)字典中，則返回 true，否則返回 false。
get(key)：使用鍵值查找對(duì)應(yīng)的值并返回。
clear()：刪除字典中的所有元素。
size()：返回字典包含的元素?cái)?shù)量，與數(shù)組的 length 屬性類(lèi)似。
keys()：將字典的所有鍵名以數(shù)組的形式返回。
values()：將字典包含的所有數(shù)值以數(shù)組形式返回。

使用示例：

let dictionary = new Dictionary();

dictionary.set("Gandalf", "[email protected]");
dictionary.set("John", "[email protected]");
dictionary.set("Tyrion", "[email protected]");

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());

提示：Web 端優(yōu)先使用 ES6 以上的語(yǔ)法實(shí)現(xiàn)。

解析：

// 二、請(qǐng)實(shí)現(xiàn)一個(gè)字典
class Dictionary {
    constructor(){
        this.items = []
    }
    /**
     * 向字典中添加新元素
     * @param {*} key 添加的鍵名
     * @param {*} value 添加的值
     */
    set (key, value) {
        if ( !key ) return new Error("請(qǐng)指定插入的key")
        this.items[key] = value
    }

    /**
     * 查詢(xún)某個(gè)鍵值存在于這個(gè)字典
     * @param {*} key 查詢(xún)的鍵名
     * @return {Boolean} 是否存在
     */
    has (key) {
        return key in this.items 
    }

    /**
     * 通過(guò)使用鍵值從字典中移除鍵值對(duì)應(yīng)的值
     * @param {*} key 移除的鍵名
     * @return {Boolean} 是否移除成功
     */
    delete (key) {
        if(!key || !this.has(key)) return false
        delete this.items[key]
        return true
    }

    /**
     * 使用鍵值查找對(duì)應(yīng)的值并返回
     * @param {*} key 查找的鍵名
     * @return {*} 查找的結(jié)果
     */
    get (key) {
        return this.has(key) ");this.items[key] : undefined
    }

    /**
     * 刪除字典中的所有元素
     */
    clear () {
        this.items = {}
    }

    /**
     * 將字典的所有鍵名以數(shù)組的形式返回
     * @return {Array} 所有鍵名的數(shù)組
     */
    keys () {
        return Object.keys(this.items)
    }

    /**
     * 將字典的所有鍵值以數(shù)組的形式返回
     * @return {Array} 所有鍵值的數(shù)組
     */
    values () {
        let result = []
        for(let k in this.items){
            if(this.has[k]){
                result.push(this.items[k])
            }
        }
        return result
    }

    /**
     * 返回字典包含的元素?cái)?shù)量
     * @return {Number} 元素?cái)?shù)量
     */
    size () {
        const values = this.values()
        return values.length
    }
}

三、請(qǐng)實(shí)現(xiàn)一個(gè)散列表

put(key,value)：向散列表增加/更新一個(gè)新的項(xiàng)。
remove(key)：根據(jù)鍵值從散列表中移除值。
get(key)：根據(jù)鍵值檢索到特定的值。
print()：打印散列表中已保存的值。

散列表內(nèi)部的散列算法：

function hashCode(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }
    return hash % 37;
}

使用示例：

const hashTable = new HashTable();

hashTable.put("Gandalf", "[email protected]");
hashTable.put("John", "[email protected]");
hashTable.put("Tyrion", "[email protected]");
hashTable.print();

解析：

// 三、請(qǐng)實(shí)現(xiàn)一個(gè)散列表
class HashTable {
    constructor(){
        this.table = []
    }
    /**
     * 散列函數(shù)
     * @param {*} key 鍵名
     */
    hashCode(key) {
        let hash = 0;
        for (let i = 0; i < key.length; i++) {
          hash += key.charCodeAt(i);
        }
        return hash % 37;
    }
    /**
     * 向散列表增加/更新一個(gè)新的項(xiàng)
     * @param {*} key 添加的鍵名
     * @param {*} value 添加的值
     */
    put (key, value) {
        let position = this.hashCode(key)
        this.table[position] = value
    }

    /**
     * 根據(jù)鍵值從散列表中移除值
     * @param {*} key 移除的鍵名
     * @return {Boolean} 是否成功移除
     */
    remove (key) {
        if ( !key ) return false
        let position = this.hashCode(key)
        this.table[position] = undefined
        return true
    }

    /**
     * 根據(jù)鍵值檢索到特定的值
     * @param {*} key 查找的鍵名
     * @return {*} 查找的值
     */
    get (key) {
        let position = this.hashCode(key)
        return this.table[position]
    }

    /**
     * 打印散列表中已保存的值
     * @return {*} 散列表的值
     */
    print () {
        return this.table
    }
}

四、請(qǐng)利用之前已實(shí)現(xiàn)的鏈表，實(shí)現(xiàn)一個(gè)分離鏈接的散列表

分離鏈接是為散列表的每一個(gè)位置創(chuàng)建一個(gè)鏈表儲(chǔ)存元素的方式來(lái)處理散列表中的沖突：

請(qǐng)實(shí)現(xiàn)新的散列表方法：

put(key,value)：將 key 和value存在一個(gè)ValuePair對(duì)象中（即可定義一個(gè)包含key和value屬性的ValuePair` 類(lèi)），并將其加入對(duì)應(yīng)位置的鏈表中。

get(key)：返回鍵值對(duì)應(yīng)的值，沒(méi)有則返回 undefined。

remove(key)：從散列表中移除鍵值對(duì)應(yīng)的元素。

print()：打印散列表中已保存的值。

提示：先找到元素儲(chǔ)存位置所對(duì)應(yīng)的鏈表，再找到對(duì)應(yīng)的值。

const hashTable = new HashTable();

hashTable.put("Gandalf", "[email protected]");
hashTable.put("Tyrion", "[email protected]");
hashTable.put("Aaron", "[email protected]");
hashTable.put("Ana", "[email protected]");
hashTable.put("Mindy", "[email protected]");
hashTable.put("Paul", "[email protected]");

hashTable.print();

console.log(hashTable.get("Tyrion"));
console.log(hashTable.get("Aaron"));

hashTable.remove("Tyrion");

hashTable.print();

解析：

// 鏈表的實(shí)現(xiàn)代碼省略 可以查看之前的代碼
let ValuePair = function (key, value){
    this.key = key
    this.value = value
    this.toString = function(){
        return `[${this.key} - ${this.value}]`
    }
}
class HashTable {
    constructor(){
        this.table = []
    }
    /**
     * 散列函數(shù)
     * @param {*} key 鍵名
     */
    hashCode(key) {
        let hash = 0;
        for (let i = 0; i < key.length; i++) {
          hash += key.charCodeAt(i);
        }
        return hash % 37;
    }
    /**
     * 向散列表增加/更新一個(gè)新的項(xiàng)
     * @param {*} key 添加的鍵名
     * @param {*} value 添加的值
     */
    put (key, value) {
        let position = this.hashCode(key)
        if(this.table[position] == undefined){
            this.table[position] = new LinkedList()
        }
        this.table[position].append(new ValuePair(key, value))
    }

    /**
     * 根據(jù)鍵值從散列表中移除值
     * @param {*} key 移除的鍵名
     * @return {Boolean} 是否成功移除
     */
    remove (key) {
        let position = this.hashCode(key)
        if ( !key || this.table[position] === undefined ) return false
        let current = this.table[position].getHead()
        while(current.next){
            if(current.element.key === key){
                this.table[position].remove(current.element)
                if(this.table[position].isEmpty){
                    this.table[position] = undefined
                }
                return true
            }
            current = current.next
        }
    }

    /**
     * 根據(jù)鍵值檢索到特定的值
     * @param {*} key 查找的鍵名
     * @return {*} 查找的值
     */
    get (key) {
        let position = this.hashCode(key)
        if(!key || this.table[position] === undefined) return undefined
        let current = this.table[position].getHead()
        while(current.next()){
            if(current.element.key === key){
                return current.element.value
            }
            current = current.next
        }
    }

    /**
     * 打印散列表中已保存的值
     * @return {*} 散列表的值
     */
    print () {
        return this.table
    }
}

五、實(shí)現(xiàn)一個(gè)線性探查的散列表

線性探查是解決散列表中沖突的另一種方法，當(dāng)向表中某一個(gè)位置加入新元素的時(shí)候，如果索引為 index 的位置已經(jīng)被占據(jù)了，就嘗試 index+1 的位置。如果 index+1 的位置也被占據(jù)，就嘗試 index+2，以此類(lèi)推。

請(qǐng)實(shí)現(xiàn)散列表：

put(key,value)：將 key 和 value 存在一個(gè) ValuePair 對(duì)象中（即可定義一個(gè)包含 key 和 value 屬性的 ValuePair 類(lèi)）并分配到散列表。

get(key)：返回鍵值對(duì)應(yīng)的值，沒(méi)有則返回 undefined。

remove(key)：從散列表中移除鍵值對(duì)應(yīng)的元素。

提示：移除一個(gè)元素，只需要將其賦值為 undefined。

使用示例：

const hashTable = new HashTable();

hashTable.put("Gandalf", "[email protected]");
hashTable.put("Tyrion", "[email protected]");
hashTable.put("Aaron", "[email protected]");
hashTable.put("Ana", "[email protected]");
hashTable.put("Mindy", "[email protected]");
hashTable.put("Paul", "[email protected]");

hashTable.print();

console.log(hashTable.get("Tyrion"));
console.log(hashTable.get("Aaron"));

hashTable.remove("Tyrion");

hashTable.print();

解析：

let ValuePair = function (key, value){
    this.key = key
    this.value = value
    this.toString = function(){
        return `[${this.key} - ${this.value}]`
    }
}
class HashTable {
    constructor(){
        this.table = []
    }
    /**
     * 散列函數(shù)
     * @param {*} key 鍵名
     */
    hashCode(key) {
        let hash = 0;
        for (let i = 0; i < key.length; i++) {
          hash += key.charCodeAt(i);
        }
        return hash % 37;
    }
    /**
     * 向散列表增加/更新一個(gè)新的項(xiàng)
     * @param {*} key 添加的鍵名
     * @param {*} value 添加的值
     */
    put (key, value) {
        let position = this.hashCode(key)
        if(this.table[position] == undefined){
            this.table[position] = new ValuePair(key, value)
        }else{
            let index = ++position
            while(this.table[index] !== undefined){
                index ++
            }
            this.table[index] = new ValuePair(key, value)
        }
    }

    /**
     * 根據(jù)鍵值從散列表中移除值
     * @param {*} key 移除的鍵名
     * @return {Boolean} 是否成功移除
     */
    remove (key) {
        let position = this.hashCode(key)
        if( !key || this.table[position] === undefined ) return undefined
        if(this.table[position].key === key){
            this.table[index] = undefined
        }else{
            let index = ++position
            while(
                this.table[index] === undefined ||
                this.table[index].key !== key
            ){
                index ++
            }
            if(this.table[index].key === key){
                this.table[index] = undefined
            }
        }
    }

    /**
     * 根據(jù)鍵值檢索到特定的值
     * @param {*} key 查找的鍵名
     * @return {*} 查找的值
     */
    get (key) {
        let position = this.hashCode(key)
        if( !key || this.table[position] === undefined ) return undefined
        if(this.table[position].key === key){
            return this.table[position].value
        }else{
            let index = ++position
            while(
                this.table[index] === undefined ||
                this.table[index].key !== key
            ){
                index ++
            }
            if(this.table[index].key === key){
                return this.table[index].value
            }
        }
    }

    /**
     * 打印散列表中已保存的值
     * @return {*} 散列表的值
     */
    print () {
        return this.table
    }
}

下周預(yù)告

下周將練習(xí) Tree 的題目。

云服務(wù)器 GPU云服務(wù)器看動(dòng)畫(huà)學(xué)算法之:hashtable webrtc之vad算法算法與數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)與算法

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/6724.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

ingood

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

增強(qiáng)全面從嚴(yán)治黨永遠(yuǎn)在路上的堅(jiān)定和執(zhí)著——論學(xué)習(xí)貫徹黨的十九屆六中全會(huì)精神

閱讀 3095·2021-11-24 09:38
什么叫獨(dú)立主機(jī)-什么是云主機(jī)，與獨(dú)立服務(wù)器有什么區(qū)別？

閱讀 1347·2021-09-22 15:27
程序員的自我修煉——新手如何學(xué)好編程

閱讀 2983·2021-09-10 10:51
C語(yǔ)言進(jìn)階：指針進(jìn)階續(xù)

閱讀 1521·2021-09-09 09:33
DediPath夏季促銷(xiāo)：洛杉磯E3服務(wù)器每月39美元起,紐約服務(wù)器每月49美元起

閱讀 932·2021-08-09 13:47
應(yīng)該了解的 Web 圖標(biāo)解決方案

閱讀 2098·2019-08-30 13:05
Styled-Components

閱讀 903·2019-08-29 15:15
關(guān)于移動(dòng)端文字無(wú)法垂直居中（或line-height不起作用）的問(wèn)題的解決方案

閱讀 2439·2019-08-29 12:21

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專(zhuān)欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

每周一練之數(shù)據(jù)結(jié)構(gòu)與算法（Dictionary 和 HashTable）

相關(guān)文章