散列表（哈希表）
实现一个基于链表法解决冲突问题的散列表
class HashTable {
constructor() {
this.table = [];
}
loseHashCode(key) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash += key.charCodeAt(i);
}
return hash;
}
put(key, value) {
const position = this.loseHashCode(key);
if (this.table[position] == undefined) {
this.table[position] = new LinkedList();
}
this.table[position].append(key, value);
}
get(key) {
const position = this.loseHashCode(key);
if (this.table[position] != undefined) {
const current = this.table[position].getHead();
while (current.next) {
if (current.element.key === key) {
return current.element.value;
}
current = current.next;
}
if (current.element.key === key) {
return current.element.value;
}
return undefined;
}
return undefined;
}
remove(key) {
const position = this.loseHashCode(key);
if (this.table[position] !== undefined) {
const current = this.table[position].getHead();
do {
if (current.element.key === key) {
current.element.remove(key);
if (this.table[position].isEmpty()) {
this.table[position] = undefined;
}
return true;
}
current = current.next;
} while (current);
}
return false;
}
}
实现一个 LRU 缓存淘汰算法
class LRUCache {
constructor(capacity) {
this.capacity = capacity
this.map = new Map()
}
get(key) {
let val = this.map.get(key)
if (typeof val === 'undefined') { return -1 }
this.map.delete(key)
this.map.set(key, val)
return val
}
put(key, value) {
if (this.map.has(key)) {
this.map.delete(key)
}
this.map.set(key, value)
let keys = this.map.keys()
while (this.map.size > this.capacity) { this.map.delete(keys.next().value) }
}
}
参考资料
