How it works
Find a key in a separate-chaining hash table by scanning the bucket chosen by the hash function.
Implementation
function hashLookupOp(state, target) { const bucketHead = state.bucketHead; const nodeKey = state.nodeKey; const nodeNext = state.nodeNext; const numBuckets = state.numBuckets; const bucket = target % numBuckets; probeSlot(bucket); let current = bucketHead[bucket]; while (current !== -1) { visitNode(current); compareKeys(current, target); if (nodeKey[current] === target) { reportFound(current); return; } current = nodeNext[current]; } reportNotFound(); }
def hashLookupOp(state, target): bucketHead = state.bucketHead nodeKey = state.nodeKey nodeNext = state.nodeNext numBuckets = state.numBuckets bucket = (target % numBuckets) probeSlot(bucket) current = bucketHead[bucket] while (current != -1): visitNode(current) compareKeys(current, target) if (nodeKey[current] == target): reportFound(current) return current = nodeNext[current] reportNotFound()
#include <vector> #include <algorithm> void hashLookupOp(int state, int target) { auto bucketHead = state.bucketHead; auto nodeKey = state.nodeKey; auto nodeNext = state.nodeNext; auto numBuckets = state.numBuckets; auto bucket = (target % numBuckets); probeSlot(bucket); auto current = bucketHead[bucket]; while((current != -1)) { visitNode(current); compareKeys(current, target); if((nodeKey[current] == target)) { reportFound(current); return; } current = nodeNext[current]; } reportNotFound(); }
public void hashLookupOp(int state, int target) { var bucketHead = state.bucketHead; var nodeKey = state.nodeKey; var nodeNext = state.nodeNext; var numBuckets = state.numBuckets; var bucket = (target % numBuckets); probeSlot(bucket); var current = bucketHead[bucket]; while((current != -1)) { visitNode(current); compareKeys(current, target); if((nodeKey[current] == target)) { reportFound(current); return; } current = nodeNext[current]; } reportNotFound(); }
#include <stdio.h> void hashLookupOp(int state, int target) { var bucketHead = state.bucketHead; var nodeKey = state.nodeKey; var nodeNext = state.nodeNext; var numBuckets = state.numBuckets; var bucket = (target % numBuckets); probeSlot(bucket); var current = bucketHead[bucket]; while((current != -1)) { visitNode(current); compareKeys(current, target); if((nodeKey[current] == target)) { reportFound(current); return; } current = nodeNext[current]; } reportNotFound(); }