《算法导论》第11章 散列表 (3)开放寻址

前一节介绍是最简单的冲突解决方法-链接法。开放寻址与链接法不同，所有元素都放在散列表内。

在这种方法中，散列表可能会被填满。开放寻址不需要指针，只需要计算出要存取的各个槽。

由于不用存储指针而节省的空间可以提供更多的槽。

有三种技术常用来计算开放寻址法中的探查序列：线性探查、二次探查和双重探查。

下面的实现中，三种方法的差别只在计算探查序列的那一行代码。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE 20

typedef struct _Entry {    
     char *key;
     char *val;
} Entry;

// 指针数组
Entry *hashmap[SIZE];

// Same as hashcode when String put to HashMap
unsigned hashcode(char *key)
{
     // Ensure >> is logical shift
     unsigned h = 0;

     // String.hashcode()
     do h = 31 * h + *key++;
     while (*key != '\0');    

     // HashMap.hash()
     h ^= (h >> 20) ^ (h >> 12);
     return h ^ (h >> 7) ^ (h >> 4);
}

Entry * hashmap_search(char *key)
{
     unsigned h = hashcode(key) % SIZE;
     unsigned h2 = h;
     Entry *entry = hashmap[h];
     while (entry != NULL) {
          if (strcmp(entry->key, key) == 0) {
               return entry;
          }

          // 线性探查。不同探查方法差别只在这一行。
          h = (h + 1) % SIZE;
          entry = hashmap[h];

          if (h == h2)
               break;
     }
     return NULL;
}

char * hashmap_insert(char *key, char *val)
{
     unsigned h = hashcode(key) % SIZE;
     printf("Insert %s - %s to bucket %d\n", key, val, h);
    
     // Find duplicate key, replace it then return old value
     unsigned h2 = h;
     Entry *entry = hashmap[h];
     while (entry != NULL) {
          if (strcmp(entry->key, key) == 0) {
               char *oldVal = entry->val;
               entry->val = val;
               return oldVal;
          }

          // Linear search
          h = (h + 1) % SIZE;
          entry = hashmap[h];

          // Check if loop to initial bucket
          if (h == h2)
               break;
     }

     // Not found, create new node to save key&val pair
     if (entry == NULL) {
          entry = malloc(sizeof(Entry));
          entry->key = key;
          entry->val = val;
          hashmap[h] = entry;
     }    

     return val;
}

void hashmap_print()
{    
     Entry *entry;
     int i;
     for (i = 0; i < SIZE; i++) {
          entry = hashmap[i];
          if (entry == NULL)
               printf("%d: null\n", i);
          else
               printf("%d: %s - %s\n", i, entry->key, entry->val);
     }
     printf("\n");    
}

int main(void)
{
     // Compare to String.hashcode() in JDK
     printf("%d\n", hashcode("helloworld"));

     hashmap_insert("aabb", "value1");
     hashmap_insert("ccdd", "value2");
     hashmap_insert("i'mcdai", "value3");

     int i;
     for (i = 0; i < 2 * SIZE + 5; i++) {
          char *key = calloc(sizeof(char), 10);
          char *val = calloc(sizeof(char), 10);
          sprintf(key, "%s%d", "aabbcc", i);
          sprintf(val, "%s%d", "val ", i);
          hashmap_insert(key, val);
     }

     // Insert duplicate key
     printf("%s\n", hashmap_insert("i'mcdai", "dupdup"));

     hashmap_print();

     printf("%s\n", hashmap_search("i'mcdai")->val);
    
     hashmap_print();

     return 1;
}