Class: HashTable::HashTable Abstract

Inherits:
Object
  • Object
show all
Defined in:
lib/hashtable/hash_table.rb

Overview

This class is abstract.

HashTable

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(capacity = 8, expand: false) ⇒ HashTable

Returns a new instance of HashTable.



11
12
13
14
15
16
17
18
 
# File 'lib/hashtable/hash_table.rb', line 11

def initialize(capacity = 8, expand: false)
  capacity = capacity < 8 ? 8 : 2**(capacity - 1).bit_length
  @buckets = Array.new(capacity)
  @present = SparseBitArray.new
  @deleted = SparseBitArray.new
  @expand = expand
  @num_entries = 0
end

Instance Attribute Details

#num_entries ⇒ Integer (readonly)

Returns nums of HashTable entries.

Returns:

  • (Integer) —

    nums of HashTable entries



9
10
11
 
# File 'lib/hashtable/hash_table.rb', line 9

def num_entries
  @num_entries
end

Instance Method Details

#add(key, traits) ⇒ Integer

Set the entry using a key type that the specified Traits can convert from a real key to an internal key.

Parameters:

  • key (object)
  • traits (object)

Returns:

  • (Integer) —

    internal key



82
83
84
 
# File 'lib/hashtable/hash_table.rb', line 82

def add(key, traits)
  set_as_interal(key, traits)
end

#adds(keys, traits) ⇒ Array<Integer>

Set the entry using a key type that the specified Traits can convert from a real key to an internal key.

Parameters:

  • key (object)
  • traits (object)

Returns:

  • (Array<Integer>) —

    internal key



90
91
92
 
# File 'lib/hashtable/hash_table.rb', line 90

def adds(keys, traits)
  keys.map { |key| set_as_interal(key, traits) }
end

#capacity ⇒ Object 



28
29
30
 
# File 'lib/hashtable/hash_table.rb', line 28

def capacity
  @buckets.length
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


24
25
26
 
# File 'lib/hashtable/hash_table.rb', line 24

def empty?
  size.zero?
end

#find(key, traits) ⇒ Integer

using the specified traits defining hash function and equality.

Parameters:

  • key (object)
  • traits (object)

Returns:

  • (Integer) —

    Find the entry whose key has the specified hash value,

Raises:

  • (ArgumentError) 


36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 
# File 'lib/hashtable/hash_table.rb', line 36

def find(key, traits)
  raise ArgumentError, 'traits must respond to hash_lookup_key method' unless traits.respond_to?(:hash_lookup_key)

  unless traits.respond_to?(:storage_key_to_lookup_key)
    raise ArgumentError,
          'traits must respond to storage_key_to_lookup_key method'
  end
  h = traits.hash_lookup_key(key) % capacity
  i = h
  fisrt_unsed = nil
  loop do
    if present?(i)
      return i if !@buckets[i].nil? && traits.storage_key_to_lookup_key(@buckets[i].first) == key
    else
      fisrt_unsed = i if fisrt_unsed.nil?
      break unless deleted?(i)
    end
    i = (i + 1) % capacity
    break if i == h
  end
  raise ArgumentError if fisrt_unsed.nil?

  fisrt_unsed
end

#get(key, traits) ⇒ Object

Raises:

  • (ArgumentError) 


70
71
72
73
74
75
76
 
# File 'lib/hashtable/hash_table.rb', line 70

def get(key, traits)
  i = find(key, traits)
  bucket = @buckets[i]
  raise ArgumentError if bucket.nil? || bucket.empty?

  bucket.last
end

#set(key, value, traits) ⇒ Integer

Set the entry using a key type that the specified Traits can convert from a real key to an internal key.

Parameters:

  • key (object)
  • value (object)
  • traits (object)

Returns:

  • (Integer) —

    internal key



66
67
68
 
# File 'lib/hashtable/hash_table.rb', line 66

def set(key, value, traits)
  set_as_interal(key, traits, value)
end

#size ⇒ Object 



20
21
22
 
# File 'lib/hashtable/hash_table.rb', line 20

def size
  @present.count
end