第八章散串列-有解無憂

說明

散列演算法的作用是盡可能快地在資料結構中找到一個值，在之前的章節中，你已經知道如果要在資料結構中獲得一個值（使用get方法），需要遍歷整個資料結構來找到它，如果使用散列函式，就知道值的具體位置，因此能夠快速檢索到該值，散列函式的作用是給定一個鍵值，然后回傳值在表中的地址，
舉個例子，我們繼續使用在前一節中使用的電子郵件地址簿，我們將要使用最常見的散列函式——“lose lose”散列函式，方法是簡單地將每個鍵值中的每個字母的ASCII值相加，

簡單圖解

一個字典基本方法

hashCode : 獲取一個hashCode
put(key,value) : 向字典中添加新元素，
remove(key) : 如果某個鍵值存在于這個字典中，則回傳true，反之則回傳false，
get(key) :通過鍵值查找特定的數值并回傳，
clear() : 移除字典中的所有元素
size() : 回傳字典的元素個數
isEmpty: 字典是空的
getTable: 回傳字典中的資料

散列沖突

當使用散列演算法的時候難免會出現計算出來的hashCode相同的時候,這個就叫散列沖突

解決散列沖突

分離鏈接

分離鏈接法包括為散串列的每一個位置創建一個鏈表并將元素存盤在里面，它是解決沖突的最簡單的方法，但是它在HashTable實體之外還需要額外的存盤空間，

線性探查

另一種解決沖突的方法是線性探查，當想向表中某個位置加入一個新元素的時候，如果索引為index的位置已經被占據了，就嘗試index+1的位置，如果index+1的位置也被占據了，就嘗試index+2的位置，以此類推，

公共部分

function defaultToString(item: any): string {
  if (item === null) {
    return 'NULL';
  } else if (item === undefined) {
    return 'UNDEFINED';
  } else if (typeof item === 'string' || item instanceof String) {
    return `${item}`;
  }
  return item.toString();
}

class ValuePair<K, V> {
  key: K;
  value: V;

  constructor(key: K, value: V) {
    this.key = key;
    this.value = https://www.cnblogs.com/wangzhaoyv/archive/2020/11/15/value;
  }

  toString() {
    return `[#${this.key}: ${this.value}]`;
  }
}

分離鏈接

import LinkedList from "./linked-list"; 
export default class HashMapByLinkList<K, V> {
  table: any;
  count: number;
  toStrFn: any;

  constructor(defaultToStr: any = defaultToString) {
    this.count = 0;
    this.table = {};
    this.toStrFn = defaultToStr;
  }

  private loseloseHashCode(key: K) {
    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
   */
  hashCode(key: K) {
    return this.loseloseHashCode(key)
  }

  //插入一個元素
  put(key: K, value: V) {
    //如果沒有key,或者沒有值,就沒辦法插入
    if (key == null || value =https://www.cnblogs.com/wangzhaoyv/archive/2020/11/15/= null) {
      return false
    }
    //獲取hash位置
    let position = this.hashCode(key);
    //如果這個位置沒有鏈表,添加一個鏈表
    if (!this.table[position]) {
      this.table[position] = new LinkedList();
    }
    //將值添加到鏈表中
    this.table[position].push(new ValuePair(key, value));
    //維護數字
    this.count++;
    //回傳插入成功
    return true;
  }

  get(key: K) {
    //獲取位置資訊
    let hashCode = this.hashCode(key);
    //獲取該位置的鏈表
    let linkList = this.table[hashCode];
    //如果這個位置有鏈表,并且鏈表有值
    if (linkList && !linkList.isEmpty()) {
      //獲取head指標
      let current = linkList.getHead();
      while (current) {
        //判斷這個節點上元素的key是否和傳入的key相同
        if (current.element.key === key) {
          return current.element.value;
        }
        //如果不相等,就遍歷下一個節點
        current = current.next;
      }
    }
    //如果沒有找到,就回傳undefined
    return undefined;
  }

  remove(key: K) {
    //獲取這個key的hashCode
    let position = this.hashCode(key);
    //獲取該位置下的鏈表
    let linkList = this.table[position];
    if (linkList && !linkList.isEmpty()) {
      //需找key值在哪個位置
      let current = linkList.getHead();
      while (current) {
        if (current.element.key === key) {
          //洗掉元素
          linkList.remove(current.element);
          //如果鏈表空了,就洗掉該元素
          if (linkList.isEmpty()) {
            delete this.table[position];
          }
          //洗掉數量減一
          this.count--;
          return true;
        }
        current = current.next;
      }
    }
    return false;
  }

  isEmpty() {
    return this.count === 0
  }

  size() {
    return this.count;
  }

  clear() {
    this.table = {};
    this.count = 0;
  }

  getTable() {
    return this.table;
  }


  toString() {
    if (this.isEmpty()) {
      return'';
    }
    const keys = Object.keys(this.table);
    let objString = `{${keys[0]} => ${this.table[keys[0]].toString()}}`;
    for (let i = 1; i < keys.length; i++) {
      objString = `${objString},{${keys[i]} => ${this.table[
        keys[i]
        ].toString()}}`;
    }
    return objString;
  }
}

線性探查

export default class HashMap<K, V> {
  table: any;
  toStrFn: any;
  count: number;

  constructor(toStrFn = defaultToString) {
    this.toStrFn = toStrFn;
    this.table = {};
    this.count = 0;
  }


  private loseloseHashCode(key: K) {
    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: K) {
    return this.loseloseHashCode(key);
  }

  /**
   * 注意key,value必傳,還要注意使用key做判斷條件判斷可能會有問題,0
   * @param key
   * @param value
   */
  put(key: K, value: V) {
    if (key != null && value != null) {
      // 獲取key經過計算后在什么位置
      let position = this.hashCode(key);
      let data = https://www.cnblogs.com/wangzhaoyv/archive/2020/11/15/new ValuePair(key, value);
      // 如果position位置無值
      if (this.table[position] == null) {
        this.table[position] = data;
      }
      // 如果key的位置有值
      else {
        //當前位置有值,所以先自增一個
        position++;
        //如果這個位置有值就繼續,無值就停止
        while (this.table[position] != null) {
          position++;
        }
        //回圈結束將找到一個新的位置,這個時候將值賦值上去,完成插入
        this.table[position] = data;
      }
      this.count++;
      return true;
    }
    return false;
  }

  remove(key: K): boolean {
    // 獲取key經過計算后在什么位置
    let position = this.hashCode(key);
    //如果這個位置沒有值,則回傳false
    if (this.table[position] == null) {
      return false;
    }
    //如果這個位置的值的key等于傳入的key,那么就洗掉,并回傳true
    if (this.table[position].key === key) {
      delete this.table[position];
      //重排資料
      this.rearrangeData(key, position);
      this.count--;
      return true;
    }
    //這個位置有值,但是key不是我要找的,所以需要繼續向下查找
    else {
      //因為position位置已經不對,所以這里+1
      position++;
      //記錄一下這個位置,到時需要重排資料
      //當這個位置有值,但是值的key不等于傳入的key就繼續回圈
      while (this.table[position] != null && this.table[position].key !== key) {
        position++;
      }
      //判斷出來的位置是不是有值,有值就洗掉
      if (this.table[position] != null) {
        delete this.table[position];
        //重排資料
        this.rearrangeData(key, position);
        this.count--;
        return true;
      }
      //沒有找到,就回傳false
      return false;
    }
  }

  get(key: K) {
    let position = this.hashCode(key);
    if (this.table[position] == null) {
      return undefined;
    }
    if (this.table[position].key === key) {
      return this.table[position].value;
    } else {
      position++;
      while (this.table[position] != null && this.table[position].key !== key) {
        position++;
      }
      if (this.table[position] != null) {
        return this.table[position].value;
      }
    }
    return undefined;
  }

  /**
   * 從index位置重排后面的資料
   * @param index
   * 這個方法存在一個致命的錯誤,當元素洗掉了,但是又沒有填充到這個洗掉的位置,
   * 會導致下一次找到這個值的時候,發現沒有值
   private rearrangeData(index: any) {
    //獲取下一個元素
    let current = this.table[++index];
    let keyIndex = this.hashCode(current.key);
    //如果下一個元素有值,并且該位置的值算出來的key值 >= index - 1,則將該值移動到前一個位置去
    while (current != null && keyIndex <= index - 1) {
      this.table[index - 1] = this.table[index];
      index++;
      current = this.table[index]
      keyIndex = this.hashCode(current.key);
    }
  }*/


  /**
   * 移動洗掉的元素
   * @param key       通過key計算起始位置
   * @param position  洗掉的位置
   */
  private rearrangeData(key: any, position: any) {
    //起始位置
    let startPosition = this.hashCode(key)
    let index = position + 1;
    //從洗掉位置的下一個位置開始迭代散串列,直到找到一個空位置,
    while (this.table[index] != null) {
      //獲取下一個位置的position應該是多少
      let posHash = this.hashCode(this.table[index].key)
      //如果下一個位置的position <= 起始位置   或者下一個位置的position <= 洗掉位置
      if (posHash <= startPosition || posHash <= position) {
        // 將洗掉位置的值填到洗掉位置
        this.table[position] = this.table[index];
        //洗掉下一個位置
        delete this.table[index];
        //將新的位置轉移到符合條件的位置上
        position = index;
      }
      index++;
    }
  }

  isEmpty() {
    return this.size() === 0;
  }

  size() {
    return this.count;
  }

  clear() {
    this.table = {};
    this.count = 0;
  }

  getTable() {
    return this.table;
  }

  toString() {
    if (this.isEmpty()) {
      return'';
    }
    const keys = Object.keys(this.table);
    let objString = `{${keys[0]} => ${this.table[keys[0]].toString()}}`;
    for (let i = 1; i < keys.length; i++) {
      objString = `${objString},{${keys[i]} => ${this.table[
        keys[i]
        ].toString()}}`;
    }
    return objString;
  }
}

書中代碼

分離鏈接

export default class HashTableSeparateChaining<K, V> {
  protected table: { [key: string]: LinkedList<ValuePair<K, V>> };

  constructor(protected toStrFn: (key: K) => string = defaultToString) {
    this.table = {};
  }

  private loseloseHashCode(key: K) {
    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: K) {
    return this.loseloseHashCode(key);
  }

  put(key: K, value: V) {
    if (key != null && value != null) {
      const position = this.hashCode(key);

      if (this.table[position] == null) {
        this.table[position] = new LinkedList<ValuePair<K, V>>();
      }
      this.table[position].push(new ValuePair(key, value));
      return true;
    }
    return false;
  }

  get(key: K) {
    const position = this.hashCode(key);
    const linkedList = this.table[position];
    if (linkedList != null && !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: K) {
    const position = this.hashCode(key);
    const linkedList = this.table[position];
    if (linkedList != null && !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;
  }

  isEmpty() {
    return this.size() === 0;
  }

  size() {
    let count = 0;
    Object.values(this.table).forEach(linkedList => count += linkedList.size());
    return count;
  }

  clear() {
    this.table = {};
  }

  getTable() {
    return this.table;
  }

  toString() {
    if (this.isEmpty()) {
      return '';
    }
    const keys = Object.keys(this.table);
    let objString = `{${keys[0]} => ${this.table[keys[0]].toString()}}`;
    for (let i = 1; i < keys.length; i++) {
      objString = `${objString},{${keys[i]} => ${this.table[
        keys[i]
      ].toString()}}`;
    }
    return objString;
  }
}

線性探查

直接洗掉版

export default class HashTableLinearProbing<K, V> {
  protected table: { [key: string]: ValuePair<K, V> };

  constructor(protected toStrFn: (key: K) => string = defaultToString) {
    this.table = {};
  }

  private loseloseHashCode(key: K) {
    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: K) {
    return this.loseloseHashCode(key);
  }

  put(key: K, value: V) {
    if (key != null && value != null) {
      const position = this.hashCode(key);

      if (this.table[position] == null) {
        this.table[position] = new ValuePair(key, value);
      } else {
        let index = position + 1;
        while (this.table[index] != null) {
          index++;
        }
        this.table[index] = new ValuePair(key, value);
      }
      return true;
    }
    return false;
  }

  get(key: K) {
    const position = this.hashCode(key);

    if (this.table[position] != null) {
      if (this.table[position].key === key) {
        return this.table[position].value;
      }
      let index = position + 1;
      while (this.table[index] != null && this.table[index].key !== key) {
        index++;
      }
      if (this.table[index] != null && this.table[index].key === key) {
        return this.table[position].value;
      }
    }
    return undefined;
  }

  remove(key: K) {
    const position = this.hashCode(key);

    if (this.table[position] != null) {
      if (this.table[position].key === key) {
        delete this.table[position];
        this.verifyRemoveSideEffect(key, position);
        return true;
      }
      let index = position + 1;
      while (this.table[index] != null && this.table[index].key !== key) {
        index++;
      }
      if (this.table[index] != null && this.table[index].key === key) {
        delete this.table[index];
        this.verifyRemoveSideEffect(key, index);
        return true;
      }
    }
    return false;
  }

  private verifyRemoveSideEffect(key: K, removedPosition: number) {
    const hash = this.hashCode(key);
    let index = removedPosition + 1;
    while (this.table[index] != null) {
      const posHash = this.hashCode(this.table[index].key);
      if (posHash <= hash || posHash <= removedPosition) {
        this.table[removedPosition] = this.table[index];
        delete this.table[index];
        removedPosition = index;
      }
      index++;
    }
  }

  isEmpty() {
    return this.size() === 0;
  }

  size() {
    return Object.keys(this.table).length;
  }

  clear() {
    this.table = {};
  }

  getTable() {
    return this.table;
  }

  toString() {
    if (this.isEmpty()) {
      return '';
    }
    const keys = Object.keys(this.table);
    let objString = `{${keys[0]} => ${this.table[keys[0]].toString()}}`;
    for (let i = 1; i < keys.length; i++) {
      objString = `${objString},{${keys[i]} => ${this.table[
        keys[i]
      ].toString()}}`;
    }
    return objString;
  }
}

偽洗掉版

export default class HashTableLinearProbingLazy<K, V> {
  protected table: { [key: string]: ValuePairLazy<K, V> };

  constructor(protected toStrFn: (key: K) => string = defaultToString) {
    this.table = {};
  }

  private loseloseHashCode(key: K) {
    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: K) {
    return this.loseloseHashCode(key);
  }

  put(key: K, value: V) {
    if (key != null && value != null) {
      const position = this.hashCode(key);

      if (
        this.table[position] == null ||
        (this.table[position] != null && this.table[position].isDeleted)
      ) {
        this.table[position] = new ValuePairLazy(key, value);
      } else {
        let index = position + 1;
        while (this.table[index] != null && !this.table[position].isDeleted) {
          index++;
        }
        this.table[index] = new ValuePairLazy(key, value);
      }
      return true;
    }
    return false;
  }

  get(key: K) {
    const position = this.hashCode(key);

    if (this.table[position] != null) {
      if (this.table[position].key === key && !this.table[position].isDeleted) {
        return this.table[position].value;
      }
      let index = position + 1;
      while (
        this.table[index] != null &&
        (this.table[index].key !== key || this.table[index].isDeleted)
      ) {
        if (this.table[index].key === key && this.table[index].isDeleted) {
          return undefined;
        }
        index++;
      }
      if (
        this.table[index] != null &&
        this.table[index].key === key &&
        !this.table[index].isDeleted
      ) {
        return this.table[position].value;
      }
    }
    return undefined;
  }

  remove(key: K) {
    const position = this.hashCode(key);

    if (this.table[position] != null) {
      if (this.table[position].key === key && !this.table[position].isDeleted) {
        this.table[position].isDeleted = true;
        return true;
      }
      let index = position + 1;
      while (
        this.table[index] != null &&
        (this.table[index].key !== key || this.table[index].isDeleted)
      ) {
        index++;
      }
      if (
        this.table[index] != null &&
        this.table[index].key === key &&
        !this.table[index].isDeleted
      ) {
        this.table[index].isDeleted = true;
        return true;
      }
    }
    return false;
  }

  isEmpty() {
    return this.size() === 0;
  }

  size() {
    let count = 0;
    Object.values(this.table).forEach(valuePair => {
      count += valuePair.isDeleted === true ? 0 : 1;
    });
    return count;
  }

  clear() {
    this.table = {};
  }

  getTable() {
    return this.table;
  }

  toString() {
    if (this.isEmpty()) {
      return '';
    }
    const keys = Object.keys(this.table);
    let objString = `{${keys[0]} => ${this.table[keys[0]].toString()}}`;
    for (let i = 1; i < keys.length; i++) {
      objString = `${objString},{${keys[i]} => ${this.table[
        keys[i]
      ].toString()}}`;
    }
    return objString;
  }
}

leetcode對應訓練

轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/217543.html

標籤：其他

上一篇：第八章字典

下一篇：js陣列方法(管飽)

第八章 散串列

說明

簡單圖解

一個字典基本方法

散列沖突

解決散列沖突

公共部分

分離鏈接

線性探查

書中代碼

分離鏈接

線性探查

直接洗掉版

偽洗掉版

leetcode對應訓練

第八章散串列