基于ruby实现的哈希表

编程那点事

自己实现的哈希表,基于ruby3.0.0进行测试,写入性能大约为原来的1/5,读取性能差不多,写入性能低因为动态扩容需要重新计算哈希值

# hash.rb
class HASH
  attr_accessor :size, :arr, :capacity

  def initialize capacity: 128
    @arr = Array.new
    @capacity = capacity
    @arr[@capacity - 1] = []
    @size = 0
    @prng = Random.new
  end

  def set key, value
    hash = get_hash key
    if @arr[hash]
      exist = @arr[hash].detect { |k, v| k == key }
      if exist
        exist[1] = value
      else
        @arr[hash] << [key, value]
        @size += 1
      end
    else
      @arr[hash] = [[key, value]]
      @size += 1
    end
    resize if size / capacity.to_f > 1
    value
  end

  def get key
    hash = get_hash key
    return nil unless @arr[hash]
    value = nil
    @arr[hash].each do |k, v|
      break value = v if k == key 
    end
    value
  end

  def get_hash key
    key.hash % @capacity
  end

  def resize
    new_hash = HASH.new capacity: @capacity * 4
    each do |k, v|
      new_hash[k] = v
    end
    @arr = new_hash.arr
    @capacity = new_hash.capacity
    @size = new_hash.size
  end

  def each &blk
    @arr.each do |elements|
      next if elements.nil? || elements.size.zero?
      elements.each do |key, value|
        blk.call(key, value)
      end
    end
    nil
  end

  def inspect
    result = "{"
    elements = []
    each do |k, v|
      elements << "#{k.inspect} => #{v}"
    end
    result << elements.join(", ")
    result += '}'
    result
  end

  def delete key
    hash = get_hash key
    return nil unless @arr[hash]
    k = @arr[hash].index { |k, _| k == key }
    @arr[hash][k] = nil
    @arr[hash].compact! if @prng.rand(@arr[hash].size).zero?
    @size -= 1
    true
  end

  alias_method :[]=, :set
  alias_method :[], :get
end

benchmark:

require 'securerandom'
require 'benchmark'
require './hash.rb'

strings = []
10000.times do |i|
  strings << SecureRandom.hex
end

h = HASH.new

puts '自己写的hash写入性能'
Benchmark.bm do |x|
  x.report do
    strings.each_with_index do |string, idx|
      h[string] = idx
    end
  end
end
puts '自己写的hash读取性能'
Benchmark.bm do |x|
  x.report do
    strings.each do |string|
      h[string]
      h[string + 'c']
    end
  end
end

puts '原生hash写入性能'
h2 = Hash.new
Benchmark.bm do |x|
  x.report do
    strings.each_with_index do |string, idx|
      h2[string] = idx
    end
  end
end
puts '原生hash读取性能'
Benchmark.bm do |x|
  x.report do
    strings.each do |string|
      h2[string]
      h2[string + 'c']
    end
  end
end

发表于 2021.06.02