CLRS-Cpp-Implementations-Chapter-11

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

#include "chapter-10/list/list.h"
namespace CLRS
{
  template <typename T, std::size_t m, std::size_t m_d, std::size_t p_m>
  class HashTableChaining;
  template <typename T, std::size_t m, std::size_t m_d, std::size_t p_m>
  void chained_hash_insert(HashTableChaining<T, m, m_d, p_m> &, ListNode<T> &);
  template <typename T, std::size_t m, std::size_t m_d, std::size_t p_m>
  ListNode<T> *chained_hash_search(HashTableChaining<T, m, m_d, p_m> &, T);
  template <typename T, std::size_t m, std::size_t m_d, std::size_t p_m>
  void chained_hash_delete(HashTableChaining<T, m, m_d, p_m> &, ListNode<T> &);

  template <typename T, std::size_t m, std::size_t m_d, std::size_t p_m>
  class HashTableChaining
  {
    List<T> array[m];
  public:
    List<T> &operator[](std::size_t i) {return array[i];}
    /* template needs explicitly instanced
     * with template non-type parameter m,
     * m is a prime number which is not close
     * to any power of 2.
     */
    std::size_t hash_function_division(T key)
    {
      return key % m_d;
    }
    /* template needs explicitly instanced
     * with template non-type parameter p,
     * p is a integer number which is used
     * to calculate a integer: 2^p
     */
    std::size_t hash_function_multiply(T key)
    {
      double A = 0.6180339887;
      std::size_t f_m = 1 << p_m;
      double multi = key * A;
      T int_part = multi;
      double dec_part = multi - int_part;
      return dec_part * f_m;
    }
  };

  template <typename T, std::size_t m, std::size_t m_d, std::size_t p_m>
  void chained_hash_insert(HashTableChaining<T, m, m_d, p_m> &t, ListNode<T> &n)
  {
    std::size_t i = t.hash_function_division(n.get_value());
    list_insert(t[i], n);
  }

  template <typename T, std::size_t m, std::size_t m_d, std::size_t p_m>
  ListNode<T> *chained_hash_search(HashTableChaining<T, m, m_d, p_m> &t, T key)
  {
    std::size_t i = t.hash_function_division(key);
    return list_search(t[i], key);
  }

  template <typename T, std::size_t m, std::size_t m_d, std::size_t p_m>
  void chained_hash_delete(HashTableChaining<T, m, m_d, p_m> &t, ListNode<T> &n)
  {
    std::size_t i = t.hash_function_division(n.get_value());
    list_delete(t[i], n);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

/*
 * Since auxiliary hash functions for linear probing and
 * quadratic probing hash functions are not illustrated in text,
 * both would not be implemented here.
 */
namespace CLRS
{
  // m must be a prime number in this implementation
  template <typename T>
  class HashTableOpenAddressingNode
  {
    T key;
    bool occupied = false;
    bool deleted = false;
  public:
    T get_value() {return key;}
    void set_value(T k) {key = k; occupied = true; deleted = false;}
    void del_value() {deleted = true;}
    bool is_occupied() {return occupied;}
    bool is_deleted() {return deleted;}
  };

  // m must be a prime number in this implementation
  template <typename T, std::size_t m>
  std::size_t hash_function_double(T key, std::size_t i)
  {
    std::size_t first_part = key % m;
    std::size_t second_part = 1 + (key % (m - 1));
    return (first_part + i * second_part) % m;
  }

  template <typename T, std::size_t m>
  std::size_t open_addressing_hash_insert(HashTableOpenAddressingNode<T> (&t)[m], T key)
  {
    std::size_t i = 0;
    while(i != m)
      {
	std::size_t j = hash_function_double<T, m>(key, i);
	if(!t[j].is_occupied() || t[j].is_deleted())
	  {
	    t[j].set_value(key);
	    return j;
	  }
	else
	  ++i;
      }
    throw std::overflow_error("Hash table is overflow");
  }

  /*
   * return -1 it search failed
   * return type is long long which is able to store maximum std::size_t
   */
  template <typename T, std::size_t m>
  long long open_addressing_hash_search(HashTableOpenAddressingNode<T> (&t)[m], std::size_t key)
  {
    std::size_t i = 0;
    std::size_t j = 0;
    do
      {
	j = hash_function_double<T, m>(key, i);
	if(t[j].is_deleted())
	  ;
	else if(t[j].get_value() == key)
	  return j;
	++i;
      }
    while(t[j].is_occupied() && i != m);
    return -1;
  }

  template <typename T, std::size_t m>
  void open_addressing_hash_delete(HashTableOpenAddressingNode<T> (&t)[m], std::size_t key)
  {
    std::size_t i = 0;
    std::size_t j = 0;
    do
      {
	j = hash_function_double<T, m>(key, i);
	if(t[j].is_deleted())
	  ;
	else if(t[j].get_value() == key)
	  {
	    t[j].del_value();
	    return;
	  }
	++i;
      }
    while(t[j].is_occupied() && i != m);
  }
}