第八章散列表

Coder編程 2021-09-06

展開(kāi)全文

自我測(cè)試

本篇文章的測(cè)試用例及調(diào)試方法見(jiàn)前言

說(shuō)明

散列算法的作用是盡可能快地在數(shù)據(jù)結(jié)構(gòu)中找到一個(gè)值。在之前的章節(jié)中，你已經(jīng)知道如果要在數(shù)據(jù)結(jié)構(gòu)中獲得一個(gè)值（使用get方法），需要遍歷整個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)找到它。如果使用散列函數(shù)，就知道值的具體位置，因此能夠快速檢索到該值。散列函數(shù)的作用是給定一個(gè)鍵值，然后返回值在表中的地址。
舉個(gè)例子，我們繼續(xù)使用在前一節(jié)中使用的電子郵件地址簿。我們將要使用最常見(jiàn)的散列函數(shù)——“l(fā)ose lose”散列函數(shù)，方法是簡(jiǎn)單地將每個(gè)鍵值中的每個(gè)字母的ASCII值相加。

簡(jiǎn)單圖解

一個(gè)字典基本方法

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

散列沖突

當(dāng)使用散列算法的時(shí)候難免會(huì)出現(xiàn)計(jì)算出來(lái)的hashCode相同的時(shí)候,這個(gè)就叫散列沖突

解決散列沖突

分離鏈接

分離鏈接法包括為散列表的每一個(gè)位置創(chuàng)建一個(gè)鏈表并將元素存儲(chǔ)在里面。它是解決沖突的最簡(jiǎn)單的方法，但是它在HashTable實(shí)例之外還需要額外的存儲(chǔ)空間。

線性探查

另一種解決沖突的方法是線性探查。當(dāng)想向表中某個(gè)位置加入一個(gè)新元素的時(shí)候，如果索引為index的位置已經(jīng)被占據(jù)了，就嘗試index+1的位置。如果index+1的位置也被占據(jù)了，就嘗試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 = 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)
  }

  //插入一個(gè)元素
  put(key: K, value: V) {
    //如果沒(méi)有key,或者沒(méi)有值,就沒(méi)辦法插入
    if (key == null || value == null) {
      return false
    }
    //獲取hash位置
    let position = this.hashCode(key);
    //如果這個(gè)位置沒(méi)有鏈表,添加一個(gè)鏈表
    if (!this.table[position]) {
      this.table[position] = new LinkedList();
    }
    //將值添加到鏈表中
    this.table[position].push(new ValuePair(key, value));
    //維護(hù)數(shù)字
    this.count++;
    //返回插入成功
    return true;
  }

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

  remove(key: K) {
    //獲取這個(gè)key的hashCode
    let position = this.hashCode(key);
    //獲取該位置下的鏈表
    let linkList = this.table[position];
    if (linkList && !linkList.isEmpty()) {
      //需找key值在哪個(gè)位置
      let current = linkList.getHead();
      while (current) {
        if (current.element.key === key) {
          //刪除元素
          linkList.remove(current.element);
          //如果鏈表空了,就刪除該元素
          if (linkList.isEmpty()) {
            delete this.table[position];
          }
          //刪除數(shù)量減一
          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做判斷條件判斷可能會(huì)有問(wèn)題,0
   * @param key
   * @param value
   */
  put(key: K, value: V) {
    if (key != null && value != null) {
      // 獲取key經(jīng)過(guò)計(jì)算后在什么位置
      let position = this.hashCode(key);
      let data = new ValuePair(key, value);
      // 如果position位置無(wú)值
      if (this.table[position] == null) {
        this.table[position] = data;
      }
      // 如果key的位置有值
      else {
        //當(dāng)前位置有值,所以先自增一個(gè)
        position++;
        //如果這個(gè)位置有值就繼續(xù),無(wú)值就停止
        while (this.table[position] != null) {
          position++;
        }
        //循環(huán)結(jié)束將找到一個(gè)新的位置,這個(gè)時(shí)候?qū)⒅蒂x值上去,完成插入
        this.table[position] = data;
      }
      this.count++;
      return true;
    }
    return false;
  }

  remove(key: K): boolean {
    // 獲取key經(jīng)過(guò)計(jì)算后在什么位置
    let position = this.hashCode(key);
    //如果這個(gè)位置沒(méi)有值,則返回false
    if (this.table[position] == null) {
      return false;
    }
    //如果這個(gè)位置的值的key等于傳入的key,那么就刪除,并返回true
    if (this.table[position].key === key) {
      delete this.table[position];
      //重排數(shù)據(jù)
      this.rearrangeData(key, position);
      this.count--;
      return true;
    }
    //這個(gè)位置有值,但是key不是我要找的,所以需要繼續(xù)向下查找
    else {
      //因?yàn)閜osition位置已經(jīng)不對(duì),所以這里+1
      position++;
      //記錄一下這個(gè)位置,到時(shí)需要重排數(shù)據(jù)
      //當(dāng)這個(gè)位置有值,但是值的key不等于傳入的key就繼續(xù)循環(huán)
      while (this.table[position] != null && this.table[position].key !== key) {
        position++;
      }
      //判斷出來(lái)的位置是不是有值,有值就刪除
      if (this.table[position] != null) {
        delete this.table[position];
        //重排數(shù)據(jù)
        this.rearrangeData(key, position);
        this.count--;
        return true;
      }
      //沒(méi)有找到,就返回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位置重排后面的數(shù)據(jù)
   * @param index
   * 這個(gè)方法存在一個(gè)致命的錯(cuò)誤,當(dāng)元素刪除了,但是又沒(méi)有填充到這個(gè)刪除的位置,
   * 會(huì)導(dǎo)致下一次找到這個(gè)值的時(shí)候,發(fā)現(xiàn)沒(méi)有值
   private rearrangeData(index: any) {
    //獲取下一個(gè)元素
    let current = this.table[++index];
    let keyIndex = this.hashCode(current.key);
    //如果下一個(gè)元素有值,并且該位置的值算出來(lái)的key值 >= index - 1,則將該值移動(dòng)到前一個(gè)位置去
    while (current != null && keyIndex <= index - 1) {
      this.table[index - 1] = this.table[index];
      index++;
      current = this.table[index]
      keyIndex = this.hashCode(current.key);
    }
  }*/


  /**
   * 移動(dòng)刪除的元素
   * @param key       通過(guò)key計(jì)算起始位置
   * @param position  刪除的位置
   */
  private rearrangeData(key: any, position: any) {
    //起始位置
    let startPosition = this.hashCode(key)
    let index = position + 1;
    //從刪除位置的下一個(gè)位置開(kāi)始迭代散列表,直到找到一個(gè)空位置,
    while (this.table[index] != null) {
      //獲取下一個(gè)位置的position應(yīng)該是多少
      let posHash = this.hashCode(this.table[index].key)
      //如果下一個(gè)位置的position <= 起始位置   或者下一個(gè)位置的position <= 刪除位置
      if (posHash <= startPosition || posHash <= position) {
        // 將刪除位置的值填到刪除位置
        this.table[position] = this.table[index];
        //刪除下一個(gè)位置
        delete this.table[index];
        //將新的位置轉(zhuǎn)移到符合條件的位置上
        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對(duì)應(yīng)訓(xùn)練

本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購(gòu)買等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)點(diǎn)擊一鍵舉報(bào)。

轉(zhuǎn)藏 分享

QQ空間 QQ好友新浪微博微信

獻(xiàn)花（0） +1

來(lái)自： Coder編程 > 《待分類》

舉報(bào)/認(rèn)領(lǐng)