Random key from Ruby Hash (faster) (See related posts)

I needed a Ruby Hash class that could extract a random key from the keys that have not been extracted before. Plus that the class should be re-entrant...

I found baby's class, but it was not working (at least not in Ruby 1.8.x). I made it work (slight changes), and I added the keys_not_used to make it work faster (baby's random would cycle almost forever on large lists). But I would say all credit should go to the original author, who did all the hard work.

Without further ado, here is the new version:

class RandomHash < Hash 

   @keys_used = nil 
  
   def random_key 
      if @keys_used == nil then
         @keys_used = Hash.new 
      else
         @keys_used = Hash.new if @keys_used.size == self.size
      end
      
      if (@keys_used.size == 0) then
         pos = rand(self.size)
         key = self.keys[pos]
      else
         @keys_not_used = Hash.new
     	 self.keys.each{ |key|
         	if (! @keys_used.include?(key)) then
            	    @keys_not_used[key] = 1
         	end
	     }
	     pos = rand(@keys_not_used.size)
	     key = @keys_not_used.keys[pos]
	  end
	  
      @keys_used[key] = 1
      return key 
   end 
end 

# Test code
$sources = Hash.new
$RandomSources = RandomHash.new

begin

   (1..10).each{ |val|
      $sources["#{val}"] = 1
   }
   
   $sources.each { |src|
      puts "Src=#{src}"
      $RandomSources[src] = 1
   }

   RandomKeys = Hash.new
   (0..$sources.length).each{ |index| # one more than all values
      key = $RandomSources.random_key
      print "Extracted #{key} ... It's a"
      if (!RandomKeys.has_key?(key)) then
         puts " NEW key!"
         RandomKeys[key] = 1
      else
         puts "n OLD key!"
      end
   }
end