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

eternalshallow 發(fā)布于2019-08-26 13:51 / 949人閱讀

摘要：什么是散列表和散列函數(shù)哈希表，也叫散列表，是根據(jù)關鍵碼值而直接進行訪問的數(shù)據(jù)結構。根據(jù)鍵值從散列表中移除值。請實現(xiàn)散列表將和存在一個對象中即可定義一個包含和屬性的類并分配到散列表。

這是第五周的練習題，上周忘記發(fā)啦，這周是復習 Dictionary 和 HashTable。

下面是之前分享的鏈接：

1.每周一練之數(shù)據(jù)結構與算法（Stack）

2.每周一練之數(shù)據(jù)結構與算法（LinkedList）

3.每周一練之數(shù)據(jù)結構與算法（Queue）

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

歡迎關注我的 個人主頁 &&  個人博客 && 個人知識庫 && 微信公眾號“前端自習課”

本周練習內(nèi)容：數(shù)據(jù)結構與算法 —— Dictionary 和 HashTable

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

一、字典和散列表的概念

字典是什么？

字典和集合有什么異同？

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

散列表的特點是什么？

解析：

字典是什么？

字典是一種以 鍵-值對 形式存儲數(shù)據(jù)的數(shù)據(jù)格式，其中鍵名用來查詢特定元素。

字典和集合有什么異同？

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

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

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

散列表的特點是什么？

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

二、請實現(xiàn)一個字典

set(key,value)：向字典中添加新元素。
delete(key)：通過使用鍵值從字典中移除鍵值對應的值。
has(key)：如果某個鍵值存在于這個字典中，則返回 true，否則返回 false。
get(key)：使用鍵值查找對應的值并返回。
clear()：刪除字典中的所有元素。
size()：返回字典包含的元素數(shù)量，與數(shù)組的 length 屬性類似。
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 以上的語法實現(xiàn)。

解析：

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

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

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

    /**
     * 使用鍵值查找對應的值并返回
     * @param {*} key 查找的鍵名
     * @return {*} 查找的結果
     */
    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
    }

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

三、請實現(xiàn)一個散列表

put(key,value)：向散列表增加/更新一個新的項。
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();

解析：

// 三、請實現(xiàn)一個散列表
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;
    }
    /**
     * 向散列表增加/更新一個新的項
     * @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
    }
}

四、請利用之前已實現(xiàn)的鏈表，實現(xiàn)一個分離鏈接的散列表

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

請實現(xiàn)新的散列表方法：

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

get(key)：返回鍵值對應的值，沒有則返回 undefined。

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

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

提示：先找到元素儲存位置所對應的鏈表，再找到對應的值。

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

解析：

// 鏈表的實現(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;
    }
    /**
     * 向散列表增加/更新一個新的項
     * @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
    }
}

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

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

請實現(xiàn)散列表：

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

get(key)：返回鍵值對應的值，沒有則返回 undefined。

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

提示：移除一個元素，只需要將其賦值為 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;
    }
    /**
     * 向散列表增加/更新一個新的項
     * @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
    }
}

下周預告

下周將練習 Tree 的題目。

GPU云服務器云服務器看動畫學算法之:hashtable webrtc之vad算法算法與數(shù)據(jù)結構數(shù)據(jù)結構與算法

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

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

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

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

ingood 2019-05-22 14:21 評論0 收藏0
每周一練之 數(shù)據(jù)結構與算法（Set）

摘要：一集合是什么與它相關數(shù)學概念有哪些解題集合定義集合是一種包含不同元素的數(shù)據(jù)結構。集合中的元素稱為成員，集合最重要的兩個特點集合中的成員是無序集合中不存在相同成員即無序且唯一。 showImg(https://segmentfault.com/img/remote/1460000019005270); 這是第四周的練習題，五一放假結束，該收拾好狀態(tài)啦。下面是之前分享的鏈接： ...

silvertheo 2019-08-23 17:17 評論0 收藏0
每周一練之 數(shù)據(jù)結構與算法（Tree）

摘要：假設一個二叉搜索樹具有如下特征節(jié)點的左子樹只包含小于當前節(jié)點的數(shù)。所有左子樹和右子樹自身必須也是二叉搜索樹。代碼實現(xiàn)二叉樹節(jié)點定義來源驗證二叉搜索樹解析 showImg(https://segmentfault.com/img/remote/1460000019005270); 這是第六周的練習題，最近加班比較多，上周主要完成一篇 GraphQL入門教程，有興趣的小伙伴可以看下哈。 ...

zhonghanwen 2019-08-26 13:51 評論0 收藏0
每周一練之 數(shù)據(jù)結構與算法（Tree）

摘要：假設一個二叉搜索樹具有如下特征節(jié)點的左子樹只包含小于當前節(jié)點的數(shù)。所有左子樹和右子樹自身必須也是二叉搜索樹。代碼實現(xiàn)二叉樹節(jié)點定義來源驗證二叉搜索樹解析這是第六周的練習題，最近加班比較多，上周主要完成一篇 GraphQL入門教程，有興趣的小伙伴可以看下哈。下面是之前分享的鏈接： 1.每周一練之數(shù)據(jù)結構與算法（Stack） 2.每周一練之數(shù)據(jù)結構與算法（LinkedList） 3...

fizz 2019-05-22 11:25 評論0 收藏0
每周一練之 數(shù)據(jù)結構與算法（Queue）

摘要：與堆棧區(qū)別隊列的操作方式和堆棧類似，唯一的區(qū)別在于隊列只允許新數(shù)據(jù)在后端進行添加。移除隊列的第一項，并返回被移除的元素。三使用隊列計算斐波那契數(shù)列的第項。前兩項固定為，后面的項為前兩項之和，依次向后。 showImg(https://segmentfault.com/img/remote/1460000019005270); 這是第二周的練習題，這里補充下咯，五一節(jié)馬上就要到了，自己的...

anquan 2019-08-23 17:10 評論0 收藏0