# 算法导论11.2散列表Hash tables链式法解决碰撞11.3.1除法散列法

11.2是第11章的主要内容，11章叫散列表(Hash Tables)11.2也叫散列表(Hash Tables)

11.3节讲散列函数(比如除尘散列法)，11.4节讲处理碰撞的另外一种方法区别于链式法技术

` `
```/*
* IA_11.2ChainedHash.h
*
*  Created on: Feb 13, 2015
*      Author: sunyj
*/

#ifndef IA_11_2CHAINEDHASH_H_
#define IA_11_2CHAINEDHASH_H_

#include <iostream>
#include <string.h>

#include "IA_10.2LinkedLists.h"

// CHAINED-HASH-INSERT(T, x)
// insert x at the head of list T[h(x.key)]

// CHAINED-HASH-SEARCH(T, k)
// search for an element with key k in list T[h(k)]

// CHAINED-HASH-DELETE(T, x)
// delete x from the list T[h(x.key)]

template <class T> class ChainedHashTable {
public:
ChainedHashTable(int64_t const n) : size(n)
{
data = new LinkedList<int64_t, T>[n]();
}
~ChainedHashTable() {}
int64_t HashFunc(int64_t const key)
{
return key % size;
}
Node<int64_t, T>* search(int64_t const key)
{
return data[HashFunc(key)].search(key);
}
// the user of this class, has to invoke search first
// this interface assume that x was not in the hash table
void insert(Node<int64_t, T>* x)
{
(data[HashFunc(x->key)]).insert(x);
}
void del(Node<int64_t, T>* x)
{
data[HashFunc(x->key)].del(x);
}
void print(int64_t key)
{
data[HashFunc(key)].print();
}
private:
LinkedList<int64_t, T>* data;
int64_t const size;
};

#endif /* IA_11_2CHAINEDHASH_H_ */
```

```/*
* IA_11.2ChainedHash.cpp
*
*  Created on: Feb 12, 2015
*      Author: sunyj
*/

#include "IA_11.2ChainedHash.h"

int main()
{
/*
* A prime not too close to an exact power of 2 is often a good choice for m. For
example, suppose we wish to allocate a hash table, with collisions resolved by
chaining, to hold roughly n = 2000 character strings, where a character has 8 bits.
We don't mind examining an average of 3 elements in an unsuccessful search, and
so we allocate a hash table of size m = 701. We could choose 701 because
it is a prime near 2000=3 but not near any power of 2.
*/
ChainedHashTable<int64_t> table(701); // The division method,

Node<int64_t, int64_t> node1(1, 100);
Node<int64_t, int64_t> node4(4, 400);
Node<int64_t, int64_t> node16(16, 1600);
Node<int64_t, int64_t> node9(9, 900);
if (nullptr == table.search(node1.key))
{	// search before insert
table.insert(&node1);
}
else
{
std::cout << "node1 already exist" << std::endl;
}
if (nullptr == table.search(node1.key))
{
table.insert(&node1);
}
else
{
std::cout << "node1 already exist" << std::endl;
}
table.insert(&node4);
table.insert(&node16);
table.insert(&node9);
table.print(4);
Node<int64_t, int64_t> node25(25, 2500);
table.insert(&node25);
table.print(16);
// search before del, or you are clearly sure that, there are this node exist.
// if node1 is not exist, and you invoke del, program will crush
table.del(&node1);
table.print(9);
Node<int64_t, int64_t>* tmp;
tmp = table.search(9);
table.del(tmp);
table.print(9);
return 0;
}
```
` `

原文作者：孙永杰
原文地址: https://www.cnblogs.com/sunyongjie1984/p/4287759.html
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。