Kotlinでデータ構造 ハッシュテーブル編 [Kotlin]

やること

データ構造のハッシュテーブルをKotlinで実装する方法について解説します。

参考

この記事では酒井潤さんが「アルゴリズムとデータ構造」をpythonで解説されてるudemyの講座を基にKotlinで再現しています。
酒井さんのツイート
https://twitter.com/sakaijun/status/1322222298422632449
講座url
https://udemy.com/course/python-algo/?couponCode=80515F7DEDBC4776BF87

ハッシュテーブルとは

データ構造の一つ。 ハッシュテーブルとは、データ構造の一つで、標識（キー：key）と対応する値（value）のペアを単位としてデータを格納し、キーを指定すると対応する値を高速に取得できる構造。https://e-words.jp　より引用

[格納する仕組み]
n個のリストを生成しておく。
文字列から0~nのいずれかの数値を導き出すハッシュ関数を作る。
キー：keyをハッシュ関数にかけて返された数番目のリストにkeyとvalueを格納する。

[取得する仕組み]
keyをハッシュ関数にかけて複数あるリストの内、格納されているリストを特定しそのリストから取得する。

#実装(初期化)

private class HashTable {
    val size: Int = 10  //tableに格納するリストの個数(今回は10で固定)
    val table: List<MutableList<Pair<String, Any>>> 

    init {
        val list = mutableListOf<MutableList<Pair<String, Any>>>()
        for (i in 0 until size) list.add(mutableListOf())
        table = list
    }
}

tableは要素として、Pair<String, Anyを格納するMutableListをsize個持っている。
PairのStringにはkey、Anyにはvalueを格納する。

#hashメソッド

    private fun hash(key: String): Int{
        val hash = key.hashCode()
        return hash.absoluteValue % size
    }
//sizeが10の場合、　println(hash("erutaso"))  -> 1

ハッシュテーブルの心臓部。同じ文字列を入れた場合必ず同じ数値が返ってくるようにする。
hashCode( )でStringをIntに変換。ただhashCode( )メソッドは負の数を返すことがあるので、absoluteValueで絶対値を取得し、sizeで割った余りを求めることで0~size内の数値を取得することができる。

#isExistsメソッド

private fun isExists(key: String, index: Int): Int{
        val firsts = mutableListOf<String>()
        table[index].forEach {
            firsts.add(it.first)
        }
        var result = -1
        firsts.forEachIndexed {index, value ->
            if (value == key) result = index
        }
        return result
    }

引数として渡されてきたkeyがすで使われているkeyかどうかを判定。すでに使われているkeyだった場合、そのkeyで格納されている要素のインデックスを返す。使われていなかった場合-1を返す。

#addメソッド

fun add(key: String, value: Any){
        val index = hash(key)
        val detailIndex = isExists(key, index)
        if (detailIndex == -1){
            table[index].add(Pair(key, value))
        }else table[index][detailIndex] = Pair(key, value)
    }

ハッシュテーブルに要素を追加するメソッド。
index　大枠のリスト内の何番目のリストに値を追加するかをhash(key)で求めて代入している
detailIndex 　大枠のリスト内のindex番目のリストに同じkeyで保存されている要素があるかをisExists(key, index)で調べている。ある場合はそのインデックス番号が、ない場合-1が返される。その後if (detailIndex == -1)によって分岐し追加or更新を行う。

#getメソッド

fun get(key: String): Any{
        val index = hash(key)
        var result: Any? = null
        val detailIndex = isExists(key, index)
        if (detailIndex != -1) result = table[index][detailIndex]
        return result ?: "key = $key: There is no such key."
    }

addメソッドと同様に処理を分岐させる。if (detailIndex != -1)がtrueになる場合detailIndexを使って取得する。

#全コード

private class HashTable {
    val size: Int = 10
    val table: List<MutableList<Pair<String, Any>>>

    init {
        val list = mutableListOf<MutableList<Pair<String, Any>>>()
        for (i in 0 until size) list.add(mutableListOf())
        table = list
    }

    private fun hash(key: String): Int{
        val hash = key.hashCode()
        return hash.absoluteValue % size
    }

    fun add(key: String, value: Any){
        val index = hash(key)
        val detailIndex = isExists(key, index)
        if (detailIndex == -1){
            table[index].add(Pair(key, value))
        }else table[index][detailIndex] = Pair(key, value)
    }

    fun get(key: String): Any{
        val index = hash(key)
        var result: Any? = null
        val detailIndex = isExists(key, index)
        if (detailIndex != -1) result = table[index][detailIndex]
        return result ?: "key = $key: There is no such key."
    }

    private fun isExists(key: String, index: Int): Int{
        val firsts = mutableListOf<String>()
        table[index].forEach {
            firsts.add(it.first)
        }
        var result = -1
        firsts.forEachIndexed {index, value ->
            if (value == key) result = index
        }
        return result
    }

    fun remove(key: String){
        val index = hash(key)
        val detailIndex = isExists(key, index)
        if (detailIndex != -1) table[index].removeAt(detailIndex)
    }

    fun printTable(){
        for (i in 0 until size){
            if (!table[i].isEmpty()){
                print("$i -> ")
                println(table[i])
            }
        }
    }

}

#入出力例

    val ht = HashTable()
    ht.add("艦長", "岬 明乃")
    ht.add("副長", "宗谷 ましろ")
    ht.add("水雷長", "西崎 衣")
    ht.add("炊事委員", "杵咲 ほまれ")
    ht.add("機関長", "柳原 麻侖")
    ht.printTable()
    println(ht.get("水雷長"))
    ht.remove("副長")
    ht.printTable()

//結果　　
//    0 -> [(水雷長, 西崎 衣), (機関長, 柳原 麻侖)]
//    2 -> [(炊事委員, 杵咲 ほまれ)]
//    5 -> [(艦長, 岬 明乃)]
//    6 -> [(副長, 宗谷 ましろ)]
//    (水雷長, 西崎 衣)
//    0 -> [(水雷長, 西崎 衣), (機関長, 柳原 麻侖)]
//    2 -> [(炊事委員, 杵咲 ほまれ)]
//    5 -> [(艦長, 岬 明乃)]

add、get、removeも問題なく動いてますし、"水雷長"と"機関庁"ではhashした結果が0で被っていますが、問題なく格納できています！(まだ見てない方はアニメ「ハイスクール・フリート」を要チェック)

#終わり
データ構造をコードに起こす際に大事なのは仕組みを再現することだと思うので、同じ言語でもたくさんの実装の仕方があると思います。なので今回のコードは一つの例程度に思ってください。
アルゴリズムとデータ構造の解説はpythonやC言語でされてることが多いので、Kotlinしか知らんけど勉強したいという方の参考になれば！