字体: 小 中 大  

ACE_Hash_Map_Manager的open

iaagssphinx 发表于: 2008-10-27 12:22 来源: ACE 开发者

最新回复

winston at 2008-10-27 13:26:13

不是的。你看看hash的原理吧。冲突的时候，可以用链的形式，继续存储。

newzai at 2008-11-21 21:01:22

ACE_Hash_Map_Manager_Ex/ACE_Hash_Map_Manager 在第一个open打开后，设置了HASH表的大小后，就固定了。
在绑定的过成功不会存在因为HASH Table用完了而导致bind失败 的情况。

如果open的时候指定大小为10，这个时候ACE_Hash_Map_Manager_Ex或ACE_Hash_Map_Manager对象的容量超过10时，依然是成功的。
因为具有相同hash值的元素通过link连接在一起。

此时hash如果容量太小的话，效率就没有那么高了，就不是O(1)的时间效率了。而是 total_size/hash_table_size * O(1)了。

newzai at 2008-11-21 21:12:59

源码如下
{
  size_t loc;
  int result = this->shared_find (ext_id, entry, loc);

  if (result == -1)
    {
      // Not found. 如果该绑定不存在 hashtable时，进行插入。
      void *ptr;
      ACE_ALLOCATOR_RETURN (ptr,
                            this->entry_allocator_->malloc (sizeof (ACE_Hash_Map_Entry<EXT_ID, INT_ID>)),
                            -1);

      entry = new (ptr) ACE_Hash_Map_Entry<EXT_ID, INT_ID> (ext_id,
                                                            int_id,
                                                            this->table_[loc].next_,
                                                            &this->table_[loc]);
      this->table_[loc].next_ = entry;  // 在这里我们可以看到是以列表的形式插入到loc位置的。loc就是EXT_ID的hash值，不同的EXT_ID hash值可能是一样的。在hash值一样时，把他们通过列表链接在一起。我们可以看一下shared_find  函数什么时候返回-1.
      entry->next_->prev_ = entry;
      this->cur_size_++;
      return 0;
    }
  else
    return 1;
}



template <class EXT_ID, class INT_ID, class HASH_KEY, class COMPARE_KEYS, class ACE_LOCK> int
ACE_Hash_Map_Manager_Ex<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>::shared_find (const EXT_ID &ext_id,
                                                                                        ACE_Hash_Map_Entry<EXT_ID, INT_ID> *&entry,
                                                                                        size_t &loc)
{
  loc = this->hash (ext_id) % this->total_size_; // 根据hash值，计算存储的位置。如果open把size设置为1，这个hash map就变成了链表了。

  ACE_Hash_Map_Entry<EXT_ID, INT_ID> *temp = this->table_[loc].next_;

  while (temp != &this->table_[loc] && this->equal (temp->ext_id_, ext_id) == 0) // 在loc位置的link列表查找自己。
    temp = temp->next_;

  if (temp == &this->table_[loc])
    { // 找不到时。。

      errno = ENOENT;
      return -1;
    }
  else
    {
      entry = temp;
      return 0;
    }
}

winston at 2008-11-21 22:31:33

楼上的解释很好。