VBA

【VBA】Dictionaryはハッシュテーブルでなのか？

「VBA ハッシュテーブル」で検索するとScripting.Dictionaryの使い方を説明したページがヒットします。

Dictionaryはキーと値のペアを格納できるデータ構造なので、自分もこれはハッシュテーブルだと思って使用しておりました。

しかし、このDictionaryですがデータ件数が増えてくると明らかに速度が遅くなる気がしておりまして、ハッシュテーブルなのか怪しい気がしてきました。

そこで今回はDictionaryが本当にハッシュテーブルなのか検証してみたいと思います。

※Dictionaryの内部構造に詳しいわけではありません。動作検証による推測になります。もし間違っていたらすみません。

ハッシュテーブルとは？

そもそもハッシュテーブルとは何かということについて簡単に記載します。

ハッシュテーブルは、データを素早く検索・追加・削除できるデータ構造の一つで「キー（Key）」と「値（Value）」をペアで管理し、キーのハッシュ値を使ってデータの保存場所を決定します。

キーのハッシュ値を求めるには、特定のハッシュ関数を使用します。ハッシュ関数にはいろいろと種類がありますが、例えばJavaでは以下のようにハッシュ値を求めます。

public int hashCode() {
    int h = 0;
    for (int i = 0; i < length(); i++) {
        h = 31 * h + charAt(i);
    }
    return h;
}

“abc”というキーの場合のハッシュ値を求めると以下のように、96354になります。

h = 0
h = 31 * 0 + 'a' = 97
h = 31 * 97 + 'b' = 3105
h = 31 * 3105 + 'c' = 96354

そして「キーのハッシュ値 % 配列サイズ」のインデックスに値を格納しておきます。

キーが”abc”、配列のサイズが1000だった場合、96354 % 1000 = 354番目のインデックスに”abc”というキーに該当するValueを格納しておきます。

その後、プログラムから「”abc”というキーの値を取り出してくれ」という命令が来た時、”abc”のハッシュ値から354番目のインデックスに入っていることわかるので、354番目にアクセスして値を取り出します。

ハッシュテーブルを使わないとデータが増えると遅くなる

前項で説明した通り、ハッシュテーブルを使用すると目的のデータが格納されている配列のインデックスを1発で当てることができます。

一方でハッシュテーブルを使わない場合は、ループ(線形探索)で値を見つけないといけないです。

例えば、以下のような キーとバリューのペア があるとします。

KeyValue
“apple”“100”
“banana”“200”
“cherry”“300”
“date”“400”
“grape”“500”

このデータを配列として管理し、キー”grape”に対応する値を検索する場合、以下のように探索を行います。

Sub test()
  Dim arrTest() As String
  ReDim arrTest(1, 4)
  
  ' 1次元目にキー、2次元目に値を格納する
  arrTest(0, 0) = "apple"
  arrTest(1, 0) = "100"
  arrTest(0, 1) = "banana"
  arrTest(1, 1) = "200"
  arrTest(0, 2) = "cherry"
  arrTest(1, 2) = "300"
  arrTest(0, 3) = "date"
  arrTest(1, 3) = "400"
  arrTest(0, 4) = "grape"
  arrTest(1, 4) = "500"
  
  ' 線形探索でキー"grape"を探してみる
  For i = 0 To 4
    If arrTest(0, i) = "grape" Then
      MsgBox "grapeの値は" + arrTest(1, i)
      Exit For
    End If
  Next i

End Sub

今回はデータが5件のためFor文のループが最大5回です。しかし、もしデータが100万件の場合はFor文も100万回のループになるため非常に遅くなります。

そのためデータ件数が多い時にはできる限りハッシュテーブルの仕組みを使いたいです。


Dictionaryはデータが増えると遅くなる気がする

ここからが本題ですが、以前Scripting.Dictionaryにて大量のデータを扱ったときにDictionaryからデータを取り出す速度が著しく遅くなったことがあります。

簡単に検証をしてみたいと思います。

まずは以下のコードでDictionaryに1万件程度のデータを格納して取り出すスピードを計測してみます。

Sub test()

    Debug.Print ("開始:" + CStr(Now))
    ' Dictionaryの作成
    Dim l As Long
    Dim dict As Object
    Set dict = CreateObject("Scripting.Dictionary")
    
    For l = 0 To 10000
        dict.Add l, ThisWorkbook.Sheets(1)
    Next l
    
    ' Dictionaryからデータを取得する
    
    Dim ws As Variant
    Set ws = dict.Item(10000)
    Debug.Print ("終了:" + CStr(Now))
End Sub

１万件程度では一瞬で完了したので、一般的なデータ件数で使用する分には問題ないと思います。

次にfor文の回数を10万まで上げてみます。

Sub test()

    Debug.Print ("開始:" + CStr(Now))
    ' Dictionaryの作成
    Dim l As Long
    Dim dict As Object
    Set dict = CreateObject("Scripting.Dictionary")
    
    For l = 0 To 100000
        dict.Add l, ThisWorkbook.Sheets(1)
    Next l
    
    ' Dictionaryからデータを取得する
    
    Dim ws As Variant
    Set ws = dict.Item(100000)
    Debug.Print ("終了:" + CStr(Now))
End Sub

10万件も1秒で完了しました。更に増やして100万件もやってみます。

Sub test()

    Debug.Print ("開始:" + CStr(Now))
    ' Dictionaryの作成
    Dim l As Long
    Dim dict As Object
    Set dict = CreateObject("Scripting.Dictionary")
    
    For l = 0 To 1000000
        dict.Add l, ThisWorkbook.Sheets(1)
    Next l
    
    ' Dictionaryからデータを取得する
    
    Dim ws As Variant
    Set ws = dict.Item(1000000)
    Debug.Print ("終了:" + CStr(Now))
End Sub

10万件で１秒だったのに10倍の100万件では98秒となりました。

ハッシュテーブルを使っているのであれば件数が10倍になっただけで時間が98倍になるのは解せないところです。

Dictionaryの内部構造を知っているわけではないので正確かどうかわからないのですが、ハッシュテーブルを使っているのか少し怪しいなと感じてきています。

（もしくはハッシュテーブルを使っているが、ハッシュ値の計算が凄く時間がかかるのか？）

自作ハッシュテーブルを作成してみる

比較検証として自作のハッシュテーブルを作成した時と速度比較をしてみたいと思います。

まず簡単にハッシュ値を求める関数を作成します。

Function simpleHash(inputString As String) As Long
    Dim i As Long
    Dim hash As Long
    hash = 0

    For i = 1 To Len(inputString)
        hash = hash + Asc(Mid(inputString, i, 1)) * i
    Next i

    simpleHash= hash
End Function

単純なロジックのため衝突が発生しやすいのですが、今回は速度検証なので衝突は無視することにします。（衝突したら後勝ちとする）

Sub test()

    Dim hashTable(0 To 10000000) As String
    Dim key As Long
    Dim index As Long

    Debug.Print ("開始:" + CStr(Now))
    ' ハッシュテーブルの作成
    Dim l As Long
    
    For l = 0 To 10000000
         key = simpleHash("Key_" & CStr(l)) ' ハッシュキーを計算
         index = key Mod 10000000 ' 配列の範囲内に収める
         hashTable(index) = "テストでーす" & CStr(l)
    Next l
    
    ' ハッシュテーブからデータを取得する
    Debug.Print (hashTable(simpleHash("Key_10000000")))
    Debug.Print ("終了:" + CStr(Now))
End Sub

Function simpleHash(inputString As String) As Long
    Dim i As Long
    Dim hash As Long
    hash = 0

    For i = 1 To Len(inputString)
        hash = hash + Asc(Mid(inputString, i, 1)) * i
    Next i

    simpleHash = hash
End Function

上記ロジックでハッシュテーブルから値を取得するスピードを検証すると、下記のような結果となりました。

1万件1秒未満
10万件1秒未満
100万件2秒
1000万件16秒

100万件→1000万件が約10倍の時間になっているので、データを格納するスピードや取り出すスピードは一定であることが予想されます。

Dictionaryでは件数を増やすと、それ以上に時間の増加が見られたのでデータ件数が多くなることによるロスが発生していると推測しています。

とはいえDictionaryで100万件などを扱わない限り問題にならないと思いますが、一応遅くなってくることもあるということを頭に入れておこうと思います。


コメントを残す

メールアドレスが公開されることはありません。

日本語が含まれない投稿は無視されますのでご注意ください。（スパム対策）

ABOUTこの記事をかいた人

VBAによるEXCELアプリケーション開発の業務経験を生かし、日々の業務でもVBAを使用して生産性の向上を図っています。

NEW POST最新の記事

RECOMMENDこちらの記事も人気です。