本文中實現了一個簡單的hashtable，不一定實用，但是反應出了hashtable的原理，而且若是面試中讓實現一個hashtable，本文的實現足以應付，我在一次迅雷的面試中就遇到，讓實現一個hashtable。
本文中采用開鏈法（separate chaining）來處理“沖突”（collision），而且hashtable只存儲唯一的元素，不存在重復。
實現代碼如下：
class hashtable
{
public:
// 構造函數，n為想要構造的hashtable的bucket數量
hashtable(size_t n);
~hashtable();
// 插入元素。若元素不存在，插入成功返回true；若元素已存在則插入失敗，返回false
bool insert(const int val);
// 查找元素是否在表中出現
bool find(const int val);
// 刪除元素。若元素存在，刪除成功返回true；若元素不存在則刪除失敗，返回false
bool erase(const int val);
// 清除所有元素
void clear();
// 返回已有元素數目
size_t size();
private:
// bucket中的節點
struct hashtable_node
{
hashtable_node *next;
int val;
hashtable_node(int _val, hashtable_node *_next = NULL):val(_val), next(_next){};
};
// hash函數
size_t hash(unsigned int long x);
// 尋找大於等於n且最接近n的質數
unsigned long next_prime(unsigned long n);
// bucket向量表
vector<hashtable_node*> buckets;
// 元素個數
size_t num_elements;
};
hashtable::hashtable(size_t n)
{
// 將bucket數量設置為大於等於n且最接近n的質數
const size_t n_buckets = next_prime(n);
buckets.reserve(n_buckets);
buckets.insert(buckets.end(), n_buckets, NULL);
num_elements = 0;
};
hashtable::~hashtable()
{
// 清除所有鏈中的節點
clear();
}
bool hashtable::insert(const int val)
{
// 不重復插入。已存在，返回false
if(find(val)) return false;
// 調用hash函數獲得bucket號
const size_t k = hash(val);
// 將新節點直接插入到鏈表頭部
hashtable_node * tmp = new hashtable_node(val);
tmp->next = buckets[k];
buckets[k] = tmp;
++num_elements;
// 插入成功
return true;
}
bool hashtable::find(const int val)
{
const size_t k = hash(val);
hashtable_node *p = buckets[k];
// 在對應的bucket中查找
while(p != NULL)
{
if(p->val = val) return true;
p = p->next;
}
return false;
}
bool hashtable::erase(const int val)
{
const size_t k = hash(val);
hashtable_node *p = buckets[k];
hashtable_node *pre = NULL;
// 找到該節點
while(p != NULL && p->val != val)
{
pre = p;
p = p->next;
}
// 刪除該節點
if(p == NULL) return false;
if(pre == NULL)
buckets[k] = p->next;
else
pre->next = p->next;
delete p;
return true;
}
void hashtable::clear()
{
// 清除所有鏈中的節點
for(int i = 0; i < buckets.size(); i++)
{
hashtable_node *p = buckets[i];
while(p != NULL)
{
hashtable_node *next = p->next;
delete p;
p = next;
}
}
}
size_t hashtable::size()
{
return num_elements;
}
size_t hashtable::hash(unsigned int long x)
{
return x % buckets.size();
}
unsigned long hashtable::next_prime(unsigned long n)
{
static const int num_primes = 28;
static const unsigned long prime_list[num_primes] =
{
53, 97, 193, 389, 769,
1543, 3079 , 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433,
1572869, 3145739, 6291469, 12582917, 25165843,
50331653, 100663319, 201326611, 402653189, 805306457,
1610612741, 3221225473ul, 4294967291ul
};
// 尋找大於等於n且最接近n的質數
int i = 0;
while(i < num_primes && prime_list[i] < n)
i++;
return i == num_primes ? prime_list[num_primes-1] : prime_list[i];
}
