Reduce memory usage of Hash object

## Implementation Summary

* Change entry list from segmented list to flat array.
* Change value of hash bucket from pointer to entry to index of entry list,
  and represent it by variable length bits according to capacity of hash
  buckets.
* Store management information about entry list and hash table to `struct
  RHash` as much as possible.

## Benchmark Summary

Only the results of typical situations on 64-bit Word-boxing are present
here. For more detailed information, including consideration, see below
(although most of the body is written in Japanese).

* https://shuujii.github.io/mruby-hash-benchmark

### Memory Usage

Lower value is better.

| Hash Size |   Baseline    |      New      |   Factor   |
|----------:|--------------:|--------------:|-----------:|
|        16 |          344B |          256B |   0.74419x |
|        40 |        1,464B |          840B |   0.57377x |
|       200 |        8,056B |        3,784B |   0.46971x |
|       500 |       17,169B |        9,944B |   0.57949x |

### Performance

Higher value is better.

#### `mrb_hash_set`

| Hash Size |   Baseline    |      New      |   Factor   |
|----------:|--------------:|--------------:|-----------:|
|        16 |  1.41847M i/s |  1.36004M i/s |   0.95881x |
|        40 |  0.39224M i/s |  0.31888M i/s |   0.81296x |
|       200 |  0.03780M i/s |  0.04290M i/s |   1.13494x |
|       500 |  0.01225M i/s |  0.01314M i/s |   1.07275x |

#### `mrb_hash_get`

| Hash Size |   Baseline    |      New      |   Factor   |
|----------:|--------------:|--------------:|-----------:|
|        16 | 26.05920M i/s | 30.19543M i/s |   1.15872x |
|        40 | 44.26420M i/s | 32.75781M i/s |   0.74005x |
|       200 | 44.55171M i/s | 31.56926M i/s |   0.70860x |
|       500 | 39.19250M i/s | 29.73806M i/s |   0.75877x |

#### `mrb_hash_each`

| Hash Size |   Baseline    |      New      |   Factor   |
|----------:|--------------:|--------------:|-----------:|
|        16 | 25.11964M i/s | 30.34167M i/s |   1.20789x |
|        40 | 11.74253M i/s | 13.25539M i/s |   1.12884x |
|       200 |  2.01133M i/s |  2.97214M i/s |   1.47770x |
|       500 |  0.87411M i/s |  1.21178M i/s |   1.38631x |

#### `Hash#[]=`

| Hash Size |   Baseline    |      New      |   Factor   |
|----------:|--------------:|--------------:|-----------:|
|        16 |  0.50095M i/s |  0.56490M i/s |   1.12764x |
|        40 |  0.19132M i/s |  0.18392M i/s |   0.96129x |
|       200 |  0.03624M i/s |  0.03256M i/s |   0.89860x |
|       500 |  0.01527M i/s |  0.01236M i/s |   0.80935x |
#### `Hash#[]`

| Hash Size |   Baseline    |      New      |   Factor   |
|----------:|--------------:|--------------:|-----------:|
|        16 | 11.53211M i/s | 12.78806M i/s |   1.10891x |
|        40 | 15.26920M i/s | 13.37529M i/s |   0.87596x |
|       200 | 15.28550M i/s | 13.36410M i/s |   0.87430x |
|       500 | 14.57695M i/s | 12.75388M i/s |   0.87494x |

#### `Hash#each`

| Hash Size |   Baseline    |      New      |   Factor   |
|----------:|--------------:|--------------:|-----------:|
|        16 |  0.30462M i/s |  0.27080M i/s |   0.88898x |
|        40 |  0.12912M i/s |  0.11704M i/s |   0.90642x |
|       200 |  0.02638M i/s |  0.02402M i/s |   0.91071x |
|       500 |  0.01066M i/s |  0.00959M i/s |   0.89953x |

#### `Hash#delete`

| Hash Size |   Baseline    |      New      |   Factor   |
|----------:|--------------:|--------------:|-----------:|
|        16 |  7.84167M i/s |  6.96419M i/s |   0.88810x |
|        40 |  6.91292M i/s |  7.41427M i/s |   1.07252x |
|       200 |  3.75952M i/s |  7.32080M i/s |   1.94727x |
|       500 |  2.10754M i/s |  7.05963M i/s |   3.34970x |

#### `Hash#shift`

| Hash Size |   Baseline    |      New      |   Factor   |
|----------:|--------------:|--------------:|-----------:|
|        16 | 14.66444M i/s | 13.18876M i/s |   0.89937x |
|        40 | 11.95124M i/s | 11.10420M i/s |   0.92913x |
|       200 |  5.53681M i/s |  7.88155M i/s |   1.42348x |
|       500 |  2.96728M i/s |  5.40405M i/s |   1.82121x |

#### `Hash#dup`

| Hash Size |   Baseline    |      New      |   Factor   |
|----------:|--------------:|--------------:|-----------:|
|        16 |  0.15063M i/s |  5.37889M i/s |  35.71024x |
|        40 |  0.06515M i/s |  3.38196M i/s |  51.91279x |
|       200 |  0.01359M i/s |  1.46538M i/s | 107.84056x |
|       500 |  0.00559M i/s |  0.75411M i/s | 134.88057x |

### Binary Size

Lower value is better.

|    File    |   Baseline    |      New      |  Factor   |
|:-----------|--------------:|--------------:|----------:|
| mruby      |      730,408B |      734,176B |  1.00519x |
| libmruby.a |    1,068,134B |    1,072,846B |  1.00441x |

## Other Fixes

The following issues have also been fixed in the parts where there was some
change this time.

* [Heap use-after-free in `Hash#value?`](https://gist.github.com/shuujii/30e4fcd5844a4112a0ecd4a5b3483101#file-heap-use-after-free-in-hash-value-md)
* [Heap use-after-free in `ht_hash_equal`](https://gist.github.com/shuujii/30e4fcd5844a4112a0ecd4a5b3483101#file-heap-use-after-free-in-ht_hash_equal-md)
* [Heap use-after-free in `ht_hash_func`](https://gist.github.com/shuujii/30e4fcd5844a4112a0ecd4a5b3483101#file-heap-use-after-free-in-ht_hash_func-md)
* [Heap use-after-free in `mrb_hash_merge`](https://gist.github.com/shuujii/30e4fcd5844a4112a0ecd4a5b3483101#file-heap-use-after-free-in-mrb_hash_merge-md)
* [Self-replacement does not work for `Hash#replace`](https://gist.github.com/shuujii/30e4fcd5844a4112a0ecd4a5b3483101#file-self-replacement-does-not-work-for-hash-replace-md)
* [Repeated deletes and inserts increase memory usage of `Hash`](https://gist.github.com/shuujii/30e4fcd5844a4112a0ecd4a5b3483101#file-repeated-deletes-and-inserts-increase-memory-usage-of-hash-md)
* [`Hash#rehash` does not reindex completely](https://gist.github.com/shuujii/30e4fcd5844a4112a0ecd4a5b3483101#file-hash-rehash-does-not-reindex-completely-md)
* `mrb_hash_delete_key` does not cause an error for frozen object
* `mrb_hash_new_capa` does not allocate required space first
* [`mrb_os_memsize_of_hash_table` result is incorrect](https://github.com/mruby/mruby/pull/5032#discussion_r457994075)

1 files changed, 903 insertions, 281 deletions

diff --git a/test/t/hash.rb b/test/t/hash.rb
index cd47d251d..c51af03aa 100644
--- a/test/t/hash.rb
+++ b/test/t/hash.rb
@@ -1,378 +1,1000 @@
 ##
 # Hash ISO Test
 
-assert('Hash', '15.2.13') do
-  assert_equal Class, Hash.class
-end
+class HashKey
+  attr_accessor :value, :error, :callback
 
-assert('Hash#==', '15.2.13.4.1') do
-  assert_true({ 'abc' => 'abc' } == { 'abc' => 'abc' })
-  assert_false({ 'abc' => 'abc' } ==  { 'cba' => 'cba' })
-  assert_false({ :a => 1 } == true)
-  skip unless Object.const_defined?(:Float)
-  assert_true({ :equal => 1 } == { :equal => 1.0 })
-end
+  self.class.alias_method :[], :new
 
-assert('Hash#[]', '15.2.13.4.2') do
-  a = { 'abc' => 'abc' }
+  def initialize(value, error: nil, callback: nil)
+    @value = value
+    @error = error
+    @callback = callback
+  end
 
-  assert_equal 'abc', a['abc']
+  def ==(other)
+    @callback.(:==, self, other) if @callback
+    return raise_error(:==) if @error == true || @error == :==
+    other.kind_of?(self.class) && @value == other.value
+  end
 
-  # Hash#[] should call #default (#3272)
-  hash = {}
-  def hash.default(k); self[k] = 1; end
-  hash[:foo] += 1
+  def eql?(other)
+    @callback.(:eql?, self, other) if @callback
+    return raise_error(:eql?) if @error == true || @error == :eql?
+    other.kind_of?(self.class) && @value.eql?(other.value)
+  end
 
-  assert_equal 2, hash[:foo]
-end
+  def hash
+    @callback.(:hash, self) if @callback
+    return raise_error(:hash) if @error == true || @error == :hash
+    @value % 3
+  end
 
-assert('Hash#[]=', '15.2.13.4.3') do
-  a = Hash.new
-  a['abc'] = 'abc'
+  def to_s
+    "#{self.class}[#{@value}]"
+  end
+  alias inspect to_s
 
-  assert_equal 'abc', a['abc']
+  def raise_error(name)
+    raise "##{self}: #{name} error"
+  end
 end
 
-assert('Hash#clear', '15.2.13.4.4') do
-  a = { 'abc' => 'abc' }
-  a.clear
-
-  assert_equal({ }, a)
+class HashEntries < Array
+  self.class.alias_method :[], :new
+
+  def initialize(entries) self.replace(entries) end
+  def key(index, k=get=true) get ? self[index][0] : (self[index][0] = k) end
+  def value(index, v=get=true) get ? self[index][1] : (self[index][1] = v) end
+  def keys; map{|k, v| k} end
+  def values; map{|k, v| v} end
+  def each_key(&block) each{|k, v| block.(k)} end
+  def each_value(&block) each{|k, v| block.(v)} end
+  def dup2; self.class[*map{|k, v| [k.dup, v.dup]}] end
+  def to_s; "#{self.class}#{super}" end
+  alias inspect to_s
+
+  def hash_for(hash={}, &block)
+    each{|k, v| hash[k] = v}
+    block.(hash) if block
+    hash
+  end
 end
 
-assert('Hash#dup') do
-  a = { 'a' => 1 }
-  b = a.dup
-  a['a'] = 2
-  assert_equal({'a' => 1}, b)
-
-  c = Hash.new { |h, k| h[k] = k.upcase }
-  d = c.dup
-  assert_equal("FOO", d["foo"])
+def ar_entries
+  HashEntries[
+    [1, "one"],
+    [HashKey[2], :two],
+    [nil, :two],
+    [:one, 1],
+    ["&", "&amp;"],
+    [HashKey[6], :six],
+    [HashKey[5], :five],  # same hash code as HashKey[2]
+  ]
+end
+
+def ht_entries
+  ar_entries.dup.push(
+    ["id", 32],
+    [:date, "2020-05-02"],
+    [200, "OK"],
+    ["modifiers", ["left_shift", "control"]],
+    [:banana, :yellow],
+    ["JSON", "JavaScript Object Notation"],
+    [:size, :large],
+    ["key_code", "h"],
+    ["h", 0x04],
+    [[3, 2, 1], "three, two, one"],
+    [:auto, true],
+    [HashKey[12], "December"],
+    [:path, "/path/to/file"],
+    [:name, "Ruby"],
+  )
+end
+
+def merge_entries!(entries1, entries2)
+  entries2.each do |k2, v2|
+    entry1 = entries1.find{|k1, _| k1.eql?(k2)}
+    entry1 ? (entry1[1] = v2) : (entries1 << [k2, v2])
+  end
+  entries1
+end
+
+def product(*arrays, &block)
+  sizes = Array.new(arrays.size+1, 1)
+  (arrays.size-1).downto(0){|i| sizes[i] = arrays[i].size * sizes[i+1]}
+  size = sizes[0]
+  results = Array.new(size){[]}
+  arrays.each_with_index do |array, arrays_i|
+    results_i = -1
+    (size / sizes[arrays_i]).times do
+      array.each do |v|
+        sizes[arrays_i+1].times{results[results_i+=1] << v}
+      end
+    end
+  end
+  results.each{block.(_1)}
 end
 
-assert('Hash#default', '15.2.13.4.5') do
-  a = Hash.new
-  b = Hash.new('abc')
-  c = Hash.new {|s,k| s[k] = k}
-
-  assert_nil a.default
-  assert_equal 'abc', b.default
-  assert_nil c.default
-  assert_equal 'abc', c.default('abc')
+def assert_iterator(exp, obj, meth)
+  params = []
+  obj.__send__(meth) {|param| params << param}
+  assert_equal(exp, params)
 end
 
-assert('Hash#default=', '15.2.13.4.6') do
-  a = { 'abc' => 'abc' }
-  a.default = 'cba'
-
-  assert_equal 'abc', a['abc']
-  assert_equal 'cba', a['notexist']
+def assert_nothing_crashed(&block)
+  block.call rescue nil
+  pass
 end
 
-assert('Hash#default_proc', '15.2.13.4.7') do
-  a = Hash.new
-  b = Hash.new {|s,k| s[k] = k + k}
-  c = b[2]
-  d = b['cat']
-
-  assert_nil a.default_proc
-  assert_equal Proc, b.default_proc.class
-  assert_equal 4, c
-  assert_equal 'catcat', d
+assert('Hash', '15.2.13') do
+  assert_equal(Class, Hash.class)
+end
+
+[[:==, '15.2.13.4.1'], [:eql?, '']].each do |meth, iso|
+  assert("Hash##{meth}", iso) do
+    cls = Class.new(Hash){attr_accessor :foo}
+    [ar_entries, ht_entries].each do |entries|
+      h1 = entries.hash_for
+      h2 = entries.dup.reverse!.hash_for
+      assert_operator(h1, meth, h2)
+      assert_operator(h1, meth, h1)
+      assert_not_operator(h1, meth, true)
+      assert_operator({}, meth, Hash.new)
+
+      h1 = entries.hash_for(cls.new(1)) {|h| h.foo = 1}
+      h2 = entries.hash_for(cls.new(2)) {|h| h.foo = 2}
+      assert_operator(h1, meth, h2)
+
+      h1 = entries.hash_for
+      h2 = entries.hash_for(cls.new)
+      assert_operator(h1, meth, h2)
+
+      h1 = (entries.dup << [:_k, 1]).hash_for
+      h2 = (entries.dup << [:_k, 2]).hash_for
+      assert_not_operator(h1, meth, h2)
+
+      h1 = (entries.dup << [:_k1, 0]).hash_for
+      h2 = (entries.dup << [:_k2, 0]).hash_for
+      assert_not_operator(h1, meth, h2)
+
+      h1 = entries.hash_for
+      h2 = (entries.dup << [:_k, 2]).hash_for
+      assert_not_operator(h1, meth, h2)
+
+      k1, v1 = HashKey[-1], HashKey[-2]
+      k2, v2 = HashKey[-1], HashKey[-2]
+      h1 = (entries.dup << [k1, v1]).hash_for
+      h2 = (entries.dup << [k2, v2]).hash_for
+      product([h1, h2], [k1, k2], %i[eql? hash]) do |h, k, m|
+        [k1, k2].each{_1.callback = nil}
+        k.callback = ->(name, *){h.clear if name == m}
+        assert_nothing_crashed{h1.__send__(meth, h2)}
+      end
+      product([h1, h2], [v1, v2]) do |h, v|
+        [v1, v2].each{_1.callback = nil}
+        v.callback = ->(name, *){h.clear if name == meth}
+        assert_nothing_crashed{h1.__send__(meth, h2)}
+      end
+
+      if Object.const_defined?(:Float)
+        h1 = (entries.dup << [-1, true]).hash_for
+        h2 = (entries.dup << [-1.0, true]).hash_for
+        assert_not_operator(h1, meth, h2)
+        h1 = (entries.dup << [-1.0, true]).hash_for
+        h2 = (entries.dup << [-1, true]).hash_for
+        assert_not_operator(h1, meth, h2)
+
+        h1 = (entries.dup << [:_k, 1]).hash_for
+        h2 = (entries.dup << [:_k, 1.0]).hash_for
+        if meth == :==
+          assert_operator(h1, meth, h2)
+        else
+          assert_not_operator(h1, meth, h2)
+        end
+      end
+    end
+  end
 end
 
-assert('Hash#delete', '15.2.13.4.8') do
-  a = { 'abc' => 'ABC' }
-  b = { 'abc' => 'ABC' }
-  b_tmp_1 = false
-  b_tmp_2 = false
-
-  assert_equal 'ABC', a.delete('abc')
-  b.delete('abc') do |k|
-    b_tmp_1 = true
-  end
-  b.delete('abc') do |k|
-    b_tmp_2 = true
+assert('Hash#[]', '15.2.13.4.2') do
+  [ar_entries, ht_entries].each do |entries|
+    h = entries.hash_for
+    assert_equal(entries.size, h.size)
+    entries.each{|k, v| assert_equal(v, h[k])}
+    assert_equal(nil, h["_not_found_"])
+    assert_equal(nil, h[:_not_dound_])
+    assert_equal(nil, h[-2])
+
+    k = HashKey[-4]
+    h[HashKey[-1]] = -1
+    h[k] = -4
+    h.delete(k)
+    assert_equal(nil, h[k])
+
+    if Object.const_defined?(:Float)
+      h[-2] = 22
+      assert_equal(nil, h[-2.0])
+      h[-3.0] = 33
+      assert_equal(nil, h[-3])
+      assert_equal(33, h[-3.0])
+    end
+
+    k = HashKey[-2]
+    k.callback = ->(name, *){h.clear if name == :eql?}
+    assert_nothing_crashed{h[k]}
+    k.callback = ->(name, *){h.clear if name == :hash}
+    assert_nothing_crashed{h[k]}
   end
 
-  assert_nil a.delete('cba')
-  assert_false a.has_key?('abc')
-  assert_false b_tmp_1
-  assert_true b_tmp_2
+  # Hash#[] should call #default (#3272)
+  h = {}
+  def h.default(k); self[k] = 1; end
+  h[:foo] += 1
+  assert_equal(2, h[:foo])
+end
+
+[%w[[]= 3], %w[store 26]].each do |meth, no|
+  assert("Hash##{meth}", "15.2.13.4.#{no}") do
+    [{}, ht_entries.hash_for].each do |h|
+      # duplicated key
+      k = :_dup_key
+      h.__send__(meth, k, 1)
+      size = h.size
+      h.__send__(meth, k, 2)
+      assert_equal(size, h.size)
+      assert_equal(2, h[k])
+
+      # freeze string key
+      k = "_mutable"
+      h.__send__(meth, k, 1)
+      h_k = h.keys[-1]
+      assert_not_same(k, h_k)
+      assert_predicate(h_k, :frozen?)
+      assert_not_predicate(k, :frozen?)
+
+      # frozen string key
+      k = "_immutable".freeze
+      h.__send__(meth, k, 2)
+      h_k = h.keys[-1]
+      assert_same(k, h_k)
+      assert_predicate(h_k, :frozen?)
+
+      # numeric key
+      if Object.const_defined?(:Float)
+        h.__send__(meth, 3, :fixnum)
+        h.__send__(meth, 3.0, :float)
+        assert_equal(:fixnum, h[3])
+        assert_equal(:float, h[3.0])
+        h.__send__(meth, 4.0, :float)
+        h.__send__(meth, 4, :fixnum)
+        assert_equal(:fixnum, h[4])
+        assert_equal(:float, h[4.0])
+      end
+
+      # other key
+      k = [:_array]
+      h.__send__(meth, k, :_array)
+      h_k = h.keys[-1]
+      assert_same(k, h_k)
+      assert_not_predicate(h_k, :frozen?)
+      assert_not_predicate(k, :frozen?)
+
+      # deleted key
+      k1, k2, k3 = HashKey[-1], HashKey[-4], HashKey[-7]  # same hash code
+      h.__send__(meth, k1, 1)
+      h.__send__(meth, k2, -4)
+      h.__send__(meth, k3, 73)
+      size = h.size
+      h.delete(k1)
+      h.delete(k2)
+      h.__send__(meth, k2, 40)
+      assert_equal(nil, h[k1])
+      assert_equal(40, h[k2])
+      assert_equal(73, h[k3])
+      assert_equal(size - 1, h.size)
+
+      # frozen
+      h.freeze
+      assert_raise(FrozenError){h.__send__(meth, -100, 1)}
+    end
+
+    [ar_entries.hash_for, ht_entries.hash_for].each do |h|
+      k = HashKey[-2]
+      k.callback = ->(name, *){h.clear if name == :eql?}
+      assert_nothing_crashed{h.__send__(meth, k, 2)}
+      k.callback = ->(name, *){h.clear if name == :hash}
+      assert_nothing_crashed{h.__send__(meth, k, 2)}
+    end
+  end
 end
 
-assert('Hash#each', '15.2.13.4.9') do
-  a = { 'abc_key' => 'abc_value' }
-  key = nil
-  value = nil
-
-  a.each  do |k,v|
-    key = k
-    value = v
+assert('Hash#clear', '15.2.13.4.4') do
+  [ar_entries, ht_entries].each do |entries|
+    h = entries.hash_for
+    assert_same(h, h.clear)
+    assert_equal(0, h.size)
+    assert_nil(h[entries.key(3)])
+
+    h.freeze
+    assert_raise(FrozenError){h.clear}
   end
 
-  assert_equal 'abc_key', key
-  assert_equal 'abc_value', value
+  h = {}.freeze
+  assert_raise(FrozenError){h.clear}
 end
 
-assert('Hash#each_key', '15.2.13.4.10') do
-  a = { 'abc_key' => 'abc_value' }
-  key = nil
-
-  a.each_key  do |k|
-    key = k
+assert('Hash#dup') do
+  cls = Class.new(Hash){attr_accessor :foo}
+  [ar_entries, ht_entries].each do |entries|
+    h1 = entries.hash_for(cls.new(61)){|h| h.foo = 23}.freeze
+    h2 = h1.dup
+    assert_not_predicate(h2, :frozen?)
+    assert_equal(h1.class, h2.class)
+    assert_equal(entries, h2.to_a)
+    assert_equal(23, h2.foo)
+    assert_equal(61, h2["_not_found_"])
+    h2[-10] = 10
+    assert_equal(10, h2[-10])
+    assert_not_operator(h1, :key?, -10)
+
+    h = entries.hash_for
+    k = HashKey[-1]
+    h[k] = 1
+    k.callback = ->(*){h.clear}
+    assert_nothing_crashed{h.dup}
   end
-
-  assert_equal 'abc_key', key
 end
 
-assert('Hash#each_value', '15.2.13.4.11') do
-  a = { 'abc_key' => 'abc_value' }
-  value = nil
-
-  a.each_value  do |v|
-    value = v
+assert('Hash#default', '15.2.13.4.5') do
+  [ar_entries, ht_entries].each do |entries|
+    h = entries.hash_for(Hash.new)
+    assert_equal(nil, h.default)
+    assert_equal(nil, h.default(-2))
+
+    h = entries.hash_for(Hash.new(-88))
+    assert_equal(-88, h.default)
+    assert_equal(-88, h.default(-2))
+    assert_not_operator(h, :key?, -2)
+    assert_raise(ArgumentError){h.default(-2,-2)}
+
+    proc = ->(h, k){h[k] = k * 3}
+    h = entries.hash_for(Hash.new(proc))
+    assert_equal(proc, h.default(-2))
+
+    h = entries.hash_for(Hash.new(&proc))
+    assert_equal(nil, h.default)
+    assert_not_operator(h, :key?, -2)
+    assert_equal(-6, h.default(-2))
+    assert_equal(-6, h[-2])
+    h[-2] = -5
+    assert_equal(-6, h.default(-2))
+    assert_equal(-6, h[-2])
   end
-
-  assert_equal 'abc_value', value
 end
 
-assert('Hash#empty?', '15.2.13.4.12') do
-  a = { 'abc_key' => 'abc_value' }
-  b = Hash.new
-
-  assert_false a.empty?
-  assert_true b.empty?
-end
+assert('Hash#default=', '15.2.13.4.6') do
+  [ar_entries, ht_entries].each do |entries|
+    h = entries.hash_for(Hash.new)
+    h.default = 3
+    assert_equal(3, h[-2])
+    assert_equal(entries.value(0), h[entries.key(0)])
 
-assert('Hash#has_key?', '15.2.13.4.13') do
-  a = { 'abc_key' => 'abc_value' }
-  b = Hash.new
+    h.default = 4
+    assert_equal(4, h[-2])
 
-  assert_true a.has_key?('abc_key')
-  assert_false b.has_key?('cba')
-end
+    h.default = nil
+    assert_equal(nil, h[-2])
 
-assert('Hash#has_value?', '15.2.13.4.14') do
-  a = { 'abc_key' => 'abc_value' }
-  b = Hash.new
+    h.default = [5]
+    assert_same(h[-2], h[-3])
 
-  assert_true a.has_value?('abc_value')
-  assert_false b.has_value?('cba')
+    h.freeze
+    assert_raise(FrozenError){h.default = 3}
+  end
 end
 
-assert('Hash#include?', '15.2.13.4.15') do
-  a = { 'abc_key' => 'abc_value' }
-  b = Hash.new
-
-  assert_true a.include?('abc_key')
-  assert_false b.include?('cba')
+assert('Hash#default_proc', '15.2.13.4.7') do
+  [ar_entries, ht_entries].each do |entries|
+    h = entries.hash_for({})
+    assert_nil(h.default_proc)
+
+    h = entries.hash_for(Hash.new(34))
+    assert_nil(h.default_proc)
+
+    h = entries.hash_for(Hash.new{|h, k| h[k] = k * 3})
+    proc = h.default_proc
+    assert_equal(Proc, proc.class)
+    assert_equal(6, proc.(h, 2))
+    assert_equal([2, 6], h.to_a[-1])
+  end
 end
 
-assert('Hash#initialize', '15.2.13.4.16') do
-  # Testing initialize by new.
-  h = Hash.new
-  h2 = Hash.new(:not_found)
-
-  assert_true h.is_a? Hash
-  assert_equal({ }, h)
-  assert_nil h["hello"]
-  assert_equal :not_found, h2["hello"]
-end
+assert('Hash#delete', '15.2.13.4.8') do
+  [ar_entries, ht_entries].each do |entries|
+    h = entries.hash_for
+    pairs = entries.dup
+    [0, 2, -1].each do |i|
+      k, v = pairs.delete_at(i)
+      assert_equal(v, h.delete(k))
+      assert_equal(nil, h[k])
+      assert_equal(false, h.key?(k))
+    end
+    [entries.key(0), "_not_found_"].each {|k|assert_equal(nil, h.delete(k))}
+    assert_equal(pairs.size, h.size)
+    assert_equal(pairs, h.to_a)
+    pairs.each {|k, v| assert_equal(v, h[k])}
+
+    h = entries.hash_for
+    pairs = entries.dup
+    [pairs.delete_at(1), ["_not_found_", "_default"]].each do |k, v|
+      assert_equal(v, h.delete(k){"_default"})
+      assert_equal(nil, h[k])
+      assert_equal(false, h.key?(k))
+    end
+    assert_equal(pairs.size, h.size)
+    assert_equal(pairs, h.to_a)
+    pairs.each {|k, v| assert_equal(v, h[k])}
+
+    if Object.const_defined?(:Float)
+      h = entries.dup.push([-5, 1], [-5.0, 2], [-6.0, 3], [-6, 4]).hash_for
+      assert_equal(1, h.delete(-5))
+      assert_equal(3, h.delete(-6.0))
+    end
+
+    # nil value with block
+    h = entries.hash_for
+    k = "_nil"
+    h[k] = nil
+    assert_equal(nil, h.delete(k){"blk"})
+    assert_equal(false, h.key?(k))
+
+    k = HashKey[-31, callback: ->(*){h.clear}]
+    assert_nothing_crashed{h.delete(k)}
+  end
 
-assert('Hash#initialize_copy', '15.2.13.4.17') do
-  a = { 'abc_key' => 'abc_value' }
-  b = Hash.new.initialize_copy(a)
+  assert_raise(ArgumentError){{}.delete}
+  assert_raise(ArgumentError){{}.delete(1,2)}
 
-  assert_equal({ 'abc_key' => 'abc_value' }, b)
+  h = {}.freeze
+  assert_raise(FrozenError){h.delete(1)}
+end
+
+[%w[each 9], %w[each_key 10], %w[each_value 11]].each do |meth, no|
+  assert("Hash##{meth}", "15.2.13.4.#{no}") do
+    [ar_entries, ht_entries].each do |entries|
+      exp = []
+      entries.__send__(meth){|param| exp << param}
+      assert_iterator(exp, entries.hash_for, meth)
+
+      h = entries.hash_for
+      entries.shift
+      h.shift
+      entry = entries.delete_at(1)
+      h.delete(entry[0])
+      h.delete(entries.delete_at(-4)[0])
+      entries << entry
+      h.store(*entry)
+      exp = []
+      entries.__send__(meth){|param| exp << param}
+      assert_iterator(exp, h, meth)
+    end
+
+    assert_iterator([], {}, meth)
+  end
 end
 
-assert('Hash#key?', '15.2.13.4.18') do
-  a = { 'abc_key' => 'abc_value' }
-  b = Hash.new
+assert('Hash#empty?', '15.2.13.4.12') do
+  [ar_entries, ht_entries].each do |entries|
+    assert_not_predicate entries.hash_for, :empty?
 
-  assert_true a.key?('abc_key')
-  assert_false b.key?('cba')
-end
+    h = entries.hash_for
+    h.shift
+    h.delete(entries.key(-1))
+    assert_not_predicate h, :empty?
 
-assert('Hash#keys', '15.2.13.4.19') do
-  a = { 'abc_key' => 'abc_value' }
+    h = entries.hash_for
+    entries.size.times{h.shift}
+    assert_predicate(h, :empty?)
 
-  assert_equal ['abc_key'], a.keys
-end
-
-assert('Hash#length', '15.2.13.4.20') do
-  a = { 'abc_key' => 'abc_value' }
-  b = Hash.new
+    h = entries.hash_for
+    entries.each {|k, v| h.delete(k)}
+    assert_predicate(h, :empty?)
+  end
 
-  assert_equal 1, a.length
-  assert_equal 0, b.length
+  assert_predicate(Hash.new, :empty?)
+  assert_predicate(Hash.new(1), :empty?)
+  assert_predicate(Hash.new{|h, k| h[k] = 2}, :empty?)
 end
 
-assert('Hash#member?', '15.2.13.4.21') do
-  a = { 'abc_key' => 'abc_value' }
-  b = Hash.new
-
-  assert_true a.member?('abc_key')
-  assert_false b.member?('cba')
-end
+[%w[has_key? 13], %w[include? 15], %w[key? 18], %w[member? 21]].each do |meth,no|
+  assert("Hash##{meth}", "15.2.13.4.#{no}") do
+    [ar_entries, ht_entries].each do |entries|
+      pairs = entries.dup.push([HashKey[-3], 3], [nil, "NIL"])
+      h = pairs.hash_for
+      pairs.each{|k, v| assert_operator(h, meth, k)}
+      assert_not_operator(h, meth, HashKey[-6])
+      assert_not_operator(h, meth, 3)
 
-assert('Hash#merge', '15.2.13.4.22') do
-  a = { 'abc_key' => 'abc_value', 'cba_key' => 'cba_value' }
-  b = { 'cba_key' => 'XXX',  'xyz_key' => 'xyz_value' }
+      if Object.const_defined?(:Float)
+        hh = entries.push([-7, :i], [-8.0, :f]).hash_for
+        assert_not_operator(hh, meth, -7.0)
+        assert_not_operator(hh, meth, -8)
+        assert_operator(hh, meth, -8.0)
+      end
 
-  result_1 = a.merge b
-  result_2 = a.merge(b) do |key, original, new|
-    original
-  end
+      h.shift
+      assert_not_operator(h, meth, pairs.key(0))
 
-  assert_equal({'abc_key' => 'abc_value', 'cba_key' => 'XXX',
-                'xyz_key' => 'xyz_value' }, result_1)
-  assert_equal({'abc_key' => 'abc_value', 'cba_key' => 'cba_value',
-                'xyz_key' => 'xyz_value' }, result_2)
+      h.delete(pairs.key(3))
+      assert_not_operator(h, meth, pairs.key(3))
 
-  assert_raise(TypeError) do
-    { 'abc_key' => 'abc_value' }.merge "a"
+      k = HashKey[-31, callback: ->(*){h.clear}]
+      assert_nothing_crashed{h.__send__(meth, k)}
+    end
   end
-end
 
-assert('Hash#replace', '15.2.13.4.23') do
-  a = { 'abc_key' => 'abc_value' }
-  b = Hash.new.replace(a)
+  h = Hash.new{|h, k| h[1] = 1}
+  assert_not_operator(h, meth, 1)
+end
 
-  assert_equal({ 'abc_key' => 'abc_value' }, b)
+[%w[has_value? 14], %w[value? 24]].each do |meth, no|
+  assert("Hash##{meth}", "15.2.13.4.#{no}") do
+    [ar_entries, ht_entries].each do |entries|
+      entries.push([HashKey[-5], -8], ["NIL", nil])
+      h = entries.hash_for
+      entries.each{|k, v| assert_operator(h, meth, v)}
+      assert_operator(h, meth, -8.0) if Object.const_defined?(:Float)
+      assert_not_operator(h, meth, "-8")
 
-  a = Hash.new(42)
-  b = {}
-  b.replace(a)
-  assert_equal(42, b[1])
+      h.shift
+      assert_not_operator(h, meth, entries.value(0))
 
-  a = Hash.new{|h,x| x}
-  b.replace(a)
-  assert_equal(127, b[127])
+      h.delete(entries.key(3))
+      assert_not_operator(h, meth, entries.value(3))
 
-   assert_raise(TypeError) do
-    { 'abc_key' => 'abc_value' }.replace "a"
+      v = HashKey[-31, callback: ->(*){h.clear}]
+      assert_nothing_crashed{h.__send__(meth, v)}
+    end
   end
-end
-
-assert('Hash#shift', '15.2.13.4.24') do
-  a = { 'abc_key' => 'abc_value', 'cba_key' => 'cba_value' }
-  b = a.shift
-
-  assert_equal Array, b.class
-  assert_equal 2, b.size
-  assert_equal 1, a.size
 
-  b = a.shift
-
-  assert_equal Array, b.class
-  assert_equal 2, b.size
-  assert_equal 0, a.size
+  h = Hash.new{|h, k| h[1] = 1}
+  assert_not_operator(h, meth, 1)
 end
 
-assert('Hash#size', '15.2.13.4.25') do
-  a = { 'abc_key' => 'abc_value' }
-  b = Hash.new
-
-  assert_equal 1, a.size
-  assert_equal 0, b.size
+assert('Hash#initialize', '15.2.13.4.16') do
+  h = Hash.new
+  assert_equal(Hash, h.class)
+  assert_not_operator(h, :key?, 1)
+  assert_equal(nil, h[1])
+
+  h = Hash.new([8])
+  assert_not_operator(h, :key?, 1)
+  assert_equal([8], h[1])
+  assert_same(h[1], h[2])
+
+  k = "key"
+  h = Hash.new{|hash, key| [hash, key]}
+  assert_not_operator(h, :key?, k)
+  assert_equal([h, k], h[k])
+  assert_same(h, h[k][0])
+  assert_same(k, h[k][1])
+
+  assert_raise(ArgumentError){Hash.new(1,2)}
+  assert_raise(ArgumentError){Hash.new(1){}}
+end
+
+[%w[keys 19], %w[values 28]].each do |meth, no|
+  assert("Hash##{meth}", "15.2.13.4.#{no}") do
+    [ar_entries, ht_entries].each do |entries|
+      h = entries.hash_for
+      assert_equal(entries.__send__(meth), h.__send__(meth))
+
+      h.shift
+      entries.shift
+      h.delete(entries.delete_at(3)[0])
+      assert_equal(entries.__send__(meth), h.__send__(meth))
+    end
+
+    assert_equal([], {}.__send__(meth))
+  end
 end
 
-assert('Hash#store', '15.2.13.4.26') do
-  a = Hash.new
-  a.store('abc', 'abc')
+[%w[length 20], %w[size 25]].each do |meth, no|
+  assert("Hash##{meth}", "15.2.13.4.#{no}") do
+    [ar_entries, ht_entries].each do |entries|
+      h = entries.hash_for
+      assert_equal(entries.size, h.__send__(meth))
+
+      h.shift
+      entries.shift
+      h.delete(entries.delete_at(3)[0])
+      assert_equal(entries.size, h.__send__(meth))
+    end
 
-  assert_equal 'abc', a['abc']
+    assert_equal(0, Hash.new.__send__(meth))
+  end
 end
 
-assert('Hash#value?', '15.2.13.4.27') do
-  a = { 'abc_key' => 'abc_value' }
-  b = Hash.new
+assert('Hash#merge', '15.2.13.4.22') do
+  cls = Class.new(Hash){attr_accessor :foo}
+  ar_pairs = HashEntries[
+    ["id", 32],
+    [nil, :two],
+    ["&", "&amp;"],
+    [:same_key, :AR],
+    [HashKey[2], 20],
+  ]
+  ht_pairs = HashEntries[
+    *(1..20).map{[_1, _1.to_s]},
+    [:same_key, :HT],
+    [:age, 32],
+    [HashKey[5], 500],
+  ]
+
+  [[ar_pairs, ht_pairs], [ht_pairs, ar_pairs]].each do |entries1, entries2|
+    h1 = entries1.hash_for(cls.new(:dv1)){|h| h.foo = :iv1}.freeze
+    h2 = entries2.hash_for(Hash.new(:dv2)).freeze
+    h3 = h1.merge(h2)
+    assert_equal(entries1, h1.to_a)
+    assert_equal(merge_entries!(entries1.dup2, entries2), h3.to_a)
+    assert_equal(cls, h3.class)
+    assert_equal(:dv1, h3.default)
+    assert_equal(:iv1, h3.foo)
+
+    h3 = {}.merge(entries2.hash_for(cls.new))
+    assert_equal(merge_entries!([], entries2), h3.to_a)
+    assert_equal(Hash, h3.class)
+
+    h3 = entries1.hash_for.merge({})
+    assert_equal(merge_entries!(entries1.dup2, []), h3.to_a)
+
+    h1 = entries1.hash_for
+    h2 = entries2.hash_for
+    h3 = h1.merge(h2){|k, v1, v2| [k, v1, v2]}
+    exp = merge_entries!(entries1.dup2, entries2)
+    exp.find{|k, _| k == :same_key}[1] = [
+      :same_key,
+      entries1.find{|k, _| k == :same_key}[1],
+      entries2.find{|k, _| k == :same_key}[1],
+    ]
+    assert_equal(exp, h3.to_a)
+
+    assert_raise(TypeError){entries1.hash_for.merge("str")}
+
+    k2 = HashKey[-2]
+    entries2 << [k2, 234]
+    h1, h2 = entries1.hash_for, entries2.hash_for
+    k2.callback = ->(name, *){h1.clear if name == :eql?}
+    assert_nothing_crashed{h1.merge(h2)}
+    h1, h2 = entries1.hash_for, entries2.hash_for
+    k2.callback = ->(name, *){h2.clear if name == :eql?}
+    assert_nothing_crashed{h1.merge(h2)}
+    h1, h2 = entries1.hash_for, entries2.hash_for
+    k2.callback = ->(name, *){h1.clear if name == :hash}
+    assert_nothing_crashed{h1.merge(h2)}
+    h1, h2 = entries1.hash_for, entries2.hash_for
+    k2.callback = ->(name, *){h2.clear if name == :hash}
+    assert_nothing_crashed{h1.merge(h2)}
+  end
+end
 
-  assert_true a.value?('abc_value')
-  assert_false b.value?('cba')
+assert("Hash#replace", "15.2.13.4.23") do
+  cls = Class.new(Hash){attr_accessor :foo}
+  e = [ar_entries, ht_entries]
+  [e, e.reverse].each do |entries1, entries2|
+    h1 = entries1.hash_for
+    assert_same(h1, h1.replace(h1))
+    assert_equal(entries1, h1.to_a)
+
+    h1 = {}
+    assert_same(h1, h1.replace(entries2.hash_for))
+    assert_equal(entries2, h1.to_a)
+
+    h1 = entries1.hash_for
+    assert_same(h1, h1.replace({}))
+    assert_predicate(h1, :empty?)
+
+    pairs2 = entries2.dup
+    h2 = pairs2.hash_for
+    pairs2.shift
+    h2.shift
+    h2.delete(pairs2.delete_at(2)[0])
+    h2.delete(pairs2.delete_at(4)[0])
+    h1 = entries1.hash_for
+    assert_same(h1, h1.replace(h2))
+    assert_equal(pairs2, h1.to_a)
+
+    h1 = entries1.hash_for(Hash.new(10))
+    h2 = entries2.hash_for(Hash.new(20))
+    assert_same(h1, h1.replace(h2))
+    assert_equal(entries2, h1.to_a)
+    assert_equal(20, h1.default)
+
+    h1 = entries1.hash_for(Hash.new{_2})
+    h2 = entries2.hash_for(Hash.new{_2.to_s})
+    assert_same(h1, h1.replace(h2))
+    assert_equal(entries2, h1.to_a)
+    assert_equal("-11", h1[-11])
+
+    h1 = entries1.hash_for(Hash.new(10))
+    h2 = entries2.hash_for(Hash.new{_2.to_s})
+    assert_same(h1, h1.replace(h2))
+    assert_equal(entries2, h1.to_a)
+    assert_equal("-11", h1[-11])
+
+    h1 = entries1.hash_for(Hash.new{_2})
+    h2 = entries2.hash_for(Hash.new(20))
+    assert_same(h1, h1.replace(h2))
+    assert_equal(entries2, h1.to_a)
+    assert_equal(20, h1[-1])
+
+    h1 = entries1.hash_for(cls.new(10)){|h| h.foo = 41}
+    h2 = entries2.hash_for(cls.new(20)){|h| h.foo = 42}.freeze
+    assert_same(h1, h1.replace(h2))
+    assert_equal(entries2, h1.to_a)
+    assert_equal(20, h1.default)
+    assert_equal(41, h1.foo)
+
+    h1 = entries1.hash_for
+    h2 = entries2.hash_for(cls.new)
+    assert_same(h1, h1.replace(h2))
+    assert_equal(entries2, h1.to_a)
+
+    assert_raise(TypeError){entries1.hash_for.replace([])}
+
+    k2 = HashKey[-2]
+    pairs2 = entries2.dup
+    pairs2 << [k2, 23]
+    h1 = entries1.hash_for
+    h2 = pairs2.hash_for
+    k2.callback = ->(*){h1.clear; h2.clear}
+    assert_nothing_crashed{h1.replace(h2)}
+
+    assert_raise(FrozenError){h1.freeze.replace(h1)}
+    assert_raise(FrozenError){{}.freeze.replace({})}
+  end
 end
 
-assert('Hash#values', '15.2.13.4.28') do
-  a = { 'abc_key' => 'abc_value' }
+assert('Hash#shift', '15.2.13.4.24') do
+  [ar_entries, ht_entries].each do |entries|
+    pairs = entries.dup
+    h = pairs.hash_for
+    h.delete(pairs.delete_at(0)[0])
+    h.delete(pairs.delete_at(3)[0])
+    until pairs.empty?
+      exp = pairs.shift
+      act = h.shift
+      assert_equal(Array, act.class)
+      assert_equal(exp, act)
+      assert_equal(exp.size, act.size)
+      assert_not_operator(h, :key?, exp[0])
+    end
+
+    assert_equal(nil, h.shift)
+    assert_equal(0, h.size)
+
+    h.default = -456
+    assert_equal(-456, h.shift)
+    assert_equal(0, h.size)
+
+    h.freeze
+    assert_raise(FrozenError){h.shift}
+  end
 
-  assert_equal ['abc_value'], a.values
+  h = Hash.new{|h, k| [h, k]}
+  assert_operator(h.shift, :eql?, [h, nil])
+  assert_equal(0, h.size)
 end
 
 # Not ISO specified
 
-assert('Hash#eql?') do
-  a = { 'a' => 1, 'b' => 2, 'c' => 3 }
-  b = { 'a' => 1, 'b' => 2, 'c' => 3 }
-  c = { 'a' => 1.0, 'b' => 2, 'c' => 3 }
-  assert_true(a.eql?(b))
-  assert_false(a.eql?(c))
-  assert_false(a.eql?(true))
-end
-
-assert('Hash#reject') do
-  h = {:one => 1, :two => 2, :three => 3, :four => 4}
-  ret = h.reject do |k,v|
-    v % 2 == 0
+%i[reject select].each do |meth|
+  assert("Hash##{meth}") do
+    cls = Class.new(Hash){attr_accessor :foo}
+    [ar_entries, ht_entries].each do |entries|
+      params = nil
+      filter = ->((k, v)) do
+        params << [k, v]
+        String === k
+      end
+
+      h = entries.hash_for(cls.new(1))
+      params = []
+      ret = h.__send__(meth, &filter)
+      assert_equal(entries, params)
+      assert_equal(entries, h.to_a)
+      assert_equal(1, h.default)
+      assert_equal(entries.__send__(meth, &filter), ret.to_a)
+      assert_equal(Hash, ret.class)
+      assert_equal(nil, ret.default)
+
+      params = []
+      assert_predicate({}.__send__(meth, &filter), :empty?)
+      assert_predicate(params, :empty?)
+    end
   end
-  assert_equal({:one => 1, :three => 3}, ret)
-  assert_equal({:one => 1, :two => 2, :three => 3, :four => 4}, h)
 end
 
-assert('Hash#reject!') do
-  h = {:one => 1, :two => 2, :three => 3, :four => 4}
-  ret = h.reject! do |k,v|
-    v % 2 == 0
+%i[reject! select!].each do |meth|
+  assert("Hash##{meth}") do
+    [ar_entries, ht_entries].each do |entries|
+      params = nil
+      filter = ->((k, v)) do
+        params << [k, v]
+        String === k
+      end
+
+      pairs = entries.dup << ["_str", 5]
+      h = pairs.hash_for(Hash.new(1))
+      params = []
+      ret = h.__send__(meth, &filter)
+      assert_same(h, ret)
+      assert_equal(pairs, params)
+      assert_equal(pairs.__send__(meth.to_s[0..-2], &filter), h.to_a)
+      assert_equal(1, h.default)
+
+      h = pairs.hash_for
+      ret = h.__send__(meth){meth == :select!}
+      assert_nil(ret)
+      assert_equal(pairs, h.to_a)
+
+      assert_raise(FrozenError){h.freeze.__send__(meth, &filter)}
+    end
+
+    h = {}
+    assert_nil(h.__send__(meth){})
+    assert_predicate(h, :empty?)
   end
-  assert_equal({:one => 1, :three => 3}, ret)
-  assert_equal({:one => 1, :three => 3}, h)
 end
 
-assert('Hash#select') do
-  h = {:one => 1, :two => 2, :three => 3, :four => 4}
-  ret = h.select do |k,v|
-    v % 2 == 0
+%i[inspect to_s].each do |meth|
+  assert("Hash##{meth}") do
+    assert_equal('{}', Hash.new.__send__(meth))
+
+    h1 = {:s => 0, :a => [1,2], 37 => :b, :d => "del", "c" => nil}
+    h1.shift
+    h1.delete(:d)
+    s1 = ':a=>[1, 2], 37=>:b, "c"=>nil'
+    h2 = Hash.new(100)
+
+    (1..14).each{h2[_1] = _1 * 2}
+    h2 = {**h2, **h1}
+    s2 = "1=>2, 2=>4, 3=>6, 4=>8, 5=>10, 6=>12, 7=>14, 8=>16, " \
+         "9=>18, 10=>20, 11=>22, 12=>24, 13=>26, 14=>28, #{s1}"
+
+    [[h1, s1], [h2, s2]].each do |h, s|
+      assert_equal("{#{s}}", h.__send__(meth))
+
+      hh = {}
+      hh[:recur] = hh
+      h.each{|k, v| hh[k] = v}
+      assert_equal("{:recur=>{...}, #{s}}", hh.__send__(meth))
+
+      hh = h.dup
+      hh[hh] = :recur
+      assert_equal("{#{s}, {...}=>:recur}", hh.__send__(meth))
+    end
+
+    [ar_entries, ht_entries].each do |entries|
+      cls = Class.new do
+        attr_accessor :h
+        def inspect; @h.replace(@h.dup); to_s; end
+      end
+      v = cls.new
+      h = entries.hash_for({_k: v})
+      v.h = h
+      assert_nothing_raised{h.__send__(meth)}
+    end
   end
-  assert_equal({:two => 2, :four => 4}, ret)
-  assert_equal({:one => 1, :two => 2, :three => 3, :four => 4}, h)
 end
 
-assert('Hash#select!') do
-  h = {:one => 1, :two => 2, :three => 3, :four => 4}
-  ret = h.select! do |k,v|
-    v % 2 == 0
+assert('Hash#rehash') do
+  cls = Class.new(Hash){attr_accessor :foo}
+  [ar_entries, ht_entries].each do |entries|
+    k1, k2, k3 = HashKey[-1], HashKey[-2], HashKey[-3]
+    pairs = entries.dup.push(
+      [-4, -40],
+      [HashKey[-11], -5],
+      [:_del, "_del"],
+      [k1, :_k1],
+      ["_a", "_b"],
+      [k2, :_k2],
+      ["_c", "_d"],
+      [HashKey[-22], -21],
+      [k3, :_k3],
+    )
+    h = pairs.hash_for(cls.new(:defvar)){|h| h.foo = "f"}
+    k1.value, k2.value, k3.value = -11, -11, -22
+    pairs1 = pairs.dup
+    pairs1.delete([:_del, h.delete(:_del)])
+    exp_pairs1 = pairs1.hash_for.to_a
+    h.freeze
+    assert_same(h, h.rehash)
+    assert_equal(exp_pairs1, h.to_a)
+    assert_equal(exp_pairs1.size, h.size)
+    assert_equal(:defvar, h.default)
+    assert_equal("f", h.foo)
+    exp_pairs1.each {|k, v| assert_equal(v, h[k])}
+
+    # If an error occurs during rehash, at least the entry list is not broken.
+    k1.value, k2.value, k3.value = -1, -2, -3
+    h = pairs.hash_for
+    k1.value = -11
+    pairs2 = pairs.dup
+    pairs2.delete([:_del, h.delete(:_del)])
+    exp_pairs2 = pairs2.hash_for.to_a
+    k2.error = :eql?
+    assert_raise{h.rehash}
+    act_pairs2 = h.to_a
+    unless pairs2 == act_pairs2 && pairs2.size == h.size
+      assert_equal(exp_pairs2, act_pairs2)
+      assert_equal(exp_pairs2.size, h.size)
+    end
+
+    k1.value = -1
+    k2.error = false
+    h = pairs.hash_for
+    k1.callback = ->(name, *){h.clear if name == :eql?}
+    assert_nothing_crashed{h.rehash}
+    k1.callback = ->(name, *){h.clear if name == :hash}
+    assert_nothing_crashed{h.rehash}
   end
-  assert_equal({:two => 2, :four => 4}, ret)
-  assert_equal({:two => 2, :four => 4}, h)
-end
-
-# Not ISO specified
-
-assert('Hash#inspect') do
-  h = { "c" => 300, "a" => 100, "d" => 400, "c" => 300  }
-  h["recur"] = h
-  ret = h.to_s
 
-  assert_include ret, '"c"=>300'
-  assert_include ret, '"a"=>100'
-  assert_include ret, '"d"=>400'
-  assert_include ret, '"recur"=>{...}'
+  h = {}
+  assert_same(h, h.rehash)
+  assert_predicate(h, :empty?)
+end
+
+assert('#eql? receiver should be specified key') do
+  [ar_entries, ht_entries].each do |entries|
+    h = entries.hash_for
+    k0 = HashKey[-99]
+    h[k0] = 1
+
+    k1 = HashKey[-3, error: :eql?]
+    assert_raise{h[k1]}
+    k0.error = :eql?
+    k1.error = false
+    assert_nothing_raised{h[k1]}
+
+    k0.error = false
+    k1.error = :eql?
+    assert_raise{h[k1] = 1}
+    k0.error = :eql?
+    k1.error = false
+    assert_nothing_raised{h[k1] = 1}
+
+    k0.error = false
+    k2 = HashKey[-6, error: :eql?]
+    assert_raise{h.delete(k2)}
+    k0.error = :eql?
+    k2.error = false
+    assert_nothing_raised{h.delete(k2)}
+
+    k0.error = false
+    k3 = HashKey[-9, error: :eql?]
+    %i[has_key? include? key? member?].each do |m|
+      assert_raise{h.__send__(m, k3)}
+    end
+    k0.error = :eql?
+    k3.error = false
+    %i[has_key? include? key? member?].each do |m|
+      assert_nothing_raised{h.__send__(m, k3)}
+    end
+  end
 end
 
-assert('Hash#rehash') do
-  h = {[:a] => "b"}
-  # hash key modified
-  h.keys[0][0] = :b
-  # h[[:b]] => nil
-  h.rehash
-  assert_equal("b", h[[:b]])
-end
+assert('#== receiver should be specified value') do
+  [ar_entries, ht_entries].each do |entries|
+    h = entries.hash_for
+    v0 = HashKey[-99]
+    h[-99] = v0
 
-assert('Hash#freeze') do
-  h = {}.freeze
-  assert_raise(FrozenError) do
-    h[:a] = 'b'
+    v1 = HashKey[-3, error: :==]
+    %i[has_value? value?].each{|m| assert_raise{h.__send__(m, v1)}}
+    v0.error = :==
+    v1.error = false
+    %i[has_value? value?].each{|m| assert_nothing_raised{h.__send__(m, v1)}}
   end
 end