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

章節連結

課程相關資訊
內容

背景知識

範例程式碼
相關文章

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

課程對應章節：80~86

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

內容

背景知識

1. 承接上篇，若要取得 keys() 的列表陣列，可以寫迴圈遍歷即可，其複雜度為 O(n)
2. 為何有些場合要使用 Hash Tables 而不是 Array？因為 Hash Tables 在空間足夠的狀態下(避免 Collision 衝突情形)，其 search, insert, lookup 和 delete 的時間複雜度都為 O(1)。Array 的話，若要查詢、新增和刪除，複雜度都為 O(n)。
3. First Recurring Character：
思路 I ：用雙重迴圈，分別讓陣列中的數字兩兩對比。若有重複就回傳。(但要小心陣列的比較順序)
思路 II ：用 Hash Table，把數字當作 key ，value 則存 true。如此一來，當 map[key] 存在的時候，因為其 value 為 true，則 return 當下的數字。

範例程式碼

class HashTable {
  constructor(size){
    this.data = new Array(size);
  }

  _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]);
    return this.data;
  }

  get(key){
    const 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;
  }
  
  keys(){
    const keysArray = [];
    for (let i = 0; i < this.data.length; i++){
      if(this.data[i]){
        keysArray.push(this.data[i][0][0])
      }
    }
    return keysArray;
  }
}

const myHashTable = new HashTable(50);
myHashTable.set('grapes', 10000)
myHashTable.get('grapes')
myHashTable.set('apples', 9)
myHashTable.get('apples')
myHashTable.keys()