#include "pch.h"
#include <iostream>
#include <assert.h>
template<typename T>
class HashTable {
private:
struct Node
{
const int NULL_DATA = -1;
enum { NODE_SIZE = 3 };
T data[NODE_SIZE] = { NULL_DATA, NULL_DATA, NULL_DATA };
struct Node *next = nullptr;
enum {
E_SUCCESS = 0,
E_EXIST = 1,
E_FULL = 2
};
int insert(T val) {
for (int i = 0; i < NODE_SIZE; ++i) {
if (data[i] == val) {
return E_EXIST;
}
if (data[i] == NULL_DATA) {
data[i] = val;
return E_SUCCESS;
}
}
return E_FULL;
}
void dump() {
for (int i = 0; i < NODE_SIZE; ++i) {
std::cout << "\t" << data[i];
}
std::cout << std::endl;
}
};
private:
enum { prime = 7 };
Node* m_table[prime] = { nullptr, };
public:
int hash(int key)
{
return key % prime;
}
int insert(T x)
{
int index = hash(x);
Node *cur = m_table[index];
Node *prev = cur;
while (cur)
{
auto ret = cur->insert(x);
if (Node::E_SUCCESS == ret || Node::E_EXIST == ret) {
return 0;
}
prev = cur;
cur = cur->next;
}
cur = new Node;
assert(cur);
cur->insert(x);
if (prev) {
prev->next = cur;
}
if(!m_table[index]) {
m_table[index] = cur;
}
return 0;
}
void dump() {
for (int i = 0; i < prime; ++i) {
std::cout << "\n[" << i << "]:\n";
Node* ptr = m_table[i];
while (ptr) {
ptr->dump();
ptr = ptr->next;
}
}
}
};
int main()
{
HashTable<int> table;
int array[] = { 4, 15,14,21,87,96,293,35,24,149,19,63,16,103,77,5,153,87,15,145,356,51,68,705,453 };
//int array[] = {1,8,15,22,29,36,43};
for (int i = 0; i < sizeof(array) / sizeof(int); i++)
{
table.insert(array[i]);
}
std::cout << sizeof(array) / sizeof(int) << " data\n";
table.dump();
return 0;
}原文：https://blog.51cto.com/frankniefaquan/2378423