7 月 02 2008

JavaのString#hashCode()をRubyで再現

Published by haga at 15:52 under ruby

Javaで作ってあるアプリをiPhoneに移植しようと思ったが、まずObjective-Cがわからないので、Rubyに移植してみようと考えた。

移植元のアプリの中でさらっとString#hashCode()を使っていて困った。

http://sdc.sun.co.jp/java/docs/j2se/1.4/ja/docs/ja/api/java/lang/String.html#hashCode()

この文字列のハッシュコードを返します。String のハッシュコードは、次の方法で計算します。
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

上記の通りの計算をしてもRubyでは同じ数値にならない。 どうもJavaのintとRubyのIntegerは挙動が違うからのようだ。

java のInteger int 最大値超えるとどうなるの<br/> http://becomehappy.orz.hm/smithlog/article.php?id=370

Javaのintは-0x80000000~0x7fffffffの間をぐるぐるループしているらしい。<br/> 最大値（2147483647）を超えたら最小値（-2147483648）に戻してやる気遣いが必要だ。

というわけで作ってみたのが下記。

hashcode_gen.rb

#!/usr/bin/env ruby

module EmurateJavaStringHashCode
  def to_hashcode
    max = 2 ** 31 - 1 # Javaのint最大値
    min = -2 ** 31 # Javaのint最小値
    h = 0
    n = self.size
    n.times do |i|
      h = 31 * h + self[i]
      while h <min || max <h
        h = max - ( min - h  ) + 1 if h <min
        h = min - ( max - h  ) - 1 if max <h
      end
    end
    h
  end
end

class String
  include EmurateJavaStringHashCode
end

key = ARGV.first
puts key.to_hashcode


確認用のjava HashCodeGenerator.java

public class HashCodeGenerater {
    public static void main(String argv[]) {
        System.out.println( argv[0].hashCode() );
    }
}


テストスクリプト test/test_hashcode_gen.rb

require 'test/unit'

$:.unshift "#{File.dirname(__FILE__)}/../"
$:.unshift File.dirname(__FILE__)

class HashCodeGenTest <Test::Unit::TestCase

  def test_random
    10.times do
      str = [Array.new(rand(20)){rand(256).chr}.join].pack("m").chomp
      j = `java HashCodeGenerater '#{str}'`
      r = `ruby hashcode_gen.rb '#{str}'`
      assert_equal(j,r)
    end
  end
 
end


テスト結果

Loaded suite test/hashcodegen_test
Started
.
Finished in 1.478273 seconds.

1 tests, 10 assertions, 0 failures, 0 errors


ちゃんと通りました。

--

ついでにCでも書いてみた。

#include <stdio.h>
#include <string.h>

int strhashcode( char *word );

int main( int argc, char** argv)
{
  printf("hashcode = %d\n", strhashcode(argv[1]) );
  return 0;
}

int strhashcode( char *word){
  int len,i,h = 0;
  len = strlen(word);
  for (i=0; i<len; i++){
    h = 31 * h + word[i];
  }
  return h;
}


Trackback URI | Comments RSS

Leave a Reply