AcWing 840. 模拟散列表 ( JavaScript )
原题链接
简单
作者:
gaobowen
,
2019-11-24 18:48:19
,
所有人可见
,
阅读 715
拉链法
//静态单链表
let val = new Int32Array(100010); //大于100003
let idx = 1;
let next = new Int32Array(100010);
let mod = 100003;
let hash = new Uint32Array(100010);//存储单链表头节点
let insert = x => {
//模负数转正数
let h = (x % mod + mod) % mod;
val[idx] = x;
if (!hash[h]) {//创建头节点
hash[h] = idx;
next[idx] = -1;
} else {//链表尾部添加,不添加重复元素
for (let i = hash[h]; i !== -1; i = next[i]) {
if(val[i] === x) break;
if (next[i] === -1) {
next[i] = idx;
next[idx] = -1;
}
}
}
idx++;
}
//始终往头节点添加,不判断重复元素
let insert2 = x => {
let h = (x % mod + mod) % mod;
val[idx] = x;
//创建一个新的头节点,指向当前头
next[idx] = hash[h];
hash[h] = idx++;
}
let query = x => {
let h = (x % mod + mod) % mod;
if(hash[h]) {
for (let i = hash[h]; i !==-1; i = next[i]) {
if(val[i] === x) return 'Yes';
}
}
return 'No';
}
开放寻址法
/*
开放寻址法
开辟一个输入个数的2~3倍的空间来存放值,避免冲突
*/
let mod = 200003;
let hash = new Array(200010);
//返回x在hash表中的实际位置,若不存在则返回x在hash表中应该插入的位置,
//判断 hash[t] === undefined 即可知道x是否已经在hash表中
let find = x => {
let t = (x % mod + mod) % mod;
while (hash[t] !== undefined && hash[t] !== x) {
t++;
if (t > mod) t = 0;//找到表末尾还没找到,则跳到表头开始找
}
return t;
}
let insert = x => {
let t = find(x);
hash[t] = x;
}
let query = x => {
let t = find(x);
return hash[t] === undefined ? 'No' : 'Yes';
}
let buf = '';
process.stdin.on('readable', function () {
let chunk = process.stdin.read();
if (chunk) buf += chunk.toString();
});
let getInputNums = line => line.split(' ').filter(s => s !== '').map(x => parseInt(x));
let getInputStr = line => line.split(' ').filter(s => s !== '');
process.stdin.on('end', function () {
let n = 0;
buf.split('\n').forEach(function (line, lineIdx) {
if (lineIdx === 0) {
let a = getInputNums(line);
n = a[0];
} else if (lineIdx <= n) {
switch (line[0]) {
case 'I': {
let arr = getInputNums(line.slice(1));
insert(arr[0]);
break;
}
case 'Q': {
let arr = getInputNums(line.slice(1));
console.log(query(arr[0]));
break;
}
}
}
});
});