JavaのObject.hashCodeは結構衝突する件

Hash値の計算手抜きしてObject.hashCode使ってたけど、どうも衝突が発生している疑惑があったので、確かめてみました。結果としては、かなり衝突するということがわかりました。きちんとMD5とかSHAとか使ったほうがいいですねｗ

テスト

ランダムな20~30文字の小文字アルファベットの文字列からhashCodeを計算し、Hash値の衝突数を調べる

テストに使ったコード

import java.util.Random

object Main{

    def main(args : Array[String]) = {

        var m : Map[Int,String] = Map()
        var conflict = 0

        def check = {
            val s = randomString
            val hashCode = s.hashCode
            if(m.contains(hashCode)){
                if(m(hashCode) != s){
                    println("Find same hashCode: " + s + " and " + m(hashCode))
                    conflict += 1
                }
            }else{
                m = m +( hashCode -> s)
            }
        }

        val repeat = if(args.length > 0) args(0).toInt else 100

        (0 until repeat).foreach( _ => check)

        println("%s / %s conflics".format(conflict,repeat))

    }
    val r = new Random
    def randomString = {
        val chars = r.nextInt(10) + 20
        (0 to chars).foldLeft("")( (s,i) => { s + ('a' + r.nextInt(26)).asInstanceOf[Char]})
    }
}

実行結果

Tags

• Tweet