C g*_*ics 1 java hashtable hashmap
我已经在hashmap或hashtable中研究了这个相关的问题Rehashing进程.但是,我需要知道如何正在执行重复过程.例如,如果loadfactor是.75;
1-这是否意味着我们忘记了现有的hashTable,并且对于每个现有的条目,我们逐个获取它们,并且这次使用新的哈希函数将它们重新输入到新的桶组中？
2-如果是这样那么重新表达的表现是什么,比如退出n个条目.O(n)摊销吗？
这是否意味着我们忘记了现有的hashTable,并且对于每个现有的条目,我们逐个获取它们并使用新的哈希函数将它们重新输入到新的桶集中？
是的,当基础数组被认为太小时会发生这种情况.我们必须重新计算每个条目的哈希值,因为新哈希表根据其大小具有不同的压缩函数.
如果是这样那么重新表达的表现是什么,比如退出n个条目.O(n)摊销吗？
是的,对于前一个数组中的每个条目,都会计算一个新的哈希并重新输入该条目.如此O(n)摊销.根据桶链表的实现方式,最坏的情况可能是O(n^2)因为所有条目都可能在同一个桶中输入.
| 归档时间： |
|
| 查看次数： |
1271 次 |
| 最近记录： |