作业 - 第 5 周

class Cache {
	constructor() {
		this.vNodes = [];
	}
  
	addNode(node) {
		// 0. if it is first node, add virtual node which has max hash
		const isFirstNode = this.vNodes.length == 0;
		if (isFirstNode) {
			this.vNodes.push({
				hash: Math.pow(2, 32),
				node: node
			});
		}
		// 1. add virtual nodes to this.vNodes
		const VNODE_COUNT = 100;
		for (let i = 0; i < VNODE_COUNT; i++) {
			this.vNodes.push({
				hash: Math.floor(Math.random() * Math.floor(Math.pow(2, 32))), // random: 0 ~ 2^32
				node: node
			})
		}
		// re-sort this.vNodes
		this.vNodes.sort((a, b) => a.hash - b.hash);
	}
  findNode(hash) {
    for (let i = 0; i < this.vNodes.length; i++) {
      const vNode = this.vNodes[i];
      if (vNode.hash >= hash) {
        return vNode.node;
      }
    }
		throw new Error('hash is over 2^32');
	}
}