[简单研究] 大数据检索:哈希表与字典 1

[1] Key检索与Value检索

问题:假设有a,b两个文本,每行一个数据,都有近1000W行,请导出a,b数据的交集.

这个问题用哈希表/字典只要几十秒就解决了,如果用数组,只怕要到海枯石烂.

虽然我们知道要用哈希表/字典来解决问题,那将数据保存为Key还是Value?

如果保存为Key,就调用ContainsKey()方法来检索,这是哈希表/字典的效率.

如果保存为Value,就调用ContainsValue()方法来检索,它是数组的效率.

所以用哈希表/字典保存数据,数据保存的位置还是很有讲究的.

[2] 哈希表与字典的效率之差

哈希表的定义如下:

$hash=@{} 

字典的定义如下,注意TKey指的是Key的数据类型,TVal是Value的数据类型.

字典定义的数据类型要与保存的数据一致.

$dic=New-Object 'System.Collections.Generic.Dictionary[TKey,TVal]'

看下面一段代码:

#哈希表测试
Measure-Command{
    $hash=@{}
    foreach($i in 1..30000000)
    {
        $hash.Add($i,$i)
    }
    foreach($i in 1..30000000)
    {
        [void] $hash.ContainsKey($i)
    }
}

#字典测试
Measure-Command{
    $dic=New-Object 'System.Collections.Generic.Dictionary[int,int]'
    foreach($i in 1..30000000)
    {
        $dic.Add($i,$i)
    }
    foreach($i in 1..30000000)
    {
        [void] $dic.ContainsKey($i)
    }
}
pause

运行结果:

Days              : 0
Hours             : 0
Minutes           : 1
Seconds           : 13
Milliseconds      : 318
Ticks             : 733182244
TotalDays         : 0.000848590560185185
TotalHours        : 0.0203661734444444
TotalMinutes      : 1.22197040666667
TotalSeconds      : 73.3182244
TotalMilliseconds : 73318.2244

Days              : 0
Hours             : 0
Minutes           : 1
Seconds           : 1
Milliseconds      : 530
Ticks             : 615306849
TotalDays         : 0.000712160704861111
TotalHours        : 0.0170918569166667
TotalMinutes      : 1.025511415
TotalSeconds      : 61.5306849
TotalMilliseconds : 61530.6849

由此可以看出,字典的效率略胜一筹