19 #ifndef __TPIE_HASHMAP_H__
20 #define __TPIE_HASHMAP_H__
44 inline size_t operator()(
const T & e)
const {
return static_cast<size_t>(e * 103841);}
52 template <
typename T1,
typename T2>
53 struct hash<std::pair<T1,T2> > {
61 inline size_t operator()(
const std::pair<T1,T2> & e)
const {
62 return h1(e.first) + h2(e.second) * 99181;
70 struct hash<const char *> {
77 for(
int i=0; s[i]; i++){
106 template <
typename value_t,
typename hash_t,
typename equal_t,
typename index_t>
109 static const float sc;
111 #pragma pack(push, 1)
158 inline value_t &
get(
size_t idx) {
return buckets[idx].value;}
164 inline const value_t &
get(
size_t idx)
const {
return buckets[idx].value;}
171 for (
size_t i=0; i < buckets.
size(); ++i) {
172 buckets[i].value =
unused;
173 buckets[i].next =
static_cast<index_t
>(i+1);
176 *i = std::numeric_limits<index_t>::max();
185 size_t x=
static_cast<size_t>(99+
static_cast<double>(z)*sc)|1;
201 const equal_t & equal): h(hash), e(equal),
size(0),
unused(u) {
resize(ee);};
207 if (
size == 0)
return buckets.
size();
208 for(
size_t i=0;
true; ++i)
209 if (buckets[i].value !=
unused)
return i;
215 inline size_t end()
const {
return buckets.
size();}
221 inline size_t find(
const value_t & value)
const {
222 size_t v = list[h(value) % list.
size()];
223 while (v != std::numeric_limits<index_t>::max()) {
224 if (e(buckets[v].value, value))
return v;
227 return buckets.
size();
236 inline std::pair<size_t, bool>
insert(
const value_t & val) {
238 size_t hv = h(val) % list.
size();
240 while (v != std::numeric_limits<index_t>::max()) {
241 if (e(buckets[v].value, val))
return std::make_pair(v,
false);
246 first_free = buckets[v].next;
247 buckets[v].value = val;
248 buckets[v].next = list[hv];
251 return std::make_pair(v,
true);
258 inline void erase(
const value_t & val) {
259 size_t hv = h(val) % list.
size();
260 size_t cur = list[hv];
261 size_t prev = std::numeric_limits<size_t>::max();
263 while (!e(buckets[cur].value, val)) {
265 cur = buckets[cur].next;
268 if (prev == std::numeric_limits<size_t>::max())
269 list[hv] = buckets[cur].next;
271 buckets[prev].next = buckets[cur].next;
273 buckets[cur].next = first_free;
274 buckets[cur].value =
unused;
287 template <
typename value_t,
typename hash_t,
typename equal_t,
typename index_t>
290 static const float sc;
332 size_t x=(99+
static_cast<size_t>(
static_cast<float>(element_count)*sc))|1;
342 const hash_t &
hash,
const equal_t & equal):
349 inline size_t find(
const value_t & value)
const {
350 size_t v = h(value) % elements.
size();
351 while (elements[v] !=
unused) {
352 if (e(elements[v], value))
return v;
353 v = (v + 1) % elements.
size();
355 return elements.
size();
363 inline size_t end()
const {
return elements.
size();}
370 if (
size == 0)
return elements.
size();
371 for(
size_t i=0;
true; ++i)
372 if (elements[i] !=
unused)
return i;
379 value_t &
get(
size_t idx) {
return elements[idx];}
385 const value_t &
get(
size_t idx)
const {
return elements[idx];}
391 inline std::pair<size_t, bool>
insert(
const value_t & val) {
392 size_t v = h(val) % elements.
size();
393 while (elements[v] !=
unused) {
394 if (e(elements[v],val)) {
return std::make_pair(v,
false);}
395 v = (v + 1) % elements.
size();
399 return std::make_pair(v,
true);
406 inline void erase(
const value_t & val) {
407 size_t slot =
find(val);
408 size_t cur = (slot+1) % elements.
size();
410 while (elements[cur] !=
unused) {
411 size_t x = h(elements[cur]) % elements.
size();
412 if (x <= slot && (cur > slot || x > cur)) {
413 elements[slot] = elements[cur];
416 cur = (cur+1) % elements.
size();
433 template <
typename key_t,
435 typename hash_t=hash<key_t>,
436 typename equal_t=std::equal_to<key_t>,
437 typename index_t=size_t,
438 template <
typename,
typename,
typename,
typename>
class table_t = chaining_hash_table
442 typedef std::pair<key_t, data_t> value_t;
449 key_equal_t(
const equal_t & equal): e(equal) {}
450 inline bool operator()(
const value_t & a,
const value_t & b)
const {
451 return e(a.first, b.first);
460 key_hash_t(
const hash_t &
hash): h(hash) {}
461 inline size_t operator()(
const value_t & a)
const {
466 typedef table_t<value_t, key_hash_t, key_equal_t, index_t> tbl_t;
473 template <
typename IT>
478 iter_base(IT & t,
size_t c): tbl(t), cur(c) {};
482 inline const key_t & key()
const {
return tbl.get(cur).first;}
483 inline const data_t & value()
const {
return tbl.get(cur).second;}
484 inline const value_t & operator*()
const {
return tbl.get(cur);}
485 inline const value_t * operator->()
const {
return &tbl.get(cur);}
487 template <
typename IIT>
488 inline bool operator==(
const iter_base<IIT> & o)
const {
return o.cur == cur;}
489 template <
typename IIT>
490 inline bool operator!=(
const iter_base<IIT> & o)
const {
return o.cur != cur;}
491 inline void operator++() {
493 while (cur != tbl.end()) {
494 if (tbl.get(cur) != tbl.unused)
break;
508 typedef iter_base<tbl_t> p_t;
510 inline iterator(tbl_t & tbl,
size_t cur): p_t(tbl, cur) {}
514 inline key_t & key() {
return tbl.get(cur)->first;}
515 inline data_t & value() {
return tbl.get(cur)->second;}
516 inline value_t & operator*() {
return tbl.get(cur);}
517 inline value_t * operator->() {
return &tbl.get(cur);}
519 inline bool operator==(
const const_iterator & o)
const {
return o.cur == cur;}
520 inline bool operator!=(
const const_iterator & o)
const {
return o.cur != cur;}
529 return tbl_t::memory_coefficient();
537 return tbl_t::memory_overhead() -
sizeof(tbl_t) +
sizeof(
hash_map);
548 const equal_t & equal=equal_t(),
550 tbl(
size, u, key_hash_t(
hash), key_equal_t(equal)) {}
562 inline void erase(
const key_t & key) {
563 tbl.erase(value_t(key, tbl.unused.second));
577 inline bool insert(
const key_t & key,
const data_t & data) {
578 return tbl.insert(value_t(key, data)).second;
587 return tbl.get(tbl.insert(value_t(key, tbl.unused.second)).first).second;
595 return tbl.get(tbl.find(key))->second;
603 return iterator(tbl, tbl.find(value_t(key, tbl.unused.second)));
611 return const_iterator(tbl, tbl.find(value_t(key, tbl.unused.second)));
620 return tbl.find(value_t(key, tbl.unused.second)) != tbl.end();
656 inline size_t size()
const {
return tbl.size;}
661 inline void clear()
const {tbl.clear();}
673 template <
typename key_t,
674 typename hash_t=hash<key_t>,
675 typename equal_t=std::equal_to<key_t>,
676 typename index_t=size_t,
677 template <
typename,
typename,
typename,
typename>
class table_t=linear_probing_hash_table>
680 typedef table_t<key_t, hash_t, equal_t, index_t> tbl_t;
682 typedef key_t value_t;
687 template <
typename IT>
692 iter_base(IT & t,
size_t c): tbl(t), cur(c) {};
696 inline const value_t & operator*()
const {
return tbl.get(cur);}
697 inline const value_t * operator->()
const {
return &tbl.get(cur);}
698 inline bool operator==(iter_base & o)
const {
return o.cur == cur;}
699 inline bool operator!=(iter_base & o)
const {
return o.cur != cur;}
700 inline void operator++() {
701 while (cur != tbl.end()) {
703 if (tbl.get(cur) != tbl.unused)
break;
716 typedef iter_base<tbl_t> p_t;
718 inline iterator(tbl_t & tbl,
size_t cur): p_t(tbl, cur) {}
722 inline value_t & operator*() {
return tbl.get(cur);}
723 inline value_t * operator->() {
return &tbl.get(cur);}
725 inline bool operator==(
const const_iterator & o)
const {
return o.cur == cur;}
726 inline bool operator!=(
const const_iterator & o)
const {
return o.cur != cur;}
735 return tbl_t::memory_coefficient();
743 return tbl_t::memory_overhead() -
sizeof(tbl_t) +
sizeof(
hash_set);
754 const hash_t &
hash=hash_t(),
const equal_t & equal=equal_t(),
768 inline void erase(
const key_t & key) {tbl.erase(key);}
781 return tbl.insert(key).second;
789 return iterator(tbl, tbl.find(key));
805 inline bool contains(
const key_t & key)
const {
return tbl.find(key) != tbl.end();}
840 inline size_t size()
const {
return tbl.size;}
845 inline void clear()
const {tbl.clear();}
849 template <
typename value_t,
typename hash_t,
typename equal_t,
typename index_t>
850 const float linear_probing_hash_table<value_t, hash_t, equal_t, index_t>::sc = 2.0f;
852 template <
typename value_t,
typename hash_t,
typename equal_t,
typename index_t>
853 const float chaining_hash_table<value_t, hash_t, equal_t, index_t>::sc = 2.f;
856 #endif //__TPIE_HASHMAP_H__
Hash table handling hash collisions by chaining.
void erase(const iterator &iter)
Erase entry from hash set by iterator.
static double memory_overhead()
Return the memory overhead of the structure.
const_iterator begin() const
Return const iterator to beginning of map.
static double memory_overhead()
Return the memory overhead of the structure.
bool is_prime(size_type i)
Check if i is a prime.
void resize(size_t size)
Resize hash map to given size and remove all entries.
const_iterator find(const key_t &key) const
Get const iterator to element.
void clear() const
Clear hash set.
Base class of data structures with linear memory usage.
static double memory_coefficient()
Return the memory coefficient of the structure.
linear_probing_hash_table(size_t ee, value_t u, const hash_t &hash, const equal_t &equal)
Construct a hash table.
iterator end()
Return iterator to end of set.
size_t operator()(const char *s) const
Calculate string hash.
Hash map implementation backed by a template parameterized hash table.
void clear() const
Clear hash map.
iterator begin()
Return iterator to beginning of set.
void resize(size_t element_count)
Resize table to given number of buckets and clear contents.
size_t begin()
Return first bucket entry in use.
size_t operator()(const std::string &s) const
Calculate string hash by using std::string::c_str().
static double memory_coefficient()
Return the memory coefficient of the structure.
static double memory_coefficient()
Return the memory coefficient of the structure.
const_iterator cbegin() const
Return const iterator to beginning of set.
data_t & operator[](const key_t &key)
Look up data by key, creating an unused entry if it does not exist.
size_t begin() const
Return first bucket entry in use.
bool contains(const key_t &key) const
Search for key.
size_t size() const
Return number of keys in set.
hash_map(size_t size=0, const hash_t &hash=hash_t(), const equal_t &equal=equal_t(), value_t u=default_unused< value_t >::v())
Construct hash map.
void erase(const key_t &key)
Erase entry from hash map by key.
Generic internal array with known memory requirements.
bool contains(const key_t &key) const
Search for element with key.
iterator find(const key_t &key)
Get iterator to element.
const data_t & operator[](const key_t &key) const
Look up data by key.
const_iterator cend() const
Return const iterator to end of map.
Default hashing function for integral (size_t-castable) types.
chaining_hash_table(size_t ee, value_t u, const hash_t &hash, const equal_t &equal)
Construct a hash table.
iterator end()
Return iterator to end of map.
static double memory_overhead()
Return the memory overhead of the structure.
void erase(const value_t &val)
Erase value from table.
size_t end() const
Return index greater than any buckets in use.
void clear()
Clear contents of hash table.
const_iterator end() const
Return const iterator to end of set.
Hash set implementation backed by a template parameterized hash table.
iterator begin()
Return iterator to beginning of map.
Default hashing function for C-style strings.
void clear()
Clear contents of hash table.
size_t operator()(const std::pair< T1, T2 > &e) const
Calculate std::pair hash.
bool insert(const key_t &key)
Insert key into set.
void erase(const iterator &iter)
Erase entry from hash map by iterator.
Computations related to prime numbers.
value_t unused
Special constant indicating an unused table entry.
static double memory_coefficient()
Return the memory coefficient of the structure.
void erase(const value_t &val)
Erase value from table.
std::pair< size_t, bool > insert(const value_t &val)
Insert value into hash table.
void resize(size_t size, const T &elm)
Change the size of the array.
std::pair< size_t, bool > insert(const value_t &val)
Insert value into hash table.
void erase(const key_t &key)
Erase entry from hash set by key.
size_t size
Number of buckets in hash table.
iter_base< const tbl_t > const_iterator
Const iterator type.
static double memory_overhead()
Return the memory overhead of the structure.
iter_base< const tbl_t > const_iterator
Const iterator type.
static double memory_coefficient()
Return the memory coefficient of the structure.
size_t find(const value_t &value) const
Find bucket entry containing given value, or end() if not found.
const_iterator begin() const
Return const iterator to beginning of set.
hash_set(size_t size=0, const hash_t &hash=hash_t(), const equal_t &equal=equal_t(), value_t u=default_unused< value_t >::v())
Construct hash set.
Hash table handling hash collisions by linear probing.
const_iterator cbegin() const
Return const iterator to beginning of map.
iterator end()
Return an iterator to the end of the array.
size_t operator()(const T &e) const
Calculate integer hash.
const_iterator end() const
Return const iterator to end of map.
size_t size
Number of buckets in hash table.
iterator begin()
Return an iterator to the beginning of the array.
size_type size() const
Return the size of the array.
iterator find(const key_t &key)
Get iterator to element.
static double memory_overhead()
Return the memory overhead of the structure.
const_iterator find(const key_t &key) const
Get iterator to element.
size_t find(const value_t &value) const
Find bucket entry containing given value, or end() if not found.
size_t end() const
Return index greater than any buckets in use.
value_t unused
Special constant indicating an unused table entry.
size_t size() const
Return number of elements in map.
bool insert(const key_t &key, const data_t &data)
Insert data into the hash map.
const_iterator cend() const
Return const iterator to end of set.
void resize(size_t z)
Resize table to given number of buckets and clear contents.
void resize(size_t size)
Resize hash set to given size and remove all entries.
Default special unused values for standard types.