c++ - Cormen 书后的 HashSearch 和 HashInsert 函数实现

Question

对于我的算法，我需要另一个名为 h(k, i) 的函数，我认为它会搜索散列以查看它是否为空，然后将元素插入到 i 位置，但我不确定。有人可以向我解释那个功能吗？谢谢。到目前为止，这是我的代码。

  #include <iostream>
  using namespace std;
  #define hashSize 1000
  typedef struct hashElem{
      char* date;
      char* holiday;
  }hashElem;

  typedef struct hash{
      struct hashElem element;
      struct hash* next;
  }hash;

  void h(hash* hashTable[hashTable],int index)
  {

  }

  int hashInsert (hash* hashTable[hashSize],int k)
  {
      int index=0,index2;
      do
      {
          index2=h(k,index);
          if (hashTable[index2]== NULL) {
              hashTable[index2] = k;
              return index2;
          }
          else
              index=index+1;
      }
      while (index == hashSize);
      printf ("Hash Table Overflow");
  }
  int hashSearch (hash* hashTable[hashSize],int k){
      int index=0,index2;
      do
      {
          index2=h(k,index);
          if (hash* hashTable[index2]==k)
              return index2;
          index=index+1;
      }
      while (hash* hashTable[index2]==NULL || index=hashSize);
      return NULL;
        }
  int main() {
      cout << "Hello, World!" << endl;
      return 0;
  }

Answer 1

您的“h 函数”是一个散列函数，它以一个键作为输入并返回该键在散列表中的位置。

一个简单的哈希函数可以是return key % tablesize。

显然，这种简单的哈希函数可能会导致不同的键具有相同的位置，称为“冲突”。选择合适的哈希函数和选择解决冲突的方法是一个广泛的话题。

在某些情况下，我们可以找到一个完美的哈希函数来避免冲突，这是一个更难的话题。

通常在哈希函数中我们不会搜索整个哈希表并找到一个空位置返回，因为我们预计哈希函数需要 O(1) 时间。