散列表（Hash table，也叫哈希表），是根據(jù)關(guān)鍵字（Key value）而直接訪問在內(nèi)存存儲位置的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過計算一個關(guān)于鍵值的函數(shù)，將所需查詢的數(shù)據(jù)映射到表中一個位置來訪問記錄，這加快了查找速度。這個映射函數(shù)稱做散列函數(shù)，存放記錄的數(shù)組稱做散列表。

在吉隆等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供網(wǎng)站設(shè)計制作、做網(wǎng)站 網(wǎng)站設(shè)計制作按需開發(fā),公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),高端網(wǎng)站設(shè)計,網(wǎng)絡(luò)營銷推廣,成都外貿(mào)網(wǎng)站制作,吉隆網(wǎng)站建設(shè)費用合理。

應(yīng)用：

  一個通俗的例子是，為了查找電話簿中某人的號碼，可以創(chuàng)建一個按照人名首字母順序排列的表（即建立人名到首字母的一個函數(shù)關(guān)系），在首字母為W的表中查找“王”姓的電話號碼，顯然比直接查找就要快得多。這里使用人名作為關(guān)鍵字，“取首字母”是這個例子中散列函數(shù)的函數(shù)法則，存放首字母的表對應(yīng)散列表。關(guān)鍵字和函數(shù)法則理論上可以任意確定。

基本概念：

• 若關(guān)鍵字為K，則其值存放在的存儲位置上。由此，不需比較便可直接取得所查記錄。稱這個對應(yīng)關(guān)系為散列函數(shù)，按這個思想建立的表為散列表。

• 對不同的關(guān)鍵字可能得到同一散列地址，即，而，這種現(xiàn)象稱為沖突（英語：Collision）。具有相同函數(shù)值的關(guān)鍵字對該散列函數(shù)來說稱做同義詞。綜上所述，根據(jù)散列函數(shù)和處理沖突的方法將一組關(guān)鍵字映射到一個有限的連續(xù)的地址集（區(qū)間）上，并以關(guān)鍵字在地址集中的“像”作為記錄在表中的存儲位置，這種表便稱為散列表，這一映射過程稱為散列造表或散列，所得的存儲位置稱散列地址。

• 若對于關(guān)鍵字集合中的任一個關(guān)鍵字，經(jīng)散列函數(shù)映象到地址集合中任何一個地址的概率是相等的，則稱此類散列函數(shù)為均勻散列函數(shù)（Uniform Hash function），這就是使關(guān)鍵字經(jīng)過散列函數(shù)得到一個“隨機(jī)的地址”，從而減少沖突。

查找效率： 

  散列表的查找過程基本上和造表過程相同。一些關(guān)鍵碼可通過散列函數(shù)轉(zhuǎn)換的地址直接找到，另一些關(guān)鍵碼在散列函數(shù)得到的地址上產(chǎn)生了沖突，需要按處理沖突的方法進(jìn)行查找。在介紹的三種處理沖突的方法中，產(chǎn)生沖突后的查找仍然是給定值與關(guān)鍵碼進(jìn)行比較的過程。所以，對散列表查找效率的量度，依然用平均查找長度來衡量。

查找過程中，關(guān)鍵碼的比較次數(shù)，取決于產(chǎn)生沖突的多少，產(chǎn)生的沖突少，查找效率就高，產(chǎn)生的沖突多，查找效率就低。因此，影響產(chǎn)生沖突多少的因素，也就是影響查找效率的因素。影響產(chǎn)生沖突多少有以下三個因素：

1. 散列函數(shù)是否均勻；

2. 處理沖突的方法；

3. 散列表的載荷因子

載荷因子：

散列表的載荷因子定義為： = 填入表中的元素個數(shù) / 散列表的長度。

  是散列表裝滿程度的標(biāo)志因子。由于表長是定值，與“填入表中的元素個數(shù)”成正比，所以，越大，表明填入表中的元素越多，產(chǎn)生沖突的可能性就越大；反之，越小，標(biāo)明填入表中的元素越少，產(chǎn)生沖突的可能性就越小。實際上，散列表的平均查找長度是載荷因子的函數(shù)，只是不同處理沖突的方法有不同的函數(shù)。

構(gòu)造哈希表的幾種方法：

1. 直接定址法--取關(guān)鍵字的某個線性函數(shù)為散列地址，Hash（Key）= Key 或 Hash（Key）= A*Key + B，A、B為常數(shù)。

2. 除留余數(shù)法--取關(guān)鍵值被某個不大于散列表長m的數(shù)p除后的所得的余數(shù)為散列地址。Hash（Key）= Key % P。

3. 平方取中法

4. 折疊法

5. 隨機(jī)數(shù)法

6. 數(shù)學(xué)分析法

線性探測：

#define  _CRT_SECURE_NO_WARNINGS
#include
using namespace std;
#include
#include

enum Statue  //標(biāo)記一個數(shù)的存在狀態(tài)
{
EXIST,
DELETE,
EMPTY
};


template    //定義類型
struct HashNode
{
K _key;
V _value;
Statue statue;

HashNode(const K& key, const V& value)
:_key(key),
_value(value),
statue(EXIST)
{}

HashNode()
:statue(EMPTY)
{}
};


template
struct _HashFuncDefault
{
size_t operator()(const K& key)
{
return key;
}
};


static size_t BKDRHash(const char * str)
{
unsigned int seed = 131; // 31 131 1313 13131 131313
unsigned int hash = 0;
while (*str)
{
hash = hash * seed + (*str++);
}
return (hash & 0x7FFFFFFF);
}


template<>
struct _HashFuncDefault
{
size_t operator()(const string str)
{
return BKDRHash(str.c_str());
}
};


template>
class HashTable
{
typedef HashNode Node;
public:
HashTable()
:_size(0)
{
for (size_t i = 0; i < _table.size(); i++)
{
_table[i].statue = EMPTY;
}
}

bool Insert(const K& key, const V& value)
{
_CheckCapaciy();
size_t index = _HashFunc(key,_table.size());
size_t tmp = index;
if (_table[index]._key == key)//已經(jīng)有這個數(shù)
{
return false;
}
if (_table[index].statue == EXIST)
{
++index;
while (index != tmp)  //保證不走過一圈
{
if (index == _table.size()) //到最后一個就從第一個開始
{
index = 0;
}
if (_table[index].statue != EXIST)//找到可以插入的位置
{
break;
}
if (_table[index]._key == key)//已經(jīng)有這個數(shù)
{
return false;
}
++index;
}
}
_table[index].statue = EXIST;
_table[index]._key = key;
_table[index]._value = value;
++_size;
return true;
}

void Remove(const K& key)
{
size_t index = _HashFunc(key, _table.size());
size_t tmp = index;
if (_table[index]._key != key)
{
++index;
while (index != tmp)
{
if (index == _table.size())
{
index = 0;
}
if (_table[index]._key == key)
{
break;
}
++index;
}
}
if (_table[index]._key == key)
{
_table[index].statue = DELETE;
--_size;
return;
}
return;
}


int Find(const K& key)
{
size_t index = _HashFunc(key, _table.size());
size_t tmp = index;
if (_table[index]._key == key && _table[index].statue == EXIST)
{
return index;
}
else
{
++index;
while (index != tmp)
{
if (index == _table.size())
{
index = 0;
}
if (_table[index]._key == key && _table[index].statue == EXIST)
{
break;
}
++index;
}
}
if (_table[index]._key == key && _table[index].statue == EXIST)
{
return index;
}
return -1;
}
void Print()
{
for (size_t i = 0; i < _table.size(); i++)
{
if (_table[i].statue == EXIST)
{
cout << "KEY:" << _table[i]._key << "  " << "VALUE:" << _table[i]._value<< "  " << "STATUE:" << _table[i].statue << endl;
}
}
}

protected:
size_t _HashFunc(const K& key, size_t capacity)
{
_HashFuncer hf;
return hf(key) % capacity;
}

void _CheckCapaciy()
{
if (_size * 10 >= _table.size())
{
const int _PrimeSize = 28;
static const unsigned long _PrimeList[_PrimeSize] =
{
53ul, 97ul, 193ul, 389ul, 769ul,
1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
1610612741ul, 3221225473ul, 4294967291ul
};
size_t newCapacity = 0;
for (size_t i = 0; i < _PrimeSize; i++)
{
if (_table.size() < _PrimeList[i])
{
newCapacity = _PrimeList[i];
break;
}
}
HashTable tmp;
tmp._table.resize(newCapacity);
for (size_t i = 0; i < _table.size(); i++)
{
tmp.Insert(_table[i]._key, _table[i]._value);
}
Swap(tmp);
}
}


void Swap(HashTable& tem)
{
swap(_table, tem._table);
tem._size = _size;
}
private:
vector _table;
size_t _size;
};


void test()
{
HashTable ht;
ht.Insert("hello", "你好");
ht.Insert("hello", "你好");
ht.Insert("change", "改變");
ht.Insert("world", "世界");
ht.Insert("change", "改變");
ht.Insert("xi'an", "西安");
ht.Remove("hello");
int ret = ht.Find("world");
ht.Print();
}


int main()
{
test();
system("pause");
return 0;
}

二次探測：

#define  _CRT_SECURE_NO_WARNINGS
#include
using namespace std;
enum Status
{
EXIST,
DELETE,
EMPTY
};
template
struct KeyValue
{
K _key;
V _value;
KeyValue(const K& key = K(), const V& value = V())
:_key(key),
_value(value)
{}
};
template
class HashTable
{
typedef KeyValue type;
public:
HashTable()
:_table(NULL),
_size(0),
_capacity(0),
_status(EMPTY)
{}
HashTable(const size_t& size)
:_table(new type[size]),
_size(0),
_capacity(size),
_status(new Status[size])
{
for (size_t i = 0; i < size; i++)
{
_status[i] = EMPTY;
}
}
bool Insert(const K& key, const V& value);
void Print();
int Find(const K& key);
void Remove(const K& key);
~HashTable();
protected:
void _Swap(HashTable& tmp);
size_t _HashFunc(const K& key, size_t i);
private:
type* _table;
size_t _size;
size_t _capacity;
Status* _status;
};
template
bool HashTable::Insert(const K& key, const V& value)
{
if (_size * 10 >= _capacity * 8)//負(fù)載因子
{
size_t newcapacity = 2 * _capacity;
HashTable tmp(newcapacity);
for (size_t i = 0; i < _capacity; i++)
{
tmp.Insert(_table[i]._key, _table[i]._value);
}
this->_Swap(tmp);
}
size_t i = 0;//計數(shù)器
size_t index = _HashFunc(key, i);//計算下標(biāo)
size_t begin = index;
do
{
if (_status[index] == EMPTY || _status[index] == DELETE)//是空或者已經(jīng)刪除
break;
if (_status[index] == EXIST && _table[index]._key == key)//已經(jīng)有這個數(shù)
return true;
index = _HashFunc(key, ++i);
if (index == _capacity)
index = 0;
} while (begin != index);
if (_status[index] == EXIST)
return false;
_table[index]._key = key;
_table[index]._value = value;
_status[index] = EXIST;
++_size;
return true;
}
template
void HashTable::_Swap(HashTable& tmp)
{
swap(_table, tmp._table);
swap(_size, tmp._size);
swap(_capacity, tmp._capacity);
swap(_status, tmp._status);
}
template
size_t HashTable::_HashFunc(const K& key, size_t i)
{
size_t ret = (key + i*i) % _capacity;
return ret;
}
template
void HashTable::Print()
{
for (size_t i = 0; i < _capacity; i++)
{
printf("第%d個 key: %d  value: %d status: %d \n", i, _table[i]._key, _table[i]._value, _status[i]);
}
}
template
int HashTable::Find(const K& key)
{
int i = 0;
size_t index = _HashFunc(key,i);
if (_table[index]._key == key && _status[index]==EXIST)
{
return index;
}
else
{
int begin = index;
++index;
while (index != begin)
{
if (_table[index]._key == key && _status[index] == EXIST)
{
return index;
}
index = _HashFunc(key, ++i);
}
}
return -1;
}
template
void HashTable::Remove(const K& key)
{
int i = 0;
size_t index = _HashFunc(key, i);
if (_table[index]._key == key && _status[index] == EXIST)
{
_status[index] = DELETE;
return;
}
else
{
int begin = index;
++index;
while (index != begin)
{
if (_table[index]._key == key && _status[index] == EXIST)
{
_status[index] = DELETE;
return;
}
index = _HashFunc(key, ++i);
}
}
}
template
void HashTable::~HashTable()
{
if (_table)
{
delete[] _table;
}
}
void test()
{
HashTableha(2);
ha.Insert(0, 1);
ha.Insert(1, 2);
ha.Insert(2, 5);
ha.Insert(3, 8);
ha.Insert(4, 9);
ha.Insert(6, 0);
ha.Print();
int ret=ha.Find(3);
ha.Remove(4);
ha.Print();
}
int main()
{
test();
system("pause");
return 0;
}