人間でもわかる連想配列

連想配列を実装したいと思いませんか？

と、言うわけでいろんな実装をしてみましょう

連想配列とは？

連想配列は、key(鍵)とvalue(値)をセットで持ち、keyを渡すとvalueを取れるというものです。
特徴としてはkeyが数字でなくてもよく意味のある文字列が使用できるのでコードが読みやすくなるのです。
まぁ詳しいことはググってください

実装しよう

実装に当って、仕様を決めましょう。以下の3点を実装するものとします。
・連想配列のkeyはアルファベット(26種)から成る文字列。valueは数字(0以上の整数)
・連想配列にデータを追加する.add(key, value)　を持つ。(keyが重複する場合は、valueを上書きする)
・連想配列からデータを取り出す .getValue(key) を持つ。(keyに対応するValueが存在しない場合は-1を返す)

ソートやらなんやら、そういった機能は今回は実装しません

言語は最近業務で使ってるVBで書くのでよろしくです
あと、コードは結構適当です。(境界値エラー出ても、そこはまぁ本質ではないんで見逃してくれ)

単純に実装しよう

まずは配列で実装しましょう。連想”配列”ですからね

sample

Public Class asso

    Private arryKey(100) As String

    Private arryValue(100) As Integer

    Public Sub New()
        For Each item In arryKey
            item = String.Empty
        Next
        For Each item In arryValue
            item = -1
        Next
    End Sub

    Public Sub add(ByVal key As String, ByVal value As Integer)
        For i As Integer = 0 To 99
            If arryKey(i) = key Then
                arryValue(i) = value
                Return
            ElseIf arryKey(i) = String.Empty Then
                arryKey(i) = key
                arryValue(i) = value
            End If
        Next
    End Sub

    Public Function getValue(ByVal key As String) As Integer
        For i As Integer = 0 To 100
            If arryKey(i) = key Then
                Return arryValue(i)
            End If
        Next
        Return -1
    End Function

End Class

まぁ、いたって普通の、誰でも書けるアレですね。
さて、この実装を評価するにあたって、以下の3点の評価基準を設けましょう
1.データを追加するときにどのぐらい時間がかかるか
2.データを取り出すときにどのぐらい時間がかかるか
3.このクラスがどのぐらいメモリを占有するか

それぞれ見ていくと、
1:格納されているデータ数に比例
2:格納されているデータ数に比例
3:100個分＝連想配列の持つことの出来る最大量のデータに等しい数
と、なります

うーん、効率が悪いですね。
と、言うわけでまずは2を改善してみましょう。

二分探索で実装しよう

二分探索を使って、たかだか10回ぐらいでデータを探すことが出来るようにしちゃいましょう

sample

    Public Function getValue(ByVal key As String) As Integer
        Dim head As Integer = 0
        Dim tail As Integer = 99
        While (1)
            Dim pipot As Integer
            pipot = (head + tail) / 2
            If arryKey(pipot) = String.Empty OrElse arryKey(pipot) < key Then
                head = pipot - 1
            ElseIf arryKey(pipot) > key Then
                tail = pipot + 1
            ElseIf arryKey(pipot) = key Then
                Return arryValue(pipot)
            ElseIf head = tail Then
                Return -1
            End If
        End While
    End Function

getValueだけ実装してみました。これで、たかだか10回程度で検索が終わりますね。
ただ、これにも問題があります。それは
・データが整列していないと意味が無い
ということです。ですので、addも修正しましょう

sample

    Public Sub add(ByVal key As String, ByVal value As Integer)
        Dim pipot As Integer = 0
        For i As Integer = 0 To 99
            If key = arryKey(i) Then
                arryValue(i) = value
                Return
            ElseIf key > arryKey(i) Then
                pipot = i
                Exit For
            End If
        Next
        For i As Integer = 99 To pipot + 1
            arryKey(i) = arryKey(i - 1)
            arryValue(i) = arryValue(i - 1)
        Next
        arryKey(pipot) = key
        arryValue(pipot) = value
    End Sub

こんなもんでしょうか。
さて、ここで皆さん思いませんでしたか？
「おいおい、データを追加するときも二分探索しろよ。」と
そうです。連想配列ではデータの追加は同時にデータの検索(keyの衝突が無いかの確認)を行う必要があるということです。

と、言うわけで検索をしない方法を考えましょう

もう少し効率よく

答えから言ってしまうと、ハッシュを使えば解決できます
ざっくりいうと、「keyから一定のルールに則って数値を生成し、それを配列の添え字に相当させるようにする」という感じです。

まずは、keyから数字を生成してみましょう。
アルファベットをa-zで1~26の値を割り振り、以下のルールで数値を生成しましょう

a(1) = (1文字目のアルファベットに対応した数字 + 0) mod 97
a(n) = {a(n-1) × (n文字目のアルファベットに対応した数字) + (n - 1)} mod 97

まぁ、そこそこバラバラとした値が取れます。
なんで最後に97で割っているかというと、最後に素数で割ることで値がイイ感じでばらけるからです。
(もし、この数式で出てくるのが特定の数字の倍数だったとしても、素数で割ることでそういった事態を防げる。
　ただ、配列の要素100を目いっぱい使うことは出来なくなってしまうのが難点です)
と、いうわけで以下のようなハッシュ関数を追加しましょう。

sample

    Private Function getHashValue(ByVal key As String)
        Dim returnValue As Integer = 1
        For i As Integer = 0 To key.Count - 1
            returnValue = returnValue * getCharValue(key(i)) + i
            returnValue = returnValue Mod 97
        Next
        Return returnValue
    End Function

    Private Function getCharValue(ByVal c As Char)
        Return Asc(c) - Asc("a") + 1
    End Function

これで、keyから数値を生成することが出来ました。
これを使って、以下のようにaddとgetValueを改善しましょう
・addメソッドは、配列のどこに格納するかをgetHashValueメソッドから取得した値で決定する(取得した値=格納するindex)
・getValueメソッドは、受け取ったkeyをgetHashValueに渡し、そこから取得した値をindexとしてデータの有無を判断する

sample

Public Class asso
    Private arryValue(100) As Integer

    Public Sub New()
        For Each item In arryValue
            item = -1
        Next
    End Sub

    Public Sub add(ByVal key As String, ByVal value As Integer)
        Dim index As Integer
        index = getHashValue(key)
        arryValue(index) = value
    End Sub

    Public Function getValue(ByVal key As String) As Integer
        Dim index As Integer
        index = getHashValue(key)
        Return arryValue(index)
    End Function

    Private Function getHashValue(ByVal key As String)
        Dim returnValue As Integer = 1
        For i As Integer = 0 To key.Count - 1
            returnValue = returnValue * getCharValue(key(i)) + i
            returnValue = returnValue Mod 97
        Next
        Return returnValue
    End Function

    Private Function getCharValue(ByVal c As Char)
        Return Asc(c) - Asc("a") + 1
    End Function

End Class

これで、性能がどのように変わったか見てみましょう。

これまで
1:データを追加するときは、格納されているデータ数に比例した時間がかかる
2:データを検索するときは、格納されているデータ数に比例した時間がかかる
3:メモリはデータ100個分(保持できる最大サイズ分)占有する

ハッシュを使ったバージョン
1:一定
2:一定
3:メモリはデータ100個分(保持できる最大サイズ分)占有する

割といい感じに改善されたのではないでしょうか。

と、今日はここまでにしておきます（疲れたので）
気が向いたら続きを書きます