資訊專欄INFORMATION COLUMN
摘要：什么是散列表和散列函數哈希表，也叫散列表，是根據關鍵碼值而直接進行訪問的數據結構。將字典的所有鍵名以數組的形式返回。根據鍵值從散列表中移除值。
這是第五周的練習題，上周忘記發啦，這周是復習 Dictionary 和 HashTable。
下面是之前分享的鏈接：
1.每周一練 之 數據結構與算法（Stack）
2.每周一練 之 數據結構與算法（LinkedList）
3.每周一練 之 數據結構與算法（Queue）
4.每周一練 之 數據結構與算法（Set）
歡迎關注我的 個人主頁 && 個人博客 && 個人知識庫 && 微信公眾號“前端自習課”
本周練習內容：數據結構與算法 —— Dictionary 和 HashTable
這些都是數據結構與算法，一部分方法是團隊其他成員實現的，一部分我自己做的，有什么其他實現方法或錯誤，歡迎各位大佬指點，感謝。
一、字典和散列表的概念
字典是什么？
字典和集合有什么異同？
什么是散列表和散列函數？
散列表的特點是什么？
解析：
字典是什么？
字典是一種以 鍵-值對 形式存儲數據的數據格式，其中鍵名用來查詢特定元素。
字典和集合有什么異同？
相同：都是用來存儲不同元素的數據格式；
區別：集合是以 值-值 的數據格式存儲，而字典是以 鍵-值 的數據格式存儲。
什么是散列表和散列函數？
哈希表（Hash table，也叫散列表），是根據關鍵碼值(·Key value·)而直接進行訪問的數據結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做散列函數，存放記錄的數組叫做散列表。
散列表的特點是什么？
特點：數組和鏈接優點的結合，查詢速度非常的快，幾乎是O(1)的時間復雜度，并且插入和刪除也容易。
二、請實現一個字典
set(key,value)：向字典中添加新元素。
delete(key)：通過使用鍵值從字典中移除鍵值對應的值。
has(key)：如果某個鍵值存在于這個字典中，則返回 true，否則返回 false。
get(key)：使用鍵值查找對應的值并返回。
clear()：刪除字典中的所有元素。
size()：返回字典包含的元素數量，與數組的 length 屬性類似。
keys()：將字典的所有鍵名以數組的形式返回。
values()：將字典包含的所有數值以數組形式返回。
使用示例：
let 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());
提示：Web 端優先使用 ES6 以上的語法實現。
解析：
// 二、請實現一個字典
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 = {}
}
/**
* 將字典的所有鍵名以數組的形式返回
* @return {Array} 所有鍵名的數組
*/
keys () {
return Object.keys(this.items)
}
/**
* 將字典的所有鍵值以數組的形式返回
* @return {Array} 所有鍵值的數組
*/
values () {
let result = []
for(let k in this.items){
if(this.has[k]){
result.push(this.items[k])
}
}
return result
}
/**
* 返回字典包含的元素數量
* @return {Number} 元素數量
*/
size () {
const values = this.values()
return values.length
}
}
三、請實現一個散列表
put(key,value)：向散列表增加/更新一個新的項。
remove(key)：根據鍵值從散列表中移除值。
get(key)：根據鍵值檢索到特定的值。
print()：打印散列表中已保存的值。
散列表內部的散列算法：
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", "gandalf@email.com");
hashTable.put("John", "johnsnow@email.com");
hashTable.put("Tyrion", "tyrion@email.com");
hashTable.print();
解析：
// 三、請實現一個散列表
class HashTable {
constructor(){
this.table = []
}
/**
* 散列函數
* @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
}
/**
* 根據鍵值從散列表中移除值
* @param {*} key 移除的鍵名
* @return {Boolean} 是否成功移除
*/
remove (key) {
if ( !key ) return false
let position = this.hashCode(key)
this.table[position] = undefined
return true
}
/**
* 根據鍵值檢索到特定的值
* @param {*} key 查找的鍵名
* @return {*} 查找的值
*/
get (key) {
let position = this.hashCode(key)
return this.table[position]
}
/**
* 打印散列表中已保存的值
* @return {*} 散列表的值
*/
print () {
return this.table
}
}
四、請利用之前已實現的鏈表，實現一個分離鏈接的散列表
分離鏈接是為散列表的每一個位置創建一個鏈表儲存元素的方式來處理散列表中的沖突：
請實現新的散列表方法：
put(key,value)：將 key 和value存在一個ValuePair對象中（即可定義一個包含key和value屬性的ValuePair` 類），并將其加入對應位置的鏈表中。
get(key)：返回鍵值對應的值，沒有則返回 undefined。
remove(key)：從散列表中移除鍵值對應的元素。
print()：打印散列表中已保存的值。
提示：先找到元素儲存位置所對應的鏈表，再找到對應的值。
const hashTable = new HashTable();
hashTable.put("Gandalf", "gandalf@email.com");
hashTable.put("Tyrion", "tyrion@email.com");
hashTable.put("Aaron", "aaron@email.com");
hashTable.put("Ana", "ana@email.com");
hashTable.put("Mindy", "mindy@email.com");
hashTable.put("Paul", "paul@email.com");
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 = []
}
/**
* 散列函數
* @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))
}
/**
* 根據鍵值從散列表中移除值
* @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
}
}
/**
* 根據鍵值檢索到特定的值
* @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
}
}
五、實現一個線性探查的散列表
線性探查是解決散列表中沖突的另一種方法，當向表中某一個位置加入新元素的時候，如果索引為 index 的位置已經被占據了，就嘗試 index+1 的位置。如果 index+1 的位置也被占據，就嘗試 index+2，以此類推。
請實現散列表：
put(key,value)：將 key 和 value 存在一個 ValuePair 對象中（即可定義一個包含 key 和 value 屬性的 ValuePair 類）并分配到散列表。
get(key)：返回鍵值對應的值，沒有則返回 undefined。
remove(key)：從散列表中移除鍵值對應的元素。
提示：移除一個元素，只需要將其賦值為 undefined。
使用示例：
const hashTable = new HashTable();
hashTable.put("Gandalf", "gandalf@email.com");
hashTable.put("Tyrion", "tyrion@email.com");
hashTable.put("Aaron", "aaron@email.com");
hashTable.put("Ana", "ana@email.com");
hashTable.put("Mindy", "mindy@email.com");
hashTable.put("Paul", "paul@email.com");
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 = []
}
/**
* 散列函數
* @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)
}
}
/**
* 根據鍵值從散列表中移除值
* @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
}
}
}
/**
* 根據鍵值檢索到特定的值
* @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 的題目。
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/6724.html
摘要：什么是散列表和散列函數哈希表，也叫散列表，是根據關鍵碼值而直接進行訪問的數據結構。根據鍵值從散列表中移除值。請實現散列表將和存在一個對象中即可定義一個包含和屬性的類并分配到散列表。 showImg(https://segmentfault.com/img/remote/1460000019005270); 這是第五周的練習題，上周忘記發啦，這周是復習 Dictionary 和 Hash...
摘要：一集合是什么與它相關數學概念有哪些解題集合定義集合是一種包含不同元素的數據結構。集合中的元素稱為成員，集合最重要的兩個特點集合中的成員是無序集合中不存在相同成員即無序且唯一。 showImg(https://segmentfault.com/img/remote/1460000019005270); 這是第四周的練習題，五一放假結束，該收拾好狀態啦。 下面是之前分享的鏈接： ...
摘要：假設一個二叉搜索樹具有如下特征節點的左子樹只包含小于當前節點的數。所有左子樹和右子樹自身必須也是二叉搜索樹。代碼實現二叉樹節點定義來源驗證二叉搜索樹解析 showImg(https://segmentfault.com/img/remote/1460000019005270); 這是第六周的練習題，最近加班比較多，上周主要完成一篇 GraphQL入門教程 ，有興趣的小伙伴可以看下哈。 ...
摘要：假設一個二叉搜索樹具有如下特征節點的左子樹只包含小于當前節點的數。所有左子樹和右子樹自身必須也是二叉搜索樹。代碼實現二叉樹節點定義來源驗證二叉搜索樹解析這是第六周的練習題，最近加班比較多，上周主要完成一篇 GraphQL入門教程 ，有興趣的小伙伴可以看下哈。 下面是之前分享的鏈接： 1.每周一練 之 數據結構與算法（Stack） 2.每周一練 之 數據結構與算法（LinkedList） 3...
摘要：與堆棧區別隊列的操作方式和堆棧類似，唯一的區別在于隊列只允許新數據在后端進行添加。移除隊列的第一項，并返回被移除的元素。三使用隊列計算斐波那契數列的第項。前兩項固定為，后面的項為前兩項之和，依次向后。 showImg(https://segmentfault.com/img/remote/1460000019005270); 這是第二周的練習題，這里補充下咯，五一節馬上就要到了，自己的...
閱讀 3078·2021-11-24 09:38
閱讀 1330·2021-09-22 15:27
閱讀 2968·2021-09-10 10:51
閱讀 1504·2021-09-09 09:33
閱讀 917·2021-08-09 13:47
閱讀 2072·2019-08-30 13:05
閱讀 892·2019-08-29 15:15
閱讀 2425·2019-08-29 12:21
