#ifndef HASH_OPEN_H
#define HASH_OPEN_H
#include "iostream"
using namespace std;
template<typename Key,typename T>
class value_type
{
public:
Key first;
T second;
bool occupied;
bool removal;
value_type()
{
occupied = false;
removal = false;
}
value_type(const Key& key, T t):first(key)
{
second = t;
occupied = false;
removal = false;
}
value_type(const value_type& val):first(val.first)
{
second = val.second;
occupied = val.occupied;
removal = val.removal;
}
bool operator==(const value_type& other_value_type)
{
return first == other_value_type.first;
}
};
template<typename Key, typename T, typename Hash_Func>
class hash_map_open
{
typedef Key key_value;
typedef Hash_Func hash_func;
friend ostream& operator<<(ostream& os, hash_map_open<Key,T,Hash_Func>& map_open)
{
hash_map_open<Key,T,Hash_Func>::iterator itr;
for (itr = map_open.begin(); itr!= map_open.end(); itr++)
{
os<<(*itr).first<<" "<<(*itr).second<<endl;
}
os<<endl<<endl;
return os;
}
private:
value_type<key_value,T>* buckets;
unsigned count;
unsigned length;
unsigned count_plus;
hash_func hash;
const static int DEFAULT_SIZE;
const static float MAX_RATIO;
unsigned next_prime(unsigned lenght)
{
unsigned i;
bool factorFound;
lenght = lenght*2+1;
while (true)
{
i = 3;
factorFound = false;
while (i*i < lenght && !factorFound)
{
if (lenght%i == 0)
{
factorFound = true;
}
else
i += 2;
}
if (!factorFound) //i*i >= lenght 对于i。。。
{
return lenght;
}
lenght += 2;
}
}
void check_for_expansion()
{
unsigned hash_int;
unsigned index;
unsigned old_lenght;
unsigned offset;
if (count_plus < int(MAX_RATIO*length))
{
return;
}
value_type<key_value,T>* temp_buckets = buckets;
old_lenght = length;
length = next_prime(length);
buckets = new value_type<key_value,T>[length];
for (unsigned i=0; i<old_lenght; i++)
{
hash_int = hash(temp_buckets[i].first);
index = hash_int%length;
offset = hash_int/length;
if (offset%length == 0)
{
offset = 1;
}
while (buckets[index].occupied)
{
//index = (index+1)%length;
index = (index+offset)%length;
}
buckets[index] = temp_buckets[i];
}
delete []temp_buckets;
count_plus = count;
}
public:
hash_map_open()
{
buckets = new value_type< key_value,T>[DEFAULT_SIZE];
count = 0;
length = DEFAULT_SIZE;
count_plus = 0;
}
~hash_map_open()
{
delete []buckets;
}
unsigned size()
{
return count;
}
bool operator==(const hash_map_open<key_value,T,hash_func>& other)
{
return (buckets == other.buckets)&&
(count == other.count)&&
(length == other.length)&&
(count_plus == other.count_plus);
}
class iterator
{
friend class hash_map_open<key_value,T,hash_func>;
//friend ostream& operator<<(ostream&, hash_map_open<key_value,T,hash_func>);
private:
value_type< key_value,T>* buckets_ptr; //指向数组头指针
value_type< key_value,T>* current_ptr; //指向当前元素指针
unsigned index; //当前元素下标
unsigned lenght; //当前数组长度
public:
iterator operator++(int) //寻找下一个元素
{
iterator temp_itr = *this;
unsigned i = index;
while (i < lenght-1)
{
i++;
if (buckets_ptr[i].occupied)
{
index = i;
current_ptr = buckets_ptr+i;
return temp_itr;
}
}
// i == lenght - 1
i++;
index = i;
current_ptr = buckets_ptr+i; //end
return temp_itr;
}
bool operator==(const iterator& other_iterator)
{
return (buckets_ptr == other_iterator.buckets_ptr)&&
(current_ptr == other_iterator.current_ptr)&&
(index == other_iterator.index)&&
(lenght == other_iterator.lenght);
}
bool operator!=(const iterator& other_iterator)
{
return !(*this == other_iterator);
}
value_type< key_value,T> operator*()
{
return *current_ptr;
}
};
iterator begin() //查找第一个元素
{
if (size()==0)
{
return end();
}
iterator temp_itr;
temp_itr.buckets_ptr = buckets;
int index = 0;
while (index < length)
{
if (buckets[index].occupied)
{
temp_itr.current_ptr = buckets+index;
temp_itr.index = index;
temp_itr.lenght = length;
return temp_itr;
}
index++;
}
//index == length
temp_itr.current_ptr = buckets+index;
temp_itr.index = index;
temp_itr.lenght = length;
return temp_itr;
}
iterator end() //指向数组后的第一个元素
{
iterator temp_itr;
temp_itr.buckets_ptr = buckets;
int index = length;
temp_itr.current_ptr = buckets+index;
temp_itr.index = index;
temp_itr.lenght = length;
return temp_itr;
}
pair<iterator,bool>insert(const value_type< key_value,T>& x)
{
key_value key = x.first;
int index = hash(key)%length;
int offset = hash(key)/length;
if (offset%length == 0)
{
offset = 1;
}
iterator temp_itr;
temp_itr.buckets_ptr = buckets;
while (buckets[index].removal || buckets[index].occupied && buckets[index].first != key)
{
//index = hash(index+1)%length;
index = hash(index+offset)%length;
}
if (buckets[index].occupied && buckets[index].first == key) //已经存在数组中
{
temp_itr.current_ptr = buckets+index;
temp_itr.index = index;
temp_itr.lenght = length;
return pair<iterator,bool>(temp_itr,false);
}
// !buckets[index].occupied && !buckets[index].removal
buckets[index].first = x.first;
buckets[index].second = x.second;
buckets[index].occupied = true;
buckets[index].removal = false;
count++;
count_plus++;
temp_itr.current_ptr = buckets+index;
temp_itr.index = index;
temp_itr.lenght = length;
check_for_expansion();
return pair<iterator,bool>(temp_itr,true);
//return pair<iterator,bool>(find(key),true); //降低了效率
}
iterator find(const key_value& key)
{
int index = hash(key)%length;
int offset = hash(key)/length;
if (offset%length == 0)
{
offset = 1;
}
iterator temp_itr;
temp_itr.buckets_ptr = buckets;
//存在，不同key， 或者已移走
while (buckets[index].removal || (buckets[index].occupied && buckets[index].first != key))
{
//index = hash(index+1)%length;
index = hash(index+offset)%length;
}
if (!buckets[index].occupied && !buckets[index].removal) //不存在
{
return end();
}
//存在
temp_itr.current_ptr = buckets+index;
temp_itr.index = index;
temp_itr.lenght = length;
return temp_itr;
}
void erase(iterator itr)
{
buckets[itr.index].occupied = false;
buckets[itr.index].removal = true;
count--;
}
bool operator[](const key_value& key)
{
return (*(insert(const value_type< key_value,T>(key,T())).first)).second;
}
};
#endif
template<typename Key, typename T, typename Hash_Func>
const int hash_map_open<Key,T,Hash_Func>::DEFAULT_SIZE = 203;
template<typename Key, typename T, typename Hash_Func>
const float hash_map_open<Key,T,Hash_Func>::MAX_RATIO = 0.75;
posted on 2009-12-17 12:16
HenDanTou 阅读(343)
评论(0) 编辑 收藏 引用 所属分类:
数据结构