?98 ? ??
?99 ? ? ~HashTable();
100 ? ??
101 private:
102 ? ? int _capacity;
103 ? ? hashNode** hashArray;
104 };
105?
106 HashTable::HashTable(int capacity):_capacity(capacity) {
107 ? ? hashArray = new hashNode*[capacity];
108 ? ? for (int i = 0; i < _capacity; ++i) {
109 ? ? ? ? hashArray[i] = NULL;
110 ? ? }
111 }
112?
113 hashNode* HashTable::find(int key) {
114 ? ? for (hashNode* itr = hashArray[key % _capacity]; itr != NULL;
115 ? ? ? ? ? ? itr = itr->next) {
116 ? ? ? ? if (itr->key == key) {
117 ? ? ? ? ? ? return itr;
118 ? ? ? ? }
119 ? ? }
120 ? ? return NULL;
121 }
122?
123 void HashTable::insert(int key, BiListNode* ptr) {
124 ? ? hashNode* tmp = new hashNode(key, ptr);
125 ? ??
126 ? ? int relativeKey = key % _capacity;
127 ? ??
128 ? ? if (hashArray[relativeKey] == NULL) {
129 ? ? ? ? hashArray[relativeKey] = tmp;
130 ? ? ? ? return;
131 ? ? }
132?
133 ? ? tmp->next = hashArray[relativeKey];
134 ? ? hashArray[relativeKey] = tmp;
135 }
136?
137 void HashTable::erase(int key) {
138 ? ? for (hashNode* pre = hashArray[key % _capacity], *itr = pre;
139 ? ? ? ? ? ? itr != NULL; pre = itr, itr = itr->next) {
140 ? ? ? ? if (itr->key == key) {
141 ? ? ? ? ? ? if (itr != pre)
142 ? ? ? ? ? ? ? ? pre->next = itr->next;
143 ? ? ? ? ? ? else // head
144 ? ? ? ? ? ? ? ? hashArray[key % _capacity] = itr->next;
145?
146 ? ? ? ? ? ? delete itr;
147 ? ? ? ? }
148 ? ? }
149 }
150?
151 HashTable::~HashTable() {
152 ? ? for (int i = 0; i < _capacity; ++i) {
153 ? ? ? ? for (hashNode* itr = hashArray[i]; itr != NULL;) {
154 ? ? ? ? ? ? hashNode* tmp = itr;
155 ? ? ? ? ? ? itr = itr->next;
156 ? ? ? ? ? ? delete tmp;
157 ? ? ? ? }
158 ? ? }
159 ? ? delete [] hashArray;
160 }
161?
162 class LRUCache {
163 public:
164 ? ? LRUCache(int capacity):_capacity(capacity) {
165 ? ? ? ? hashTable = new HashTable(1024);
166 ? ? };
167 ? ??
168 ? ? int get(int key);
169 ? ??
170 ? ? void set(int key, int value);
171 ? ??
172 ? ? ~LRUCache() { delete hashTable; }
173 ? ??
174 private:
175 ? ? int _capacity;
176 ? ? BiList bilist;
177 ? ? HashTable* hashTable;
178 };
179?
180 int LRUCache::get(int key) {
181 ? ? hashNode* tmp = hashTable->find(key);
182 ? ? if (tmp != NULL) {
183 ? ? ? ? bilist.move_front(tmp->ptr);
184 ? ? ? ? return tmp->ptr->value;
185 ? ? }
186 ? ? return -1;
187 }
188?
189 void LRUCache::set(int key, int value) {
190 ? ? hashNode* tmp = hashTable->find(key);
191 ? ? if (tmp != NULL) { // set
192 ? ? ? ? bilist.move_front(tmp->ptr);
193 ? ? ? ? tmp->ptr->value = value;
194 ? ? ? ? return;
195 ? ? }
196 ? ??
197 ? ? // insert
198 ? ? if (bilist.size() == _capacity) {
199 ? ? ? ? hashTable->erase((bilist.rbegin())->key);
200 ? ? ? ? bilist.pop_back();
201 ? ? }
202?
203 ? ? bilist.push_front(new BiListNode(key, value));
204 ? ? hashTable->insert(key, bilist.begin());
205 }