From: "Aleksi Niemelä" <aleksi.niemela@...>
Date: 2000-08-11T11:57:58+02:00
Subject: [ruby-talk:04418] Array#hash ruby rewrite

I guess Array#hash does not work very well. Here's an example and Ruby
version of simple fix. I'm sure we can tweak it to even better. I just
wanted to raise this issue, tried not very hard to solve it.

This is probably completely unrelated to the hash[key]=value unlinearity
problem, which seems to be about GC. Anyway, it reminded me.

  class Array
    def shuffle
      for i in 0...size
        r=rand(size())
        self[i],self[r]=self[r],self[i]
      end
      self
    end
  end

  def puts_hash_comparison(ary1, ary2)
    puts("#{ary1.inspect}.hash == #{ary2.inspect}.hash",
         sprintf("%#{ary1.inspect.length+5}d == %d -> %s", 
                 ary1.hash, ary2.hash, ary1.hash==ary2.hash))
  end

  def test_array_hash
    puts_hash_comparison(%w(a b), %w(b a))
    puts_hash_comparison(%w(d e), %w(e d))
    puts_hash_comparison(%w(d f), %w(f d))
    puts_hash_comparison(%w(ab bc), %w(bc ab))
  
    ary=%w(a b c de )
    10.times do 
      puts_hash_comparison( ary, ary.dup.shuffle)
    end
  end

  puts "\nAll or most of these should say false!"
  test_array_hash

  class Array
    def hash
      key = 0
      for elem in self[0,self.size]
        key = (key * 65599 + elem.hash) % (2 ** 31)
      end
      key
    end
  end

  puts "\nAll or most of these say false!"
  puts "The hash function is stolen from String#hash, and I'm sure it"
  puts "could be tweaked or even replaced with better one."
  test_array_hash

#################

And the output:

#################

All or most of these should say false!
["a", "b"].hash == ["b", "a"].hash
              1 == 1 -> true
["d", "e"].hash == ["e", "d"].hash
              3 == 3 -> true
["d", "f"].hash == ["f", "d"].hash
              0 == 0 -> true
["ab", "bc"].hash == ["bc", "ab"].hash
           196802 == 196802 -> true
["a", "b", "c", "de"].hash == ["c", "a", "de", "b"].hash
                   6560101 == 6560101 -> true
["a", "b", "c", "de"].hash == ["a", "c", "de", "b"].hash
                   6560101 == 6560101 -> true
["a", "b", "c", "de"].hash == ["b", "c", "a", "de"].hash
                   6560101 == 6560101 -> true
["a", "b", "c", "de"].hash == ["a", "de", "b", "c"].hash
                   6560101 == 6560101 -> true
["a", "b", "c", "de"].hash == ["b", "de", "a", "c"].hash
                   6560101 == 6560101 -> true
["a", "b", "c", "de"].hash == ["b", "de", "a", "c"].hash
                   6560101 == 6560101 -> true
["a", "b", "c", "de"].hash == ["a", "b", "c", "de"].hash
                   6560101 == 6560101 -> true
["a", "b", "c", "de"].hash == ["b", "de", "c", "a"].hash
                   6560101 == 6560101 -> true
["a", "b", "c", "de"].hash == ["c", "a", "de", "b"].hash
                   6560101 == 6560101 -> true
["a", "b", "c", "de"].hash == ["b", "a", "c", "de"].hash
                   6560101 == 6560101 -> true

All or most of these say false!
The hash function is stolen from String#hash, and I'm sure it
could be tweaked or even replaced with better one.
["a", "b"].hash == ["b", "a"].hash
        6363201 == 6428799 -> false
["d", "e"].hash == ["e", "d"].hash
        6560001 == 6625599 -> false
["d", "f"].hash == ["f", "d"].hash
        6560002 == 6691198 -> false
["ab", "bc"].hash == ["bc", "ab"].hash
        814223488 == 822484992 -> false
["a", "b", "c", "de"].hash == ["b", "de", "c", "a"].hash
                1377712415 == 778349149 -> false
["a", "b", "c", "de"].hash == ["b", "c", "de", "a"].hash
                1377712415 == 838799265 -> false
["a", "b", "c", "de"].hash == ["b", "a", "de", "c"].hash
                1377712415 == 822276257 -> false
["a", "b", "c", "de"].hash == ["c", "a", "b", "de"].hash
                1377712415 == 783076061 -> false
["a", "b", "c", "de"].hash == ["b", "c", "de", "a"].hash
                1377712415 == 838799265 -> false
["a", "b", "c", "de"].hash == ["b", "a", "c", "de"].hash
                1377712415 == 2554461 -> false
["a", "b", "c", "de"].hash == ["de", "c", "a", "b"].hash
                1377712415 == 346459875 -> false
["a", "b", "c", "de"].hash == ["a", "c", "b", "de"].hash
                1377712415 == 1385908321 -> false
["a", "b", "c", "de"].hash == ["b", "de", "a", "c"].hash
                1377712415 == 778217953 -> false
["a", "b", "c", "de"].hash == ["a", "b", "de", "c"].hash
                1377712415 == 49950563 -> false