Repository navigation
Expand file tree
/
Copy pathHash_Table.cpp
More file actions
186 lines (170 loc) · 5.43 KB
/
Copy pathHash_Table.cpp
File metadata and controls
186 lines (170 loc) · 5.43 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
//
// Created by DevilInChina on 2018/10/10.
//
#define FIND_CIRCLE 14
#define LENGTH_TYPE 13
#include "MiniPath.cpp"
template <class Index,class Data>
class Hash_Table {
protected:
typedef typename List<std::pair<Index,Data> >::iterator iterator;
bool Equal(const Index&a,const Index&b){
return !(a<b) and !(b<a);
}
const __Index Length[LENGTH_TYPE] = {263, 523, 1031, 2063, 4099, 8219, 16411, 32771, 65539, 131111, 262147, 524347, 1048583};
///所有素数%4==3 在这种情况下进行平方探测会有较好的结果
const __Index Gap[FIND_CIRCLE] = {0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169};
///搜错循环长度，超出此长度认为常数过大，则应构建新的HashTable
std::pair<const Index&, iterator > **Code;///first for number,second for markdown
__Index curMaxSize, curRate;
/**
* @note 重新对内存进行分配
*/
void memAlloc() {
if(Code)for(int i = 0; i < curMaxSize ;++i)delete Code[i];
curMaxSize = Length[curRate];
delete[]Code;
Code = new std::pair<const Index&, iterator >*[curMaxSize];
std::fill(Code,Code+curMaxSize, nullptr);
}
/**
* @param HashCode 对应的Hash编码
* @param DataLoc 对应Hash码得到的数据位置(DataLoc>=0)
* @return 是否插入成功
*/
int Insert(const Index&Ins, iterator it ,__Index HashCode) {
__Index __copy = HashCode;
for (__Index i:Gap) {
HashCode += i;
HashCode %= curMaxSize;
if (!Code[HashCode]) {
Code[HashCode] = new std::pair<const Index&, iterator>(it->first,it);
return 1;
}else {
if (Equal(Code[HashCode]->first, Ins))return -1;
}
}
return 0;
}
/**
* @param Ins 索引值
* @param HashCode 索引值的哈希码
* @return 相应list的迭代器
*/
iterator Erase(const Index &Ins,__Index HashCode){
__Index c = HashCode;
for (__Index i:Gap) {
c+=i;
c%=curMaxSize;
if(Code[c] and Equal(Code[c]->first,Ins)){
auto it = Code[c]->second;
delete Code[c];
Code[c] = nullptr;
return it;
}
}
return iterator(nullptr);
}
iterator Find(const Index&Ins,__Index HashCode){
__Index c = HashCode;
for (__Index i:Gap) {
c+=i;
c%=curMaxSize;
if(Code[c] and Equal(Code[c]->first,Ins)){
return Code[c]->second;
}
}
return iterator(nullptr);
}
public:
explicit Hash_Table(__Index StartSize = 0) {
if (StartSize >= LENGTH_TYPE)StartSize = LENGTH_TYPE-1;
curRate = StartSize;
Code = nullptr;
curMaxSize = Length[StartSize];
memAlloc();
}
~Hash_Table(){
for(int i = 0 ; i < curMaxSize ; ++i)delete Code[i];
delete []Code;
Code = nullptr;
}
};
/**
* @tparam Index
* @tparam Data
* @node 使用时需要定义 unsigned int operator%(const Index&,unsigned int)
*/
template <class Index,class Data>
class Unordered_map:public Hash_Table<Index,Data>{
private:
typedef std::function<__Index (const Index& a,__Index)> HashFun;
typedef typename List<std::pair<Index,Data> >::iterator iterator;
List<std::pair<Index,Data>>store;
HashFun hashFun;
public:
explicit Unordered_map(HashFun func = [](const Index&fi,__Index mod)->__Index{
return fi%mod;
}):Hash_Table<Index,Data>(),hashFun(func){};
void insert(const std::pair<Index,Data>mk){
store.push_front(mk);
int flag = this->Insert(mk.first,store.begin(),hashFun(mk.first,this->curMaxSize));
switch (flag) {
case 1:///正常插入
break;
case -1:///之前已插入
store.pop_front();
break;
case 0: {///插入异常 需要扩容
bool can;
do {
can = false;
++this->curRate;
this->memAlloc();
for (auto it = store.begin(); it != store.end(); ++it) {
if (this->Insert(it->first, it, hashFun(it->first,this->curMaxSize)))continue;
else {
can = true;
break;
}
}
} while (can);
}
break;
default:
break;
}
}
void erase(const Index&fi){
auto it = this->Erase(fi,hashFun(fi,this->curMaxSize));
if(it!= iterator(nullptr)){
store.erase(it);
}
}
Data&operator[](const Index&fi){
__Index code = hashFun(fi,this->curMaxSize);
auto it = this->Find(fi,code);
if(it!=iterator(nullptr)){
return it->second;
}else{
insert(std::make_pair(fi,Data()));
return this->Find(fi,code)->second;
}
}
iterator find(const Index&fi){
auto it = this->Find(fi,hashFun(fi,this->curMaxSize));
if(it!=iterator(nullptr))return it;
else return store.end();
}
iterator begin(){
return store.begin();
}
iterator end(){
return store.end();
}
void Show(){
for(auto c:store){
std::cerr<<c.first<<" "<<c.second<<"\n";
}
}
};