해시 표 의 실현

산 목록 (Hash table, 해시 표 라 고도 함) 은 키워드 (Key value) 에 따라 메모리 에 저 장 된 위치 에 직접 접근 하 는 데이터 구조 입 니 다.즉, 키 값 에 관 한 함 수 를 계산 하여 필요 한 조회 데 이 터 를 표 의 한 위치 에 비 추어 기록 에 접근 하 는 것 은 검색 속 도 를 가속 화 시킨다.이 맵 함 수 는 해시 함수 라 고 하고 기록 을 저장 하 는 배열 을 산 목록 이 라 고 합 니 다.
적용:
  전화번호 부 에 있 는 누군가의 번 호 를 찾기 위해 서 는 이름 의 이니셜 순서대로 배 열 된 표 (즉, 이름 에서 이니셜 까지 의 함수 관 계 를 만 드 는 것) 를 만 들 수 있 고 이니셜 이 W 인 표 에서 '왕' 성의 전화 번 호 를 찾 는 것 이 직접 찾 는 것 보다 훨씬 빠르다.여기 서 사람의 이름 을 키워드 로 사용 합 니 다. '이니셜 추출' 은 이 예 에서 해시 함수 의 함수 법칙 으로 이니셜 을 저장 하 는 표 대응 산 목록 입 니 다.키워드 와 함수 법칙 은 이론 적 으로 임의로 확정 할 수 있다.
기본 개념:

키워드 가 K 이면 그 값 은 저장 위치 에 저 장 됩 니 다.따라서 비교 하지 않 아 도 조사 한 기록 을 직접 얻 을 수 있다.이 대응 관 계 를 해시 함수 라 고 부 르 고 이 사상 에 따라 만들어 진 표 는 산 목록 입 니 다.

서로 다른 키워드 에 대해 같은 해시 주 소 를 얻 을 수 있 습 니 다. 즉, 이러한 현상 을 충돌 (영어: Collision) 이 라 고 합 니 다.같은 함수 값 을 가 진 키 워드 는 이 해시 함수 에 있어 서 동의어 라 고 합 니 다.다시 말 하면 해시 함수 와 충돌 을 처리 하 는 방법 에 따라 한 그룹의 키 워드 를 유한 한 연속 주소 집합 (구간) 에 투사 하고 키워드 가 주소 에 집 중 된 '상' 을 표 에 기 록 된 저장 위치 로 한다. 이런 표 는 산 목록 이 라 고 하 는데 이 방사 과정 을 산열 표 또는 산열 이 라 고 하고 얻 은 저장 위 치 를 산열 주소 라 고 한다.

키워드 집합 에 있 는 모든 키워드 에 대해 해시 함 수 를 통 해 주소 집합 에 있 는 모든 주소 의 확률 이 같다 면 이러한 해시 함 수 를 균일 한 해시 함수 (Uniform Hash function) 라 고 부 릅 니 다. 이것 은 키워드 가 해시 함 수 를 통 해 '무 작위 주소' 를 얻어 충돌 을 줄 이 는 것 입 니 다.

찾기 효율: 
  산 목록 의 검색 과정 은 기본적으로 표를 만 드 는 과정 과 같다.일부 키 코드 는 해시 함수 로 변 환 된 주 소 를 통 해 직접 찾 을 수 있 고, 다른 키 코드 는 해시 함수 가 얻 은 주소 에서 충돌 이 생 겼 으 므 로 충돌 을 처리 하 는 방법 에 따라 찾 아야 한다.소 개 된 세 가지 충돌 처리 방법 중 충돌 이 발생 한 후의 검색 은 여전히 주어진 값 과 관건 적 인 코드 를 비교 하 는 과정 이다.따라서 산 목록 검색 효율 의 양 도 는 평균 검색 길이 로 평가한다.
검색 과정 에서 관건 적 인 코드 의 비교 횟수 는 충돌 이 발생 하 는 횟수 에 달 려 있 고 충돌 이 적 으 며 검색 효율 이 높 고 충돌 이 많 으 며 검색 효율 이 낮다.따라서 충돌 에 얼마나 영향 을 미 치 는 지, 즉 검색 효율 에 영향 을 주 는 요소 다.영향 발생 충돌 은 다음 과 같은 세 가지 요소 가 있다.

해시 함수 가 균일 한 지 여부;

충돌 을 처리 하 는 방법;

산 목록 의 부하 인자

부하 인자:
산 목록 의 부하 인자 정의: = 표 에 있 는 요소 갯 수 / 산 목록 의 길 이 를 입력 하 십시오.
  해시 표 가 가득 찬 정도 의 표지 인자 입 니 다.표 의 길이 가 정 해진 값 이기 때문에 '표 에 채 워 진 요소 의 개수' 와 정비례 하기 때문에 클 수록 표 에 채 워 진 요소 가 많 을 수록 충돌 할 가능성 이 높다 는 것 을 나타 낸다.반대로 작 을 수록 표 에 표 시 된 요소 가 적 을 수록 충돌 할 가능성 이 적다.실제로 산 목록 의 평균 검색 길 이 는 부하 인자 의 함수 이 며 충돌 을 처리 하 는 방법 에 따라 함수 가 다 릅 니 다.
해시 표를 만 드 는 몇 가지 방법:

직접 주소 법 - 키 워드 를 가 져 오 는 특정한 선형 함 수 는 해시 주소 이 고 Hash (Key) = Key 또는 Hash (Key) = A * Key + B, A, B 는 상수 이다.

나머지 법 을 제외 하고 관건 적 인 수 치 를 취 하 는 것 은 산열 표 의 길이 m 보다 크 지 않 은 수 p 에 의 해 제 거 된 나머지 는 산열 주소 이다.Hash（Key）= Key % P。

제곱 취 중 법

접 는 법

난수 법

수학 분석 법

선형 탐지:

#define  _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
#include<vector>
#include<string>

enum Statue  //          
{
EXIST,
DELETE,
EMPTY
};


template<class K, class V>    //    
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<class K>
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<string>
{
size_t operator()(const string str)
{
return BKDRHash(str.c_str());
}
};


template<class K, class V, class _HashFuncer = _HashFuncDefault<K>>
class HashTable
{
typedef HashNode<K, V> 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)//      
{
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)//      
{
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<K,V> 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<K, V>& tem)
{
swap(_table, tem._table);
tem._size = _size;
}
private:
vector<Node> _table;
size_t _size;
};


void test()
{
HashTable<string, string> 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;
}

2 차 탐지:

#define  _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
enum Status
{
EXIST,
DELETE,
EMPTY
};
template<class K, class V>
struct KeyValue
{
K _key;
V _value;
KeyValue(const K& key = K(), const V& value = V())
:_key(key),
_value(value)
{}
};
template<class K, class V>
class HashTable
{
typedef KeyValue<K, V> 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<K, V>& tmp);
size_t _HashFunc(const K& key, size_t i);
private:
type* _table;
size_t _size;
size_t _capacity;
Status* _status;
};
template<class K, class V>
bool HashTable<K, V>::Insert(const K& key, const V& value)
{
if (_size * 10 >= _capacity * 8)//    
{
size_t newcapacity = 2 * _capacity;
HashTable<K, V> 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;//   
size_t index = _HashFunc(key, i);//    
size_t begin = index;
do
{
if (_status[index] == EMPTY || _status[index] == DELETE)//        
break;
if (_status[index] == EXIST && _table[index]._key == key)//      
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<class K, class V>
void HashTable<K, V>::_Swap(HashTable<K, V>& tmp)
{
swap(_table, tmp._table);
swap(_size, tmp._size);
swap(_capacity, tmp._capacity);
swap(_status, tmp._status);
}
template<class K, class V>
size_t HashTable<K, V>::_HashFunc(const K& key, size_t i)
{
size_t ret = (key + i*i) % _capacity;
return ret;
}
template<class K, class V>
void HashTable<K, V>::Print()
{
for (size_t i = 0; i < _capacity; i++)
{
printf(" %d  key: %d  value: %d status: %d 
", i, _table[i]._key, _table[i]._value, _status[i]);
}
}
template<class K, class V>
int HashTable<K, V>::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<class K, class V>
void HashTable<K, V>::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<class K, class V>
void HashTable<K, V>::~HashTable()
{
if (_table)
{
delete[] _table;
}
}
void test()
{
HashTable<int, int>ha(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;
}

본문 은 "fun" 블 로그 에서 나 왔 으 니, 반드시 이 출처 를 보존 하 시기 바 랍 니 다.http://10725723.blog.51cto.com/10715723/1774006