C++ HashMap

C++ HashMap

参考自boost库。

基本原理：

使用连续的内存块（数组）来存储数据，通过一个hash函数（即使每一个元素值都能形成固定的数组下标值），然后数组在相应的位置存起来，不能保证每个元素的关键值与hash函数值是一一对应的（可以有多个元素生成一样的hash值），这时候就需要解决冲突。
我们把数组叫做桶（因为数组把很多相似的元素存放在同一个位置）。

流程：

查找元素
- 元素的关键值通过hash函数计算得到hash值
- 得到桶号（数组下标位置）
- 比较桶的元素值（因为只有一次hash函数的值并不准确）
- 取出相同的元素的关键值，不相等则结束

插入元素
- 元素的关键值通过hash函数计算得到hash值
- 得到桶号（数组下标位置）
- 存放元素

我们需要一个提供hash函数的工具。写出一个行为类，重载()运算符。

class CalculateHashCode
{
public:
  std::size_t operator()(const string& str)
  {
    std::size_t n = 0;
    std::size_t nIndex = str.length();
    while (nIndex) {
      n <<= 5;
      if ((--nIndex)& 1) {
        n += str[nIndex] * 3;
      }
      else {
        n ^= ((n >> 17) | 0x01) * str[nIndex];
      }
    }
    return n;
  }
  std::size_t operator()(const wstring& str)
  {
    std::size_t n = 0;
    std::size_t nIndex = str.length();
    while (nIndex) {
      n <<= 5;
      if ((--nIndex) & 1) {
        n += str[nIndex];
      }
      else {
        n ^= ((n >> 17) | 0x01) * str[nIndex];
      }
    }
    return n;
  }
  std::size_t operator()(const short& nNum)
  {
    return nNum;
  }
  std::size_t operator()(const unsigned short& nNum)
  {
    return nNum;
  }
  std::size_t operator()(const char& nNum)
  {
    return nNum;
  }
  std::size_t operator()(const unsigned char& nNum)
  {
    return nNum;
  }
  std::size_t operator()(const size_t& nNum)
  {
    return nNum;
  }
  std::size_t operator()(const int& nNum)
  {
    return nNum;
  }
  std::size_t operator()(const long long& nNum)
  {
    return (std::size_t)(nNum >> 31 ^ nNum);
  }
  std::size_t operator()(const unsigned long long& nNum)
  {
    return (std::size_t)(nNum >> 31 ^ nNum);
  }
  std::size_t operator()(const float& nNum)
  {
    return (std::size_t)(nNum * 50331653.333333f);
  }
  std::size_t operator()(const double& nNum)
  {
    return (std::size_t)(nNum * 50331653.333333);
  }
  std::size_t operator()(const long double& nNum)
  {
    return (std::size_t)(nNum * 50331653.333333);
  }
};
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

HashMap：

hashMap应该是一个泛型容器，这里使用类模板来抽象数据类型。当然啦，也可以用void*来做出泛型。

template<typename Key, 
  typename Value, 
  typename CalcHash = CalculateHashCode>
1
2
3

三个类型参数名分别是元素的关键字，元素的内容值和计算hash的工具类型，这里我们默认为提供工具类型的是我们所写的计算hash类。

数据成员：

  typedef struct _tagBucket
  {
    iterator _first; //list某一个桶的开始
    iterator _last;  //list某一个桶的最后一个元素
  }Bucket;
  list<ValueType> _listValues;
  Bucket* _arrBuckets;
  std::size_t _nBucketSize;
  CalcHash _calcHash;
1
2
3
4
5
6
7
8
9

_listValues。使用标准库的双向链表来存放全部数据，为什么这样做呢？前面我们说过了当元素关键字冲突，计算到了一个被使用桶时候，这时候需要解决冲突问题，这里我们用将元素插入链表来解决，该方法称为链地址法。
_arrBuckets。 一个我们自定义的数据类型“Bucket”，我们只存放链表的区间范围的迭代器，这样就不需要为每一个桶都做一个链表，而是将每一个桶都想象为一个链表的某一个区间。
_nBucketSize。 桶的大小。
_calcHash。 计算hash值。

供外部使用的类型：

  typedef typename pair<Key, Value> ValueType;
  typedef typename list<ValueType>::iterator iterator;
  typedef typename  list<ValueType>::const_iterator const_iterator;
1
2
3

ValueType。标准库里，一对出现的元素都是用pair来解决的，我们也一样。
iterator。遍历链表元素。
const_iterator。遍历链表const元素。
内部方法：
我们将使用hash函数值的函数都是为私有的方法。

  iterator find(const Key& k, std::size_t nHashCode);
  Value& at(const Key& k, std::size_t nHashCode);
  pair<iterator, bool> insert(const ValueType& v, std::size_t nHashCode);
  void erase(iterator it, std::size_t nHashCode);
  void reHashSize(std::size_t nHashBucketSize);
  static std::size_t hashSize(std::size_t nNumber);//静态函数
1
2
3
4
5
6

find方法：通过一个元素关键字来查找，需要一个hash值，成功返回元素迭代器，失败放回end迭代器。
at方法：通过一个元素关键字来查找，需要一个hash值，成功返回元素的内容，失败插入一个相同关键字并初始化内容的元素，然后返回元素的内容。
insert：插入一个元素，需要一个hash值。不允许重复关键字，成功返回该元素迭代器，bool值为true，失败返回end迭代器，bool值为false。
erase：该元素的迭代器，需要一个hash值（需要知道桶的位置）。
reHashSize：该容器可以扩容。需要一个桶的大小值。
hashSize：通过一个值，提供一个等于该值或者大于该值的值。（提供合适的值，提供素数是不错的办法）

供外部使用的方法：

  HashMap()
    :_calcHash(CalcHash()), _listValues(), _nBucketSize(0), _arrBuckets(nullptr)
  {
    reHashSize(hashSize(1));
  }

  HashMap(const CalcHash& func)
    :_calcHash(func), _listValues(), _nBucketSize(0), _arrBuckets(nullptr) 
  {
    reHashSize(hashSize(1));
  }

  HashMap(const HashMap<Key, Value, CalcHash>& hashMap)
    :_calcHash(hashMap._calcHash), _listValues(hashMap._listValues), _nBucketSize(0), _arrBuckets(nullptr)
  {
    reHashSize(hashSize(_listValues.size()));
  }

  HashMap(const initializer_list<ValueType>& list, const CalcHash& func = CalcHash())
    :_calcHash(func), _listValues(list), _nBucketSize(0), _arrBuckets(nullptr)
  {
    reHashSize(hashSize(_listValues.size()));
  }

  ~HashMap()
  {
    if (_arrBuckets)
      delete[] _arrBuckets;
  }

  std::size_t BucketSize()
  {
    return _nBucketSize;
  }
    iterator begin()
  {
    return _listValues.begin();
  }

  iterator end()
  {
    return _listValues.end();
  }

  const_iterator cbegin() const
  {
    return _listValues.begin();
  }

  const_iterator cend() const
  {
    return _listValues.end();
  }

  bool empty()
  {
    return _listValues.empty();
  }

  Value& at(const Key& k)
  {
    if ((_listValues.size()) >= (_nBucketSize << 1))
      reHashSize(hashSize(_listValues.size()));
    return at(k, calcHashCode(k));
  }

  HashMap<Key, Value, CalcHash>& operator<<(const ValueType& v)
  {
    at(v.first) = v.second;
    return *this;
  }

  Value& operator[](const Key& k)
  {
    return at(k);
  }

  iterator find(const Key& k)
  {
    return find(k, calcHashCode(k));
  }

  void erase(iterator it)
  {
    erase(it, calcHashCode(it->first));
  }

  void erase(const Key& k)
  {
    std::size_t nHashCode = calcHashCode(k);
    erase(find(k, nHashCode), nHashCode);

  }

  pair<iterator, bool> insert(const ValueType& v)
  {
    if ((_listValues.size()) >= (_nBucketSize << 1))
      reHashSize(hashSize(_listValues.size()));
    return insert(v, calcHashCode(v.first));
  }

  void clear()
  {
    _listValues.clear();
    iterator end = _listValues.end();
    for (size_t i = 0; i != num_buckets_; ++i)
      buckets_[i].first = buckets_[i].last = end;
  }
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

大家，都自己实现自己的HashMap吧！