走进 Typescript 数据结构（散列表）

typescript-cover-image.jpg

散列算法的作用是尽可能快地在数据结构中找到一个值。通常在集合中获取一个值的做法都是遍历整个数据结构来找到想要的值。如果用散列函数，就知道值的具体位置，所以很快就能检索到想要的值。

function showHashCode(key){
    var hash = 0;
    for(var i = 0; i < key.length; i++){
        hash += key.charCodeAt(i) + " - ";

    }
    console.log(key  + " -> " + hash);
    return hash % 35;
}

这方法很简单但是很有效地将一个值的字母ASCII值相加作为查询码。运行结果如下：

angular -> 097 - 110 - 103 - 117 - 108 - 97 - 114 -
spring -> 0115 - 112 - 114 - 105 - 110 - 103 -
flask -> 0102 - 108 - 97 - 115 - 107 -

export default class HashTable {
  table: any[];
  constructor() {
    this.table = [];
  }

  put(key: string, val: any) {
    const position: number = this.loseloseHashCode(key);
    console.log(position + " - " + key);
    this.table[position] = val;
  }

  get(key: string): any {
    return this.table[this.loseloseHashCode(key)];
  }

  remove(key: string) {
    this.table[this.loseloseHashCode(key)] = undefined;
  }

  private loseloseHashCode(key: string): number {
    var hash: number = 0;
    for (var i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }

    return hash % 35;
  }
}

这里将获取键值码过大我们可以通过取模形式对其进行简化。

let tutHashTable = new HashTable();
tutHashTable.put("angular", "javascript");
tutHashTable.put("spring", "java");
tutHashTable.put("flask", "python");

11 - angular
29 - spring
4 - flask