c - 散列表搜索比链表搜索慢

Question

我有一个树结构，其中每个节点都包含其名称以及使用哈希表对其的引用。

我尝试使用链表搜索结构中的节点一次，并使用哈希表搜索一次。链表搜索比哈希表更快。什么情况下哈希表搜索比链表搜索慢？

这是同时进行搜索的代码

 /* if there is a hasthable defined in the dpal object search using it */
 if(!htbl){
    for (i= 0, j = 0; dpal_path[i] != 0; i++)
    {
      if (dpal_path[i] == sep)
      {
        khash_str_t key;
        khiter_t entry;
        const char *token = &dpal_path[j];
        size_t length = i-j;
        j=i+1;
        htbl = &start_obj->obj_string_htbl;
        key.str = token;
        key.len = length;
        /* look for the dpal object in the hashtable */
        entry = kh_get_str2int32(htbl, key);
        if (entry != kh_end(htbl)) {
          start_obj=(dpal_obj_t*)kh_value(htbl, entry); 
          result = start_obj;
        }
        else{
          result=DPAL_OBJ_HANDLE_INVALID;
          break;
        }
      }
    }
  }
  /* otherwise search for it using linked list structure */
  else{
    for (i= 0, j = 0; dpal_path[i] != 0; i++)
    {
      if (dpal_path[i] == sep)
      {
        const char *token = &dpal_path[j];
        size_t length = i-j;
        j=i+1;
        if(start_obj != NULL){
          start_obj = start_obj->child;
        }
        while ((start_obj != NULL)){
          if(strncmp(token, start_obj->static_props.name, length) == 0){
            result = start_obj;
            break; 
          }
          /* get next handle in flat hierarchy */
          start_obj=start_obj->next;
          if(start_obj == NULL){
            result = DPAL_OBJ_HANDLE_INVALID;
          }
        }
      }
    }
  }

Answer 1

这主要取决于 for 循环的每次迭代中要搜索的元素数量(即 start_obj->next 形成的链表有多长)以及 kh_get_str2int32、kh_end 和 kh_value 的计算成本如何。如果不知道链表的平均长度和哈希表函数的实现，就不可能给出更明确的答案。