哈希冲突

1. 开放地址法
   线性探测法 = (f(key)+) mod m ( = 1, 2, 3, 4,...,m-1)
   二次探测法 = (f(key)+) mod m ( = , , ,,...,,,q<=m/2)
   随机探测法 = (f(key)+) mod m (随机的数列)
2. 链地址法
3. 公共溢出区法

线性探测法例子

// init

# define UNSUCCESS 0
# define HASHSIZE 12 /**数组长度**/
# define NULLKEY -32768
typeof struct {
  int *elem;
  int count;
}HashTable;
int m = 0; /**散列表表长**/

// init
Status InitHashTable(HashTable *H) {
  int i;
  m = HASHSIZE;
  H->count = m;
  H->elem = (int *) malloc(m * sizeof(int));
  for(i=0;i<m;i++)
    H->elem[i] = NULLKEY;
  return OK;
}

// 散列函数
int Hash(int key) {
  retrun key % m;
}

// 插入
void InsertHash(HashTable *H, int key) {
  int addr = Hash(key)
  while(H->elem[addr] != NULLKEY) {
    addr = (addr + 1) % m;
  }
  H->elem[addr] = key;
}

// 查询
Status SearchHash(HashTable *H, int key, int *addr) {
  *addr = Hash(key);
  while(H->elem[addr] != key){ // 发生冲突
    *addr = (*addr + 1) % m;
    if(H->elem[addr] == NULLKEY || addr = Hash(key))
      // 如果地址没有被更改或者已经循环到原来的位置了
      return UNSUCCESS;
  }
  return SUCCESS;
}