jqu*_*uth 5 c# dictionary hashtable
HashTable或Dictionary的查找时间是否始终为O(1),只要它具有唯一的哈希代码？
如果HashTable有1亿行,那么查找具有1行的内容需要相同的时间吗？
不可以.技术上可行,但获得完全相同的开销量极为罕见.哈希表被组织成桶.Dictionary <>(和Hashtable)使用如下表达式计算对象的桶号:
int bucket = key.GetHashCode() % totalNumberOfBuckets;
因此,具有不同哈希码的两个对象可以在同一个桶中结束.存储桶是List <>,索引器接下来在该列表中搜索关键字O(n),其中n是存储桶中的项目数.
Dictionary <>动态增加totalNumberOfBuckets的值以保持存储桶搜索的效率.当您在字典中输入一亿个项目时,会有数千个存储桶.添加项目时存储桶为空的几率非常小.但如果是偶然的话,是的,检索项目需要花费同样的时间.
随着项目数量的增加,开销量增长非常缓慢.这称为摊销 O(1).
| 归档时间： |
|
| 查看次数： |
5190 次 |
| 最近记录： |