我正在寻找哈希表如何工作的解释 - 用像我这样的傻瓜的简单英语!
例如,我知道它需要密钥,计算哈希值(我正在寻找解释如何)然后执行某种模数来计算它存储在存储值的数组中的位置,但这就是我的知识停止的地方.
任何人都可以澄清这个过程吗？
编辑:我没有具体询问如何计算哈希码,而是概述哈希表的工作原理.
我正在尝试检查给定的密钥是否在地图中,有些不能这样做:
typedef map<string,string>::iterator mi;
map<string, string> m;
m.insert(make_pair("f","++--"));
pair<mi,mi> p = m.equal_range("f");//I'm not sure if equal_range does what I want
cout << p.first;//I'm getting error here
那么如何打印p中的内容呢？
.NET有很多复杂的数据结构.不幸的是,它们中的一些非常相似,我不总是确定何时使用一个以及何时使用另一个.我的大多数C#和Visual Basic书籍都在一定程度上谈论它们,但它们从未真正涉及任何真实的细节.
Array,ArrayList,List,Hashtable,Dictionary,SortedList和SortedDictionary之间有什么区别？
哪些是可枚举的(IList - 可以做'foreach'循环)？哪些使用键/值对(IDict)？
内存占用情况如何？插入速度？检索速度？
还有其他值得一提的数据结构吗？
我还在寻找有关内存使用和速度的更多细节(Big-O表示法).
我们习惯说HashMap get/put操作是O(1).但是它取决于哈希实现.默认对象哈希实际上是JVM堆中的内部地址.我们是否确定声称get/putO(1)是否足够好？
可用内存是另一个问题.据我所知,从javadocs,HashMap load factor应该是0.75.如果我们在JVM中没有足够的内存且load factor超出限制怎么办？
所以,看起来O(1)似乎不能保证.它有意义还是我错过了什么？
我看到你如何通过密钥访问你的收藏.但是,哈希函数本身在幕后有很多操作,不是吗？
假设你有一个很好的哈希函数非常有效,它仍然可能需要很多操作.
这可以解释一下吗？
当我们使用a HashTable来存储数据时,据说搜索需要o(1)时间.我很困惑,任何人都可以解释一下吗？
如果我们从Java角度看,那么我们可以说hashmap查找需要恒定的时间.但内部实施呢？对于不同的匹配键,它仍然必须搜索特定的桶(对于哪个键的哈希码匹配).那么为什么我们说hashmap查找需要恒定的时间？请解释.
我想k在n没有选择相同数字两次的情况下随机选择均匀的元素.这有两个简单的方法.
n可能性.将它们洗牌(你不需要通过执行Fisher Yates的第一步来改变它们的
所有n数字).选择第一个.这种方法需要时间(假设分配一个大小的数组需要
时间)和空间.如果相对于非常小,这是一个问题.kkkO(k)nO(1)O(n)kn[0, n-1].当元素在集合中时,然后选择一个新数字.这种方法占用O(k)空间.运行时分析要复杂一些.如果k = theta(n)那时运行时间是
O(k*lg(k))=O(n*lg(n))因为它是优惠券收集器的问题.如果k相对较小n则需要稍微多于O(k)因为选择相同数字两次的概率(尽管很低).这在空间方面优于上述解决方案,但在运行时方面更差.我的问题:
是否有O(k)时间,O(k)空间算法为所有k和n？
我遇到了一个断言HashSet <T> .Contains()是一个O(1)操作.这令我感到惊讶,因为我遇到的每次哈希讨论都提到了碰撞的可能性,可能导致O(n)运行时间.
好奇,我查看了HashSet <T> .Contains和HashTable.Contains的文档.两种方法的文档都提出了同样的主张.
当我查看反射器时,HashSet <T> .Contains()是用for循环实现的,它通过一个包含具有相同散列值的槽列表.
现在可以肯定的是,那些关于哈希的讨论也提到了一个好的哈希算法可以避免冲突,在这种情况下查找确实是O(1).但我对Big O符号的理解是,它是最糟糕的运行时间,而不是最好的.
O(1)声明是否错误？或者我错过了什么？