Linear probing

線性探測

by Chris_Walter

JavaScript

class ValuePair {
  constructor(key, value) {
    this.key = key;
    this.value = value;
  }
}

class HashTableLinearProbing {
  constructor() {
    this.table = [];
  }
  hash(key) {
    let sum = 0;
    for (let i = 0; i < key.length; i++) {
      sum += key.charCodeAt(i);
    }
    return sum % 37;
  }
  //如果位置為undefined表示這位置還沒有元素，但如果這位置被佔走就index++，直到這位置沒有任何元素才會把
  put(key, value) {
    let position = this.hash(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);
    }
  }
  get(key) {
    let position = this.hash(key);
    if (this.table[position] !== 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 undefined;
  }
  remove(key) {
    let position = this.hash(key);
    if (this.table[position] !== undefined) {
      if (this.table[position].key === key) {
        this.table[position] = 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;
        }
      }
    }
    return undefined;
  }
}

let hashtable1 = new HashTableLinearProbing();
hashtable1.put('Strawberry', 45);
console.log(hashtable1.get('Strawberry'));
console.log(hashtable1.remove('Strawberry', 45));