相关疑难解决方法(0)

std::unordered_map 保证O(1)时间搜索,但它如何管理碰撞？

Cppreference声称

无序映射是一个关联容器,包含具有唯一键的键值对.元素的搜索,插入和删除具有平均的恒定时间复杂度.

假设所有哈希码都相同的情况,内部如何处理冲突？

如果哈希码对每个键都是唯一的,那么我的假设将完全错误.在这种情况下,如何在没有冲突的情况下创建唯一的哈希码？

std::unordered_map哈希函数采用什么方法来保证O(1)搜索？

据我所知，std :: unordered_map用于快速访问元素。这是通过存储和比较密钥哈希而不是密钥本身来实现的。同样，无序意味着其中的元素未排序。但是要快速访问元素，需要对项目进行排序，以便能够使用二进制搜索找到请求的项目。

• 这是否意味着unordered_map中的项目是根据其哈希键进行排序的，而导致unordered_map比映射到访问元素的映射更快的唯一原因是比较哈希值通常比比较键值要快得多？
• 如果是这样，则在unordered_map和map之间进行选择取决于键的类型。我对吗？

• 最后一个问题是为什么unordered_map不能像地图一样获得Compare模板参数？unordered_map如何仅通过相等的运算符比较键哈希？

  template <class Key,
            class T,
            class Compare = less<Key>,
            class Alloc = allocator<pair<const Key,T> >
            > class map;
  
  template <class Key,
            class T,
            class Hash = hash<Key>,
            class Pred = equal_to<Key>,
            class Alloc = allocator< pair<const Key,T> >
            > class unordered_map;
  

  Run Code Online (Sandbox Code Playgroud)

我有一份我正在进行的任务,而且我无法掌握教授以明确某些事情.我们的想法是,我们正在使用一组给定的单词编写一个anagram解算器,我们将其存储在3个不同的字典类中:Linear,Binary和Hash.

因此,我们从文本文件中读取单词,对于前2个字典对象(线性和二进制),我们将单词存储为ArrayList ......很简单.

但对于HashDictionary,他希望我们将这些单词存储在HashTable中.我只是不确定HashTable的值是什么,或者为什么要这样做.说明说我们将这些单词存储在Hashtable中以便快速检索,但我只是不明白这一点.将字词存储在arraylist中是有意义的,但我只是不确定键/值配对如何帮助字典.

也许我没有提供足够的细节,但我想也许有人会看到类似这样的事情并且对他们来说很明显.

我们的每个类都有一个contains方法,它返回一个布尔值,表示传入的单词是否在字典中,因此线性搜索arraylist,二进制搜索arraylist,我'我不确定哈希....

在最近的一次采访中,我被问到如何用Java 编写自己的HashMap/ Hashtable实现.

我不知道这一点所以我回答的唯一问题就是我们可以HashMap通过使用Array 来实现,因为只有这样才能提供持续时间访问,如果你知道索引的话.关键是编写哈希函数以最小化冲突.

你能告诉我怎么写自己的Hashmap/ Hashtable？