HashMap.h 6.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289
  1. #ifndef HASHMAP_H
  2. #define HASHMAP_H
  3. #include "data/List.h"
  4. #include "math/Math.h"
  5. #include "utils/StringBuffer.h"
  6. #include "utils/Types.h"
  7. template<typename K, typename V>
  8. struct HashMap final {
  9. class Node final {
  10. friend HashMap;
  11. friend List<Node>;
  12. K key;
  13. public:
  14. V value;
  15. const K& getKey() const {
  16. return key;
  17. }
  18. private:
  19. template<typename... Args>
  20. Node(const K& key, Args&&... args)
  21. : key(key), value(std::forward<Args>(args)...) {
  22. }
  23. };
  24. using Nodes = List<List<Node>>;
  25. template<typename N, typename I, typename R, R& (*A)(I&)>
  26. class Iterator final {
  27. N& nodes;
  28. int indexA;
  29. int indexB;
  30. public:
  31. Iterator(N& nodes, int indexA, int indexB)
  32. : nodes(nodes), indexA(indexA), indexB(indexB) {
  33. skip();
  34. }
  35. Iterator& operator++() {
  36. indexB++;
  37. skip();
  38. return *this;
  39. }
  40. bool operator!=(const Iterator& other) const {
  41. return indexA != other.indexA || indexB != other.indexB;
  42. }
  43. R& operator*() const {
  44. return A(nodes[indexA][indexB]);
  45. }
  46. private:
  47. void skip() {
  48. while(indexA < nodes.getLength() &&
  49. indexB >= nodes[indexA].getLength()) {
  50. indexA++;
  51. indexB = 0;
  52. }
  53. }
  54. };
  55. template<typename R>
  56. static R& access(R& node) {
  57. return node;
  58. }
  59. template<typename I, typename R>
  60. static R& accessValue(I& node) {
  61. return node.value;
  62. }
  63. static const K& accessKey(const Node& node) {
  64. return node.getKey();
  65. }
  66. template<typename N, typename R>
  67. using BaseEntryIterator = Iterator<N, R, R, access<R>>;
  68. using EntryIterator = BaseEntryIterator<Nodes, Node>;
  69. using ConstEntryIterator = BaseEntryIterator<const Nodes, const Node>;
  70. template<typename N, typename I, typename R>
  71. using BaseValueIterator = Iterator<N, I, R, accessValue<I, R>>;
  72. using ValueIterator = BaseValueIterator<Nodes, Node, V>;
  73. using ConstValueIterator =
  74. BaseValueIterator<const Nodes, const Node, const V>;
  75. using ConstKeyIterator =
  76. Iterator<const Nodes, const Node, const K, accessKey>;
  77. template<typename M, typename I>
  78. struct IteratorAdapter final {
  79. M& map;
  80. I begin() const {
  81. return I(map.nodes, 0, 0);
  82. }
  83. I end() const {
  84. return I(map.nodes, map.nodes.getLength(), 0);
  85. }
  86. };
  87. using EntryIteratorAdapter = IteratorAdapter<HashMap, EntryIterator>;
  88. using ConstEntryIteratorAdapter =
  89. IteratorAdapter<const HashMap, ConstEntryIterator>;
  90. using ValueIteratorAdapter = IteratorAdapter<HashMap, ValueIterator>;
  91. using ConstValueIteratorAdapter =
  92. IteratorAdapter<const HashMap, ConstValueIterator>;
  93. using ConstKeyIteratorAdapter =
  94. IteratorAdapter<const HashMap, ConstKeyIterator>;
  95. private:
  96. Nodes nodes;
  97. int elements;
  98. public:
  99. HashMap(int minCapacity = 8) : elements(0) {
  100. nodes.resize(1 << Math::roundUpLog2(minCapacity));
  101. }
  102. template<typename... Args>
  103. bool tryEmplace(const K& key, Args&&... args) {
  104. rehash();
  105. Hash h = hash(key);
  106. V* v = searchList(key, h);
  107. if(v == nullptr) {
  108. nodes[h].add(key, std::forward<Args>(args)...);
  109. elements++;
  110. return false;
  111. }
  112. return true;
  113. }
  114. template<typename VA>
  115. HashMap& add(const K& key, VA&& value) {
  116. rehash();
  117. Hash h = hash(key);
  118. V* v = searchList(key, h);
  119. if(v == nullptr) {
  120. nodes[h].add(key, std::forward<VA>(value));
  121. elements++;
  122. } else {
  123. *v = std::forward<VA>(value);
  124. }
  125. return *this;
  126. }
  127. bool remove(const K& key) {
  128. List<Node>& list = nodes[hash(key)];
  129. for(int i = 0; i < list.getLength(); i++) {
  130. if(list[i].key == key) {
  131. list.removeBySwap(i);
  132. return true;
  133. }
  134. }
  135. return false;
  136. }
  137. const V* search(const K& key) const {
  138. return searchList(key, hash(key));
  139. }
  140. V* search(const K& key) {
  141. return searchList(key, hash(key));
  142. }
  143. bool contains(const K& key) const {
  144. return search(key) != nullptr;
  145. }
  146. HashMap& clear() {
  147. for(List<Node>& n : nodes) {
  148. n.clear();
  149. }
  150. elements = 0;
  151. return *this;
  152. }
  153. EntryIteratorAdapter entries() {
  154. return {*this};
  155. }
  156. ConstEntryIteratorAdapter entries() const {
  157. return {*this};
  158. }
  159. ConstKeyIteratorAdapter keys() const {
  160. return {*this};
  161. }
  162. ValueIteratorAdapter values() {
  163. return {*this};
  164. }
  165. ConstValueIteratorAdapter values() const {
  166. return {*this};
  167. }
  168. EntryIterator begin() {
  169. return EntryIterator(nodes, 0, 0);
  170. }
  171. EntryIterator end() {
  172. return EntryIterator(nodes, nodes.getLength(), 0);
  173. }
  174. ConstEntryIterator begin() const {
  175. return ConstEntryIterator(nodes, 0, 0);
  176. }
  177. ConstEntryIterator end() const {
  178. return ConstEntryIterator(nodes, nodes.getLength(), 0);
  179. }
  180. template<int L>
  181. void toString(StringBuffer<L>& s) const {
  182. s.append("[");
  183. bool c = false;
  184. for(const List<Node>& list : nodes) {
  185. for(const Node& n : list) {
  186. if(c) {
  187. s.append(", ");
  188. }
  189. s.append(n.key).append(" = ").append(n.value);
  190. c = true;
  191. }
  192. }
  193. s.append("]");
  194. }
  195. private:
  196. template<typename H>
  197. Hash hash(const H& key) const {
  198. return fullHash(key) & (nodes.getLength() - 1);
  199. }
  200. template<typename H>
  201. Hash fullHash(const H& key) const {
  202. return key.hashCode();
  203. }
  204. Hash fullHash(int key) const {
  205. static_assert(sizeof(key) == sizeof(Hash),
  206. "unwanted loose of precision in hash");
  207. return key;
  208. }
  209. Hash fullHash(unsigned int key) const {
  210. static_assert(sizeof(key) == sizeof(Hash),
  211. "unwanted loose of precision in hash");
  212. return key;
  213. }
  214. void rehash() {
  215. if(elements < nodes.getLength()) {
  216. return;
  217. }
  218. HashMap<K, V> map(nodes.getLength() * 2);
  219. for(List<Node>& list : nodes) {
  220. for(Node& n : list) {
  221. map.tryEmplace(n.key, std::move(n.value));
  222. }
  223. }
  224. *this = std::move(map);
  225. }
  226. const V* searchList(const K& key, Hash h) const {
  227. for(const Node& n : nodes[h]) {
  228. if(n.key == key) {
  229. return &n.value;
  230. }
  231. }
  232. return nullptr;
  233. }
  234. V* searchList(const K& key, Hash h) {
  235. return const_cast<V*>(
  236. static_cast<const HashMap*>(this)->searchList(key, h));
  237. }
  238. };
  239. #endif