HashMap
Hash通常有几种方法：
- 除留余数法: H(key) = key mod N
- 直接定址法（取关键字或者关键字的某个线性函数值为hash地址): H(key) = key 或 H(key) = a * key + b
- 平方取中法 H(key) = sqrt(abs(key))
通常用的是第一种：除留余数法。
由于Key取值的范围是无限大，所以，得到的hash肯定会有重复。我们称这种重复为产生了冲突。
解决冲突的办法有两类：有的也成为开散列方法(open hashing，也称为拉链法，separate chaining）和闭散列法(closed hashing，也称为开地址方法，open addressing)。
这两种方法的不同之处在于：开散列法把发生冲突的关键码存储在散列表主表之外，而闭散列法把发生冲突的关键码存储在表中另一个槽内。
这里我们介绍开散列法：将所有关键字为同义词的记录存储在一个线性链表中。像这样：
openhashing
//
// Created on 3/27/18.
//
#ifndef AGORITHM_HASHMAP_H
#define AGORITHM_HASHMAP_H
#include <vector>
class HashMap {
public:
using ValueType = int;
explicit HashMap(uint32_t tableSize = 100);
// if = 1, ok.
virtual bool Search(int key, ValueType &value);
virtual bool Remove(int key);
virtual bool Insert(int key, int value);
virtual bool Search(int key, uint32_t &location, ValueType &value);
virtual bool Empty() const;
private:
struct Node {
Node(int key, ValueType value) {
this->key = key;
this->value = value;
}
Node *next = nullptr;
int key = 0;
ValueType value;
};
protected:
uint32_t hash(int key);
private:
const uint32_t TABLE_SIZE = 100;
std::vector<Node *> mTable;
uint32_t mCount = 0;
};
#endif //AGORITHM_HASHMAP_H
