Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

散列錶(哈希錶)

mob604756e90326 2021-09-27 13:58:42 阅读数:30 评论数:0 点赞数:0 收藏数:0


散列錶

散列錶也稱哈希錶,散列算法的作用是盡可能快地在數據結構中找到一個值。

如果要在數據結構中獲得一個值,需要迭代整個數據結構來找到它。如果使用散列函數,就知道值的具體比特置,因此能够快速檢索到該值。

散列函數的作用是給定一個鍵值,然後返回值在錶中的地址。

loselose散列函數


下圖為常見的散列函數——lose lose散列函數,方法是簡單地將每個鍵值中的每個字母的 ASCII 值相加


散列錶(哈希錶)_删除元素

 創建散列函數



function defaultToString(item){
// 將鍵轉化為字符串
if(item === null){
return 'NULL'
}else if(item === undefined){
return 'UNDEFINED'
}else{
return item.toString()
}

}
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
class valuePair{
  • 1.
// 鍵值對
constructor(key, value){
this.key = key
this.value = value
}
toString(){
return `[#${this.key}: ${this.value}]`
}
}

class hashTable{
constructor(toStrFn = defaultToString){
this.toStrFn = toStrFn
this.table = {}
}
loseloseHashCode(key){
// 使用loselose散列函數
// 即將每個鍵中的每個字母的ASCII碼相加
if(typeof(key) === "number"){
return key
}
const tableKey = this.toStrFn(key)
let Hash = 0
for(let i=0; i<tableKey.length; i++){
Hash += tableKey.charCodeAt(i)
}
return Hash % 37
}
hashCode(key){
return this.loseloseHashCode(key)
}
put(key, value){
// 添加鍵值對
if(key != null && value != null){
const position = this.hashCode(key)
this.table[position] = new valuePair(key, value)
return true
}
return false
}
get(key){
// 通過key查找值, 找不到返回undefined
const valuePair = this.table[this.hashCode(key)]
return valuePair
}
}
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.
  • 34.
  • 35.
  • 36.
  • 37.
  • 38.
  • 39.
  • 40.
  • 41.
  • 42.
  • 43.
  • 44.
  • 45.
  • 46.


處理散列錶中的沖突


有時候,一些鍵會有相同的散列值。不同的值在散列錶中對應相同比特置的時候,我們稱其為沖突


1.分離鏈接


分離鏈接法包括為散列錶的每一個比特置創建一個鏈錶並將元素存儲在裏面。它是解决沖突的最簡單的方法,但是在 HashTable 實例之外還需要額外的存儲空間。


 如下圖:

散列錶(哈希錶)_鍵值對_02

 實現:



class HashTableSeparateChaining extends hashTable{
constructor(toStrFn = defaultToString){
super(toStrFn)
}
put(key, value){
// 每個元素為一個鏈錶,依次存儲相同hashcode的鍵值對
if(key != null && value != null){
const position = super.hashCode(key)
if(this.table[position] == undefined){
this.table[position] = new LinkedList() // LinkedList類詳見鏈錶
}
this.table[position].push(new valuePair(key, value))
return true
}
return false
}
get(key){
// 通過key獲取value
const position = super.hashCode(key)
const linkedList = this.table[position]
if (linkedList != undefined && !linkedList.isEmpty()) {
let current = linkedList.getHead()
while(current != null){
if(current.element.key === key){
return current.element.value
}
current = current.next
}
}
return undefined
}
remove(key){
// 通過key移除對應元素
const position = super.hashCode(key)
const linkedList = this.table[position]
if(linkedList != undefined && !linkedList.isEmpty()){
let current = linkedList.getHead()
while(current != null){
if(current.element.key === key){
linkedList.remove(current.element)
if(linkedList.isEmpty()){
delete this.table[position]
}
return true
}
current = current.next
}
}
return false
}
}
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.
  • 34.
  • 35.
  • 36.
  • 37.
  • 38.
  • 39.
  • 40.
  • 41.
  • 42.
  • 43.
  • 44.
  • 45.
  • 46.
  • 47.
  • 48.
  • 49.
  • 50.
  • 51.


2.線性探查


另一種解决沖突的方法是線性探查。之所以稱作線性,是因為它處理沖突的方法是將元素直接存儲到錶中,而不是在單獨的數據結構中。


添加元素



當想向錶中某個比特置添加一個新元素的時候,如果索引為 position 的比特置已經被占據了,就嘗試 position+1 的比特置。如果 position+1 的比特置也被占據了,就嘗試 position+2 的比特置,以此類推,直到在散列錶中找到一個空閑的比特置。


如下圖:


散列錶(哈希錶)_散列錶_03

 删除元素


在删除某個元素之後,需要檢驗是否有必要將其後一個或多個元素移動到之前的比特置。當搜索一個鍵的時候,這種方法可以避免找到一個空比特置。如果移動元素是必要的,我們就需要在散列錶中挪動鍵值對。


下圖展現了這個過程:


散列錶(哈希錶)_數據結構_04

 實現:



class HashTableSeparateChaining extends hashTable{
constructor(toStrFn = defaultToString){
super(toStrFn)
}
put(key, value){
// 插入元素
// 先判斷比特置是否被占用,插入一個未被占用的比特置
if(key != null && value != null){
const position = super.hashCode(key)
if(this.table[position] == undefined){
this.table[position] = new valuePair(key, value)
}else{
let index = position + 1
while(this.table[index] != undefined){
index ++
}
this.table[index] = new valuePair(key, value)
}
return true
}
return false
}
get(key){
// 獲取元素
const position = super.hashCode(key)
if(this.table[position] != undefined){
if(this.table[position].key === key){
return this.table[position].value
}
let index = position + 1
while(this.table[index] !== undefined && this.table[index].key !== key){
index ++
}
if(this.table[index] != undefined && this.table[index].key === key){
return this.table[index].value
}
}
return undefined
}
remove(key){
const position = super.hashCode(key)
if(this.table[position] != undefined){
if(this.table[position].key === key){
delete this.table[position]
this.verifyRemoveSideEffect(key, position) // 將删除空比特補上
return true
}else{
index = position + 1
while(this.table[index] != undefined && this.table[index].key !== key){
index ++
}
if(this.table[index] != undefined && this.table[index].key === key){
delete this.table[index]
this.verifyRemoveSideEffect(key, index)
return true
}
}
}
return undefined
}
verifyRemoveSideEffect(key, removedPosition){
// 把删除元素後的且與删除元素相同散列值的元素向上補一比特
const Hash = super.hashCode(key)
let index = removedPosition + 1
while(this.table[index] != undefined){
// 若在空比特處也沒有相同的散列值,說明後面都沒有了
const posHash = super.hashCode(this.table[index].key)
if(posHash <= Hash || posHash <= removedPosition){
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.
  • 34.
  • 35.
  • 36.
  • 37.
  • 38.
  • 39.
  • 40.
  • 41.
  • 42.
  • 43.
  • 44.
  • 45.
  • 46.
  • 47.
  • 48.
  • 49.
  • 50.
  • 51.
  • 52.
  • 53.
  • 54.
  • 55.
  • 56.
  • 57.
  • 58.
  • 59.
  • 60.
  • 61.
  • 62.
  • 63.
  • 64.
  • 65.
  • 66.
  • 67.
  • 68.
// 只移動小於等於删除元素的散列值
this.table[removedPosition] = this.table[index]
delete this.table[index]
removedPosition = index
}
index ++
}
}
}
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.


創建更好的散列函數


我們實現的 lose lose 散列函數並不是一個錶現良好的散列函數,因為它會產生太多的沖突。一個錶現良好的散列函數是由幾個方面構成的:插入和檢索元素的時間(即性能),以及較低的沖突可能性


另一個可以實現的、比 lose lose 更好的散列函數是 djb2,這並不是最好的散列函數,但這是最受社區推崇的散列函數之一。 




djb2HashCode(key) {
const tableKey = this.toStrFn(key)
let hash = 5381
for (let i = 0; i < tableKey.length; i++) {
hash = (hash * 33) + tableKey.charCodeAt(i) // 即使loselose散列值相同,djb2也幾乎不會相同
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
}
return hash % 1013
}
  • 1.
  • 2.
  • 3.

版权声明
本文为[mob604756e90326]所创,转载请带上原文链接,感谢

编程之旅,人生之路,不止于编程,还有诗和远方。
阅代码原理,看框架知识,学企业实践;
赏诗词,读日记,踏人生之路,观世界之行;

支付宝红包,每日可领