hash.cpp

经典c++程序的实现

// Compile check for hash functions
#include <iostream.h>

#include "..\include\book.h"

#define HASHSIZE 101
#define KEY short
#define ELEM short
#define key(X) (X)
#define EMPTY -1
#define UNSUCCESSFUL -2
#define ERROR cout << "Duplicate value " << "R" << "\n"

KEY T[HASHSIZE];
int M = HASHSIZE;

int ELFhash(char* key) {
  unsigned long h = 0;
  while(*key) {
    h = (h << 4) + *key++;
    unsigned long g = h & 0xF0000000L;
    if (g) h ^= g >> 24;
    h &= ~g;
  }
  return h % M;
}

int h(char x[10]) {
  int i, sum;
  for (sum=0, i=0; i<10; i++)
    sum += (int) x[i];
  return(sum % M);
}

int h(int x) {
  return(x % 16);
}

int p(KEY K, int i) { return i; }

void hashInsert(ELEM R) {     // Insert record R into hash table T
  int home;                   // Home position for R
  int pos = home = h(key(R)); // Initial position on probe sequence
  for (int i=1; key(T[pos]) != EMPTY; i++) {
    pos = (home + p(key(R), i)) % M; // Next slot on probe sequence
    if (key(T[pos]) == key(R)) ERROR; // Don't allow duplicates
  }
  T[pos] = R;                 // Insert R
}

ELEM hashSearch(KEY K) { // Search for the record with key K
  int home;              // Home position for K
  int pos = home = h(K); // Initial position on probe sequence
  for (int i = 1; (key(T[pos]) != K) && (key(T[pos]) != EMPTY); i++)
    pos = (home + p(K, i)) % M;  // Next position on probe sequence
  if (key(T[pos] == K)) return T[pos];  // Found it
  else return UNSUCCESSFUL;      // K not in hash table
}

int main() {
return 0;
}