[筆記] Master The Coding Interview – 5 @地瓜大的飛翔旅程

章節連結

課程相關資訊
內容

背景知識

範例程式碼
相關文章

這篇是 Udemy 上的知名課程 – Master the Coding Interview 的部分進修心得。這篇對應的內容是「Data Structures: Hash Tables」關於陣列的第一部分簡介。

課程對應章節：74~79

請注意：本系列文章為個人對應課程的消化吸收後，所整理出來的內容。換言之，並不一定會包含全部的課程內容，也有可能會添加其他資源來說明。

內容

背景知識

1. 每個程式語言多半已內建 Hash Table 這類的資料結構(一連串的 key-value pair)，像是 JavaScript – Object、Python – Dictionary、JAVA – Map、Ruby – Hash
2. 輸入 key，經由快速的 hash function 運算後，得到一串看似亂碼的 key 當成記憶體位置，並儲存對應的值。這是一個單向的過程。
3. Hash Table 在 Insert, Lookup, Delete 和 Search 的時間複雜度都是 O(1)，不過你得先知道對應的 key 才行。
4. 當你的 Table 不夠大到容納的下 key 的數量，那就有機會發生 Hash Collision。也就是指同一個 key 會被兩筆以上的資料所呼叫到，也就發生了衝突。

範例程式碼

class HashTable{
  constructor(size){
    this.data = new Array(size);
  }
  
  /*產生 hash 的函式*/
  _hash(key){
    let hash = 0
    for(let i=0; i<key.length;i++){
      hash = (hash + key.charCodeAt(i) * i ) % this.data.length
    }
    return hash
  }
  
  set(key, value){
    let address = this._hash(key)
    if(!this.data[address]){
       this.data[address] = []
    }
    this.data[address].push([key, value])
  }
  
  get(key){
    let address = this._hash(key)
    const currentBucket = this.data[address];
    if(currentBucket){
        for(let i=0; i< currentBucket.length; i++){
          if(currentBucket[i][0] === key){
              return currentBucket[i][1]
          }
       }
    }
    return undefined
  }
}

const myHashTable = new HashTable(10)
myHashTable.set("grape",10000)
myHashTable.set("apples",54)
myHashTable.get("apples") // 54

class HashTable{

constructor(size){

this.data = new Array(size);

}

/*產生 hash 的函式*/

_hash(key){

let hash = 0

for(let i=0; i<key.length;i++){

hash = (hash + key.charCodeAt(i) * i ) % this.data.length

}

return hash

}

set(key, value){

let address = this._hash(key)

if(!this.data[address]){

this.data[address] = []

}

this.data[address].push([key, value])

}

get(key){

let address = this._hash(key)

const currentBucket = this.data[address];

if(currentBucket){

for(let i=0; i< currentBucket.length; i++){

if(currentBucket[i][0] === key){

return currentBucket[i][1]

}

return undefined

}

const myHashTable = new HashTable(10)

myHashTable.set("grape",10000)

myHashTable.set("apples",54)

myHashTable.get("apples") // 54