1	/****************************************************************************
2	**
3	** Copyright (C) 2016 The Qt Company Ltd.
4	** Copyright (C) 2016 Intel Corporation.
5	** Copyright (C) 2012 Giuseppe D'Angelo <dangelog@gmail.com>.
6	** Contact: https://www.qt.io/licensing/
7	**
8	** This file is part of the QtCore module of the Qt Toolkit.
9	**
10	** $QT_BEGIN_LICENSE:LGPL$
11	** Commercial License Usage
12	** Licensees holding valid commercial Qt licenses may use this file in
13	** accordance with the commercial license agreement provided with the
14	** Software or, alternatively, in accordance with the terms contained in
15	** a written agreement between you and The Qt Company. For licensing terms
16	** and conditions see https://www.qt.io/terms-conditions. For further
17	** information use the contact form at https://www.qt.io/contact-us.
18	**
19	** GNU Lesser General Public License Usage
20	** Alternatively, this file may be used under the terms of the GNU Lesser
21	** General Public License version 3 as published by the Free Software
22	** Foundation and appearing in the file LICENSE.LGPL3 included in the
23	** packaging of this file. Please review the following information to
24	** ensure the GNU Lesser General Public License version 3 requirements
25	** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
26	**
27	** GNU General Public License Usage
28	** Alternatively, this file may be used under the terms of the GNU
29	** General Public License version 2.0 or (at your option) the GNU General
30	** Public license version 3 or any later version approved by the KDE Free
31	** Qt Foundation. The licenses are as published by the Free Software
32	** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
33	** included in the packaging of this file. Please review the following
34	** information to ensure the GNU General Public License requirements will
35	** be met: https://www.gnu.org/licenses/gpl-2.0.html and
36	** https://www.gnu.org/licenses/gpl-3.0.html.
37	**
38	** $QT_END_LICENSE$
39	**
40	****************************************************************************/
41
42	// for rand_s, _CRT_RAND_S must be #defined before #including stdlib.h.
43	// put it at the beginning so some indirect inclusion doesn't break it
44	#ifndef _CRT_RAND_S
45	#define _CRT_RAND_S
46	#endif
47	#include <stdlib.h>
48
49	#include "qhash.h"
50
51	#ifdef truncate
52	#undef truncate
53	#endif
54
55	#include <qbitarray.h>
56	#include <qstring.h>
57	#include <qglobal.h>
58	#include <qbytearray.h>
59	#include <qdatetime.h>
60	#include <qbasicatomic.h>
61	#include <qendian.h>
62	#include <private/qsimd_p.h>
63
64	#ifndef QT_BOOTSTRAPPED
65	#include <qcoreapplication.h>
66	#include <qrandom.h>
67	#endif // QT_BOOTSTRAPPED
68
69	#include <limits.h>
70
71	QT_BEGIN_NAMESPACE
72
73	/*
74	The Java's hashing algorithm for strings is a variation of D. J. Bernstein
75	hashing algorithm appeared here http://cr.yp.to/cdb/cdb.txt
76	and informally known as DJB33XX - DJB's 33 Times Xor.
77	Java uses DJB31XA, that is, 31 Times Add.
78
79	The original algorithm was a loop around
80	(h << 5) + h ^ c
81	(which is indeed h*33 ^ c); it was then changed to
82	(h << 5) - h ^ c
83	(so h*31^c: DJB31XX), and the XOR changed to a sum:
84	(h << 5) - h + c
85	(DJB31XA), which can save some assembly instructions.
86
87	Still, we can avoid writing the multiplication as "(h << 5) - h"
88	-- the compiler will turn it into a shift and an addition anyway
89	(for instance, gcc 4.4 does that even at -O0).
90	*/
91
92	#if QT_COMPILER_SUPPORTS_HERE(SSE4_2)
93	static inline bool hasFastCrc32()
94	{
95	return qCpuHasFeature(SSE4_2);
96	}
97
98	template <typename Char>
99	QT_FUNCTION_TARGET(SSE4_2)
100	static uint crc32(const Char *ptr, size_t len, uint h)
101	{
102	// The CRC32 instructions from Nehalem calculate a 32-bit CRC32 checksum
103	const uchar *p = reinterpret_cast<const uchar *>(ptr);
104	const uchar *const e = p + (len * sizeof(Char));
105	# ifdef Q_PROCESSOR_X86_64
106	// The 64-bit instruction still calculates only 32-bit, but without this
107	// variable GCC 4.9 still tries to clear the high bits on every loop
108	qulonglong h2 = h;
109
110	p += 8;
111	for ( ; p <= e; p += 8)
112	h2 = _mm_crc32_u64(C: h2, D: qFromUnaligned<qlonglong>(src: p - 8));
113	h = h2;
114	p -= 8;
115
116	len = e - p;
117	if (len & 4) {
118	h = _mm_crc32_u32(C: h, D: qFromUnaligned<uint>(src: p));
119	p += 4;
120	}
121	# else
122	p += 4;
123	for ( ; p <= e; p += 4)
124	h = _mm_crc32_u32(h, qFromUnaligned<uint>(p - 4));
125	p -= 4;
126	len = e - p;
127	# endif
128	if (len & 2) {
129	h = _mm_crc32_u16(C: h, D: qFromUnaligned<ushort>(src: p));
130	p += 2;
131	}
132	if (sizeof(Char) == 1 && len & 1)
133	h = _mm_crc32_u8(C: h, D: *p);
134	return h;
135	}
136	#elif defined(__ARM_FEATURE_CRC32)
137	static inline bool hasFastCrc32()
138	{
139	return qCpuHasFeature(CRC32);
140	}
141
142	template <typename Char>
143	#if defined(Q_PROCESSOR_ARM_64)
144	QT_FUNCTION_TARGET(CRC32)
145	#endif
146	static uint crc32(const Char *ptr, size_t len, uint h)
147	{
148	// The crc32[whbd] instructions on Aarch64/Aarch32 calculate a 32-bit CRC32 checksum
149	const uchar *p = reinterpret_cast<const uchar *>(ptr);
150	const uchar *const e = p + (len * sizeof(Char));
151
152	#ifndef __ARM_FEATURE_UNALIGNED
153	if (Q_UNLIKELY(reinterpret_cast<quintptr>(p) & 7)) {
154	if ((sizeof(Char) == 1) && (reinterpret_cast<quintptr>(p) & 1) && (e - p > 0)) {
155	h = __crc32b(h, *p);
156	++p;
157	}
158	if ((reinterpret_cast<quintptr>(p) & 2) && (e >= p + 2)) {
159	h = __crc32h(h, *reinterpret_cast<const uint16_t *>(p));
160	p += 2;
161	}
162	if ((reinterpret_cast<quintptr>(p) & 4) && (e >= p + 4)) {
163	h = __crc32w(h, *reinterpret_cast<const uint32_t *>(p));
164	p += 4;
165	}
166	}
167	#endif
168
169	for ( ; p + 8 <= e; p += 8)
170	h = __crc32d(h, *reinterpret_cast<const uint64_t *>(p));
171
172	len = e - p;
173	if (len == 0)
174	return h;
175	if (len & 4) {
176	h = __crc32w(h, *reinterpret_cast<const uint32_t *>(p));
177	p += 4;
178	}
179	if (len & 2) {
180	h = __crc32h(h, *reinterpret_cast<const uint16_t *>(p));
181	p += 2;
182	}
183	if (sizeof(Char) == 1 && len & 1)
184	h = __crc32b(h, *p);
185	return h;
186	}
187	#else
188	static inline bool hasFastCrc32()
189	{
190	return false;
191	}
192
193	static uint crc32(...)
194	{
195	Q_UNREACHABLE();
196	return 0;
197	}
198	#endif
199
200	static inline uint hash(const uchar *p, size_t len, uint seed) noexcept
201	{
202	uint h = seed;
203
204	if (seed && hasFastCrc32())
205	return crc32(ptr: p, len, h);
206
207	for (size_t i = 0; i < len; ++i)
208	h = 31 * h + p[i];
209
210	return h;
211	}
212
213	uint qHashBits(const void *p, size_t len, uint seed) noexcept
214	{
215	return hash(p: static_cast<const uchar*>(p), len: int(len), seed);
216	}
217
218	static inline uint hash(const QChar *p, size_t len, uint seed) noexcept
219	{
220	uint h = seed;
221
222	if (seed && hasFastCrc32())
223	return crc32(ptr: p, len, h);
224
225	for (size_t i = 0; i < len; ++i)
226	h = 31 * h + p[i].unicode();
227
228	return h;
229	}
230
231	uint qHash(const QByteArray &key, uint seed) noexcept
232	{
233	return hash(p: reinterpret_cast<const uchar *>(key.constData()), len: size_t(key.size()), seed);
234	}
235
236	#if QT_STRINGVIEW_LEVEL < 2
237	uint qHash(const QString &key, uint seed) noexcept
238	{
239	return hash(p: key.unicode(), len: size_t(key.size()), seed);
240	}
241
242	uint qHash(const QStringRef &key, uint seed) noexcept
243	{
244	return hash(p: key.unicode(), len: size_t(key.size()), seed);
245	}
246	#endif
247
248	uint qHash(QStringView key, uint seed) noexcept
249	{
250	return hash(p: key.data(), len: key.size(), seed);
251	}
252
253	uint qHash(const QBitArray &bitArray, uint seed) noexcept
254	{
255	int m = bitArray.d.size() - 1;
256	uint result = hash(p: reinterpret_cast<const uchar *>(bitArray.d.constData()),
257	len: size_t(qMax(a: 0, b: m)), seed);
258
259	// deal with the last 0 to 7 bits manually, because we can't trust that
260	// the padding is initialized to 0 in bitArray.d
261	int n = bitArray.size();
262	if (n & 0x7)
263	result = ((result << 4) + bitArray.d.at(i: m)) & ((1 << n) - 1);
264	return result;
265	}
266
267	uint qHash(QLatin1String key, uint seed) noexcept
268	{
269	return hash(p: reinterpret_cast<const uchar *>(key.data()), len: size_t(key.size()), seed);
270	}
271
272	/*!
273	\internal
274
275	Creates the QHash random seed from various sources.
276	In order of decreasing precedence:
277	- under Unix, it attemps to read from /dev/urandom;
278	- under Unix, it attemps to read from /dev/random;
279	- under Windows, it attempts to use rand_s;
280	- as a general fallback, the application's PID, a timestamp and the
281	address of a stack-local variable are used.
282	*/
283	static uint qt_create_qhash_seed()
284	{
285	uint seed = 0;
286
287	#ifndef QT_BOOTSTRAPPED
288	QByteArray envSeed = qgetenv(varName: "QT_HASH_SEED");
289	if (!envSeed.isNull()) {
290	uint seed = envSeed.toUInt();
291	if (seed) {
292	// can't use qWarning here (reentrancy)
293	fprintf(stderr, format: "QT_HASH_SEED: forced seed value is not 0, cannot guarantee that the "
294	"hashing functions will produce a stable value.");
295	}
296	return seed;
297	}
298
299	seed = QRandomGenerator::system()->generate();
300	#endif // QT_BOOTSTRAPPED
301
302	return seed;
303	}
304
305	/*
306	The QHash seed itself.
307	*/
308	static QBasicAtomicInt qt_qhash_seed = Q_BASIC_ATOMIC_INITIALIZER(-1);
309
310	/*!
311	\internal
312
313	Seed == -1 means it that it was not initialized yet.
314
315	We let qt_create_qhash_seed return any unsigned integer,
316	but convert it to signed in order to initialize the seed.
317
318	We don't actually care about the fact that different calls to
319	qt_create_qhash_seed() might return different values,
320	as long as in the end everyone uses the very same value.
321	*/
322	static void qt_initialize_qhash_seed()
323	{
324	if (qt_qhash_seed.loadRelaxed() == -1) {
325	int x(qt_create_qhash_seed() & INT_MAX);
326	qt_qhash_seed.testAndSetRelaxed(expectedValue: -1, newValue: x);
327	}
328	}
329
330	/*! \relates QHash
331	\since 5.6
332
333	Returns the current global QHash seed.
334
335	The seed is set in any newly created QHash. See \l{qHash} about how this seed
336	is being used by QHash.
337
338	\sa qSetGlobalQHashSeed
339	*/
340	int qGlobalQHashSeed()
341	{
342	qt_initialize_qhash_seed();
343	return qt_qhash_seed.loadRelaxed();
344	}
345
346	/*! \relates QHash
347	\since 5.6
348
349	Sets the global QHash seed to \a newSeed.
350
351	Manually setting the global QHash seed value should be done only for testing
352	and debugging purposes, when deterministic and reproducible behavior on a QHash
353	is needed. We discourage to do it in production code as it can make your
354	application susceptible to \l{algorithmic complexity attacks}.
355
356	From Qt 5.10 and onwards, the only allowed values are 0 and -1. Passing the
357	value -1 will reinitialize the global QHash seed to a random value, while
358	the value of 0 is used to request a stable algorithm for C++ primitive
359	types types (like \c int) and string types (QString, QByteArray).
360
361	The seed is set in any newly created QHash. See \l{qHash} about how this seed
362	is being used by QHash.
363
364	If the environment variable \c QT_HASH_SEED is set, calling this function will
365	result in a no-op.
366
367	\sa qGlobalQHashSeed
368	*/
369	void qSetGlobalQHashSeed(int newSeed)
370	{
371	if (qEnvironmentVariableIsSet(varName: "QT_HASH_SEED"))
372	return;
373	if (newSeed == -1) {
374	int x(qt_create_qhash_seed() & INT_MAX);
375	qt_qhash_seed.storeRelaxed(newValue: x);
376	} else {
377	if (newSeed) {
378	// can't use qWarning here (reentrancy)
379	fprintf(stderr, format: "qSetGlobalQHashSeed: forced seed value is not 0, cannot guarantee that the "
380	"hashing functions will produce a stable value.");
381	}
382	qt_qhash_seed.storeRelaxed(newValue: newSeed & INT_MAX);
383	}
384	}
385
386	/*!
387	\internal
388
389	Private copy of the implementation of the Qt 4 qHash algorithm for strings,
390	(that is, QChar-based arrays, so all QString-like classes),
391	to be used wherever the result is somehow stored or reused across multiple
392	Qt versions. The public qHash implementation can change at any time,
393	therefore one must not rely on the fact that it will always give the same
394	results.
395
396	The qt_hash functions must *never* change their results.
397
398	This function can hash discontiguous memory by invoking it on each chunk,
399	passing the previous's result in the next call's \a chained argument.
400	*/
401	uint qt_hash(QStringView key, uint chained) noexcept
402	{
403	auto n = key.size();
404	auto p = key.utf16();
405
406	uint h = chained;
407
408	while (n--) {
409	h = (h << 4) + *p++;
410	h ^= (h & 0xf0000000) >> 23;
411	h &= 0x0fffffff;
412	}
413	return h;
414	}
415
416	/*
417	The prime_deltas array contains the difference between a power
418	of two and the next prime number:
419
420	prime_deltas[i] = nextprime(2^i) - 2^i
421
422	Basically, it's sequence A092131 from OEIS, assuming:
423	- nextprime(1) = 1
424	- nextprime(2) = 2
425	and
426	- left-extending it for the offset 0 (A092131 starts at i=1)
427	- stopping the sequence at i = 28 (the table is big enough...)
428	*/
429
430	static const uchar prime_deltas[] = {
431	0, 0, 1, 3, 1, 5, 3, 3, 1, 9, 7, 5, 3, 17, 27, 3,
432	1, 29, 3, 21, 7, 17, 15, 9, 43, 35, 15, 0, 0, 0, 0, 0
433	};
434
435	/*
436	The primeForNumBits() function returns the prime associated to a
437	power of two. For example, primeForNumBits(8) returns 257.
438	*/
439
440	static inline int primeForNumBits(int numBits)
441	{
442	return (1 << numBits) + prime_deltas[numBits];
443	}
444
445	/*
446	Returns the smallest integer n such that
447	primeForNumBits(n) >= hint.
448	*/
449	static int countBits(int hint)
450	{
451	int numBits = 0;
452	int bits = hint;
453
454	while (bits > 1) {
455	bits >>= 1;
456	numBits++;
457	}
458
459	if (numBits >= (int)sizeof(prime_deltas)) {
460	numBits = sizeof(prime_deltas) - 1;
461	} else if (primeForNumBits(numBits) < hint) {
462	++numBits;
463	}
464	return numBits;
465	}
466
467	/*
468	A QHash has initially around pow(2, MinNumBits) buckets. For
469	example, if MinNumBits is 4, it has 17 buckets.
470	*/
471	const int MinNumBits = 4;
472
473	const QHashData QHashData::shared_null = {
474	.fakeNext: nullptr, .buckets: nullptr, Q_REFCOUNT_INITIALIZE_STATIC, .size: 0, .nodeSize: 0, .userNumBits: MinNumBits, .numBits: 0, .numBuckets: 0, .seed: 0, .sharable: true, .strictAlignment: false, .reserved: 0
475	};
476
477	void *QHashData::allocateNode(int nodeAlign)
478	{
479	void *ptr = strictAlignment ? qMallocAligned(size: nodeSize, alignment: nodeAlign) : malloc(size: nodeSize);
480	Q_CHECK_PTR(ptr);
481	return ptr;
482	}
483
484	void QHashData::freeNode(void *node)
485	{
486	if (strictAlignment)
487	qFreeAligned(ptr: node);
488	else
489	free(ptr: node);
490	}
491
492	QHashData *QHashData::detach_helper(void (*node_duplicate)(Node *, void *),
493	void (*node_delete)(Node *),
494	int nodeSize,
495	int nodeAlign)
496	{
497	union {
498	QHashData *d;
499	Node *e;
500	};
501	if (this == &shared_null)
502	qt_initialize_qhash_seed(); // may throw
503	d = new QHashData;
504	d->fakeNext = nullptr;
505	d->buckets = nullptr;
506	d->ref.initializeOwned();
507	d->size = size;
508	d->nodeSize = nodeSize;
509	d->userNumBits = userNumBits;
510	d->numBits = numBits;
511	d->numBuckets = numBuckets;
512	d->seed = (this == &shared_null) ? uint(qt_qhash_seed.loadRelaxed()) : seed;
513	d->sharable = true;
514	d->strictAlignment = nodeAlign > 8;
515	d->reserved = 0;
516
517	if (numBuckets) {
518	QT_TRY {
519	d->buckets = new Node *[numBuckets];
520	} QT_CATCH(...) {
521	// restore a consistent state for d
522	d->numBuckets = 0;
523	// roll back
524	d->free_helper(node_delete);
525	QT_RETHROW;
526	}
527
528	Node *this_e = reinterpret_cast<Node *>(this);
529	for (int i = 0; i < numBuckets; ++i) {
530	Node **nextNode = &d->buckets[i];
531	Node *oldNode = buckets[i];
532	while (oldNode != this_e) {
533	QT_TRY {
534	Node *dup = static_cast<Node *>(allocateNode(nodeAlign));
535
536	QT_TRY {
537	node_duplicate(oldNode, dup);
538	} QT_CATCH(...) {
539	freeNode( node: dup );
540	QT_RETHROW;
541	}
542
543	*nextNode = dup;
544	nextNode = &dup->next;
545	oldNode = oldNode->next;
546	} QT_CATCH(...) {
547	// restore a consistent state for d
548	*nextNode = e;
549	d->numBuckets = i+1;
550	// roll back
551	d->free_helper(node_delete);
552	QT_RETHROW;
553	}
554	}
555	*nextNode = e;
556	}
557	}
558	return d;
559	}
560
561	void QHashData::free_helper(void (*node_delete)(Node *))
562	{
563	if (node_delete) {
564	Node *this_e = reinterpret_cast<Node *>(this);
565	Node **bucket = reinterpret_cast<Node **>(this->buckets);
566
567	int n = numBuckets;
568	while (n--) {
569	Node *cur = *bucket++;
570	while (cur != this_e) {
571	Node *next = cur->next;
572	node_delete(cur);
573	freeNode(node: cur);
574	cur = next;
575	}
576	}
577	}
578	delete [] buckets;
579	delete this;
580	}
581
582	QHashData::Node *QHashData::nextNode(Node *node)
583	{
584	union {
585	Node *next;
586	Node *e;
587	QHashData *d;
588	};
589	next = node->next;
590	Q_ASSERT_X(next, "QHash", "Iterating beyond end()");
591	if (next->next)
592	return next;
593
594	int start = (node->h % d->numBuckets) + 1;
595	Node **bucket = d->buckets + start;
596	int n = d->numBuckets - start;
597	while (n--) {
598	if (*bucket != e)
599	return *bucket;
600	++bucket;
601	}
602	return e;
603	}
604
605	QHashData::Node *QHashData::previousNode(Node *node)
606	{
607	union {
608	Node *e;
609	QHashData *d;
610	};
611
612	e = node;
613	while (e->next)
614	e = e->next;
615
616	int start;
617	if (node == e)
618	start = d->numBuckets - 1;
619	else
620	start = node->h % d->numBuckets;
621
622	Node *sentinel = node;
623	Node **bucket = d->buckets + start;
624	while (start >= 0) {
625	if (*bucket != sentinel) {
626	Node *prev = *bucket;
627	while (prev->next != sentinel)
628	prev = prev->next;
629	return prev;
630	}
631
632	sentinel = e;
633	--bucket;
634	--start;
635	}
636	Q_ASSERT_X(start >= 0, "QHash", "Iterating backward beyond begin()");
637	return e;
638	}
639
640	/*
641	If hint is negative, -hint gives the approximate number of
642	buckets that should be used for the hash table. If hint is
643	nonnegative, (1 << hint) gives the approximate number
644	of buckets that should be used.
645	*/
646	void QHashData::rehash(int hint)
647	{
648	if (hint < 0) {
649	hint = countBits(hint: -hint);
650	if (hint < MinNumBits)
651	hint = MinNumBits;
652	userNumBits = hint;
653	while (primeForNumBits(numBits: hint) < (size >> 1))
654	++hint;
655	} else if (hint < MinNumBits) {
656	hint = MinNumBits;
657	}
658
659	if (numBits != hint) {
660	Node *e = reinterpret_cast<Node *>(this);
661	Node **oldBuckets = buckets;
662	int oldNumBuckets = numBuckets;
663
664	int nb = primeForNumBits(numBits: hint);
665	buckets = new Node *[nb];
666	numBits = hint;
667	numBuckets = nb;
668	for (int i = 0; i < numBuckets; ++i)
669	buckets[i] = e;
670
671	for (int i = 0; i < oldNumBuckets; ++i) {
672	Node *firstNode = oldBuckets[i];
673	while (firstNode != e) {
674	uint h = firstNode->h;
675	Node *lastNode = firstNode;
676	while (lastNode->next != e && lastNode->next->h == h)
677	lastNode = lastNode->next;
678
679	Node *afterLastNode = lastNode->next;
680	Node **beforeFirstNode = &buckets[h % numBuckets];
681	while (*beforeFirstNode != e)
682	beforeFirstNode = &(*beforeFirstNode)->next;
683	lastNode->next = *beforeFirstNode;
684	*beforeFirstNode = firstNode;
685	firstNode = afterLastNode;
686	}
687	}
688	delete [] oldBuckets;
689	}
690	}
691
692	#ifdef QT_QHASH_DEBUG
693
694	void QHashData::dump()
695	{
696	qDebug("Hash data (ref = %d, size = %d, nodeSize = %d, userNumBits = %d, numBits = %d, numBuckets = %d)",
697	int(ref), size, nodeSize, userNumBits, numBits,
698	numBuckets);
699	qDebug(" %p (fakeNode = %p)", this, fakeNext);
700	for (int i = 0; i < numBuckets; ++i) {
701	Node *n = buckets[i];
702	if (n != reinterpret_cast<Node *>(this)) {
703	QString line = QString::asprintf("%d:", i);
704	while (n != reinterpret_cast<Node *>(this)) {
705	line += QString::asprintf(" -> [%p]", n);
706	if (!n) {
707	line += " (CORRUPT)";
708	break;
709	}
710	n = n->next;
711	}
712	qDebug("%ls", qUtf16Printable(line));
713	}
714	}
715	}
716
717	void QHashData::checkSanity()
718	{
719	if (Q_UNLIKELY(fakeNext))
720	qFatal("Fake next isn't 0");
721
722	for (int i = 0; i < numBuckets; ++i) {
723	Node *n = buckets[i];
724	Node *p = n;
725	if (Q_UNLIKELY(!n))
726	qFatal("%d: Bucket entry is 0", i);
727	if (n != reinterpret_cast<Node *>(this)) {
728	while (n != reinterpret_cast<Node *>(this)) {
729	if (Q_UNLIKELY(!n->next))
730	qFatal("%d: Next of %p is 0, should be %p", i, n, this);
731	n = n->next;
732	}
733	}
734	}
735	}
736	#endif
737
738	/*!
739	\fn template <typename T1, typename T2> uint qHash(const QPair<T1, T2> &key, uint seed = 0)
740	\since 5.0
741	\relates QHash
742
743	Returns the hash value for the \a key, using \a seed to seed the calculation.
744
745	Types \c T1 and \c T2 must be supported by qHash().
746	*/
747
748	/*!
749	\fn template <typename T1, typename T2> uint qHash(const std::pair<T1, T2> &key, uint seed = 0)
750	\since 5.7
751	\relates QHash
752
753	Returns the hash value for the \a key, using \a seed to seed the calculation.
754
755	Types \c T1 and \c T2 must be supported by qHash().
756
757	\note The return type of this function is \e{not} the same as that of
758	\snippet code/src_corelib_tools_qhash.cpp 29
759	The two functions use different hashing algorithms; due to binary compatibility
760	constraints, we cannot change the QPair algorithm to match the std::pair one before Qt 6.
761	*/
762
763	/*! \fn template <typename InputIterator> uint qHashRange(InputIterator first, InputIterator last, uint seed = 0)
764	\relates QHash
765	\since 5.5
766
767	Returns the hash value for the range [\a{first},\a{last}), using \a seed
768	to seed the calculation, by successively applying qHash() to each
769	element and combining the hash values into a single one.
770
771	The return value of this function depends on the order of elements
772	in the range. That means that
773
774	\snippet code/src_corelib_tools_qhash.cpp 30
775
776	and
777	\snippet code/src_corelib_tools_qhash.cpp 31
778
779	hash to \b{different} values. If order does not matter, for example for hash
780	tables, use qHashRangeCommutative() instead. If you are hashing raw
781	memory, use qHashBits().
782
783	Use this function only to implement qHash() for your own custom
784	types. For example, here's how you could implement a qHash() overload for
785	std::vector<int>:
786
787	\snippet code/src_corelib_tools_qhash.cpp qhashrange
788
789	It bears repeating that the implementation of qHashRange() - like
790	the qHash() overloads offered by Qt - may change at any time. You
791	\b{must not} rely on the fact that qHashRange() will give the same
792	results (for the same inputs) across different Qt versions, even
793	if qHash() for the element type would.
794
795	\sa qHashBits(), qHashRangeCommutative()
796	*/
797
798	/*! \fn template <typename InputIterator> uint qHashRangeCommutative(InputIterator first, InputIterator last, uint seed = 0)
799	\relates QHash
800	\since 5.5
801
802	Returns the hash value for the range [\a{first},\a{last}), using \a seed
803	to seed the calculation, by successively applying qHash() to each
804	element and combining the hash values into a single one.
805
806	The return value of this function does not depend on the order of
807	elements in the range. That means that
808
809	\snippet code/src_corelib_tools_qhash.cpp 30
810
811	and
812	\snippet code/src_corelib_tools_qhash.cpp 31
813
814	hash to the \b{same} values. If order matters, for example, for vectors
815	and arrays, use qHashRange() instead. If you are hashing raw
816	memory, use qHashBits().
817
818	Use this function only to implement qHash() for your own custom
819	types. For example, here's how you could implement a qHash() overload for
820	std::unordered_set<int>:
821
822	\snippet code/src_corelib_tools_qhash.cpp qhashrangecommutative
823
824	It bears repeating that the implementation of
825	qHashRangeCommutative() - like the qHash() overloads offered by Qt
826	- may change at any time. You \b{must not} rely on the fact that
827	qHashRangeCommutative() will give the same results (for the same
828	inputs) across different Qt versions, even if qHash() for the
829	element type would.
830
831	\sa qHashBits(), qHashRange()
832	*/
833
834	/*! \fn uint qHashBits(const void *p, size_t len, uint seed = 0)
835	\relates QHash
836	\since 5.4
837
838	Returns the hash value for the memory block of size \a len pointed
839	to by \a p, using \a seed to seed the calculation.
840
841	Use this function only to implement qHash() for your own custom
842	types. For example, here's how you could implement a qHash() overload for
843	std::vector<int>:
844
845	\snippet code/src_corelib_tools_qhash.cpp qhashbits
846
847	This takes advantage of the fact that std::vector lays out its data
848	contiguously. If that is not the case, or the contained type has
849	padding, you should use qHashRange() instead.
850
851	It bears repeating that the implementation of qHashBits() - like
852	the qHash() overloads offered by Qt - may change at any time. You
853	\b{must not} rely on the fact that qHashBits() will give the same
854	results (for the same inputs) across different Qt versions.
855
856	\sa qHashRange(), qHashRangeCommutative()
857	*/
858
859	/*! \fn uint qHash(char key, uint seed = 0)
860	\relates QHash
861	\since 5.0
862
863	Returns the hash value for the \a key, using \a seed to seed the calculation.
864	*/
865
866	/*! \fn uint qHash(uchar key, uint seed = 0)
867	\relates QHash
868	\since 5.0
869
870	Returns the hash value for the \a key, using \a seed to seed the calculation.
871	*/
872
873	/*! \fn uint qHash(signed char key, uint seed = 0)
874	\relates QHash
875	\since 5.0
876
877	Returns the hash value for the \a key, using \a seed to seed the calculation.
878	*/
879
880	/*! \fn uint qHash(ushort key, uint seed = 0)
881	\relates QHash
882	\since 5.0
883
884	Returns the hash value for the \a key, using \a seed to seed the calculation.
885	*/
886
887	/*! \fn uint qHash(short key, uint seed = 0)
888	\relates QHash
889	\since 5.0
890
891	Returns the hash value for the \a key, using \a seed to seed the calculation.
892	*/
893
894	/*! \fn uint qHash(uint key, uint seed = 0)
895	\relates QHash
896	\since 5.0
897
898	Returns the hash value for the \a key, using \a seed to seed the calculation.
899	*/
900
901	/*! \fn uint qHash(int key, uint seed = 0)
902	\relates QHash
903	\since 5.0
904
905	Returns the hash value for the \a key, using \a seed to seed the calculation.
906	*/
907
908	/*! \fn uint qHash(ulong key, uint seed = 0)
909	\relates QHash
910	\since 5.0
911
912	Returns the hash value for the \a key, using \a seed to seed the calculation.
913	*/
914
915	/*! \fn uint qHash(long key, uint seed = 0)
916	\relates QHash
917	\since 5.0
918
919	Returns the hash value for the \a key, using \a seed to seed the calculation.
920	*/
921
922	/*! \fn uint qHash(quint64 key, uint seed = 0)
923	\relates QHash
924	\since 5.0
925
926	Returns the hash value for the \a key, using \a seed to seed the calculation.
927	*/
928
929	/*! \fn uint qHash(qint64 key, uint seed = 0)
930	\relates QHash
931	\since 5.0
932
933	Returns the hash value for the \a key, using \a seed to seed the calculation.
934	*/
935
936	/*! \relates QHash
937	\since 5.3
938
939	Returns the hash value for the \a key, using \a seed to seed the calculation.
940	*/
941	uint qHash(float key, uint seed) noexcept
942	{
943	return key != 0.0f ? hash(p: reinterpret_cast<const uchar *>(&key), len: sizeof(key), seed) : seed ;
944	}
945
946	/*! \relates QHash
947	\since 5.3
948
949	Returns the hash value for the \a key, using \a seed to seed the calculation.
950	*/
951	uint qHash(double key, uint seed) noexcept
952	{
953	return key != 0.0 ? hash(p: reinterpret_cast<const uchar *>(&key), len: sizeof(key), seed) : seed ;
954	}
955
956	#if !defined(Q_OS_DARWIN) || defined(Q_CLANG_QDOC)
957	/*! \relates QHash
958	\since 5.3
959
960	Returns the hash value for the \a key, using \a seed to seed the calculation.
961	*/
962	uint qHash(long double key, uint seed) noexcept
963	{
964	return key != 0.0L ? hash(p: reinterpret_cast<const uchar *>(&key), len: sizeof(key), seed) : seed ;
965	}
966	#endif
967
968	/*! \fn uint qHash(const QChar key, uint seed = 0)
969	\relates QHash
970	\since 5.0
971
972	Returns the hash value for the \a key, using \a seed to seed the calculation.
973	*/
974
975	/*! \fn uint qHash(const QByteArray &key, uint seed = 0)
976	\relates QHash
977	\since 5.0
978
979	Returns the hash value for the \a key, using \a seed to seed the calculation.
980	*/
981
982	/*! \fn uint qHash(const QBitArray &key, uint seed = 0)
983	\relates QHash
984	\since 5.0
985
986	Returns the hash value for the \a key, using \a seed to seed the calculation.
987	*/
988
989	/*! \fn uint qHash(const QString &key, uint seed = 0)
990	\relates QHash
991	\since 5.0
992
993	Returns the hash value for the \a key, using \a seed to seed the calculation.
994	*/
995
996	/*! \fn uint qHash(const QStringRef &key, uint seed = 0)
997	\relates QHash
998	\since 5.0
999
1000	Returns the hash value for the \a key, using \a seed to seed the calculation.
1001	*/
1002
1003	/*! \fn uint qHash(QStringView key, uint seed = 0)
1004	\relates QStringView
1005	\since 5.10
1006
1007	Returns the hash value for the \a key, using \a seed to seed the calculation.
1008	*/
1009
1010	/*! \fn uint qHash(QLatin1String key, uint seed = 0)
1011	\relates QHash
1012	\since 5.0
1013
1014	Returns the hash value for the \a key, using \a seed to seed the calculation.
1015	*/
1016
1017	/*! \fn template <class T> uint qHash(const T *key, uint seed = 0)
1018	\relates QHash
1019	\since 5.0
1020
1021	Returns the hash value for the \a key, using \a seed to seed the calculation.
1022	*/
1023
1024	/*!
1025	\class QHash
1026	\inmodule QtCore
1027	\brief The QHash class is a template class that provides a hash-table-based dictionary.
1028
1029	\ingroup tools
1030	\ingroup shared
1031
1032	\reentrant
1033
1034	QHash\<Key, T\> is one of Qt's generic \l{container classes}. It
1035	stores (key, value) pairs and provides very fast lookup of the
1036	value associated with a key.
1037
1038	QHash provides very similar functionality to QMap. The
1039	differences are:
1040
1041	\list
1042	\li QHash provides faster lookups than QMap. (See \l{Algorithmic
1043	Complexity} for details.)
1044	\li When iterating over a QMap, the items are always sorted by
1045	key. With QHash, the items are arbitrarily ordered.
1046	\li The key type of a QMap must provide operator<(). The key
1047	type of a QHash must provide operator==() and a global
1048	hash function called qHash() (see \l{qHash}).
1049	\endlist
1050
1051	Here's an example QHash with QString keys and \c int values:
1052	\snippet code/src_corelib_tools_qhash.cpp 0
1053
1054	To insert a (key, value) pair into the hash, you can use operator[]():
1055
1056	\snippet code/src_corelib_tools_qhash.cpp 1
1057
1058	This inserts the following three (key, value) pairs into the
1059	QHash: ("one", 1), ("three", 3), and ("seven", 7). Another way to
1060	insert items into the hash is to use insert():
1061
1062	\snippet code/src_corelib_tools_qhash.cpp 2
1063
1064	To look up a value, use operator[]() or value():
1065
1066	\snippet code/src_corelib_tools_qhash.cpp 3
1067
1068	If there is no item with the specified key in the hash, these
1069	functions return a \l{default-constructed value}.
1070
1071	If you want to check whether the hash contains a particular key,
1072	use contains():
1073
1074	\snippet code/src_corelib_tools_qhash.cpp 4
1075
1076	There is also a value() overload that uses its second argument as
1077	a default value if there is no item with the specified key:
1078
1079	\snippet code/src_corelib_tools_qhash.cpp 5
1080
1081	In general, we recommend that you use contains() and value()
1082	rather than operator[]() for looking up a key in a hash. The
1083	reason is that operator[]() silently inserts an item into the
1084	hash if no item exists with the same key (unless the hash is
1085	const). For example, the following code snippet will create 1000
1086	items in memory:
1087
1088	\snippet code/src_corelib_tools_qhash.cpp 6
1089
1090	To avoid this problem, replace \c hash[i] with \c hash.value(i)
1091	in the code above.
1092
1093	Internally, QHash uses a hash table to perform lookups. This
1094	hash table automatically grows and shrinks to
1095	provide fast lookups without wasting too much memory. You can
1096	still control the size of the hash table by calling reserve() if
1097	you already know approximately how many items the QHash will
1098	contain, but this isn't necessary to obtain good performance. You
1099	can also call capacity() to retrieve the hash table's size.
1100
1101	If you want to navigate through all the (key, value) pairs stored
1102	in a QHash, you can use an iterator. QHash provides both
1103	\l{Java-style iterators} (QHashIterator and QMutableHashIterator)
1104	and \l{STL-style iterators} (QHash::const_iterator and
1105	QHash::iterator). Here's how to iterate over a QHash<QString,
1106	int> using a Java-style iterator:
1107
1108	\snippet code/src_corelib_tools_qhash.cpp 7
1109
1110	Here's the same code, but using an STL-style iterator:
1111
1112	\snippet code/src_corelib_tools_qhash.cpp 8
1113
1114	QHash is unordered, so an iterator's sequence cannot be assumed
1115	to be predictable. If ordering by key is required, use a QMap.
1116
1117	Normally, a QHash allows only one value per key. If you call
1118	insert() with a key that already exists in the QHash, the
1119	previous value is erased. For example:
1120
1121	\snippet code/src_corelib_tools_qhash.cpp 9
1122
1123	If you only need to extract the values from a hash (not the keys),
1124	you can also use \l{foreach}:
1125
1126	\snippet code/src_corelib_tools_qhash.cpp 12
1127
1128	Items can be removed from the hash in several ways. One way is to
1129	call remove(); this will remove any item with the given key.
1130	Another way is to use QMutableHashIterator::remove(). In addition,
1131	you can clear the entire hash using clear().
1132
1133	QHash's key and value data types must be \l{assignable data
1134	types}. You cannot, for example, store a QWidget as a value;
1135	instead, store a QWidget *.
1136
1137	\target qHash
1138	\section2 The qHash() hashing function
1139
1140	A QHash's key type has additional requirements other than being an
1141	assignable data type: it must provide operator==(), and there must also be
1142	a qHash() function in the type's namespace that returns a hash value for an
1143	argument of the key's type.
1144
1145	The qHash() function computes a numeric value based on a key. It
1146	can use any algorithm imaginable, as long as it always returns
1147	the same value if given the same argument. In other words, if
1148	\c{e1 == e2}, then \c{qHash(e1) == qHash(e2)} must hold as well.
1149	However, to obtain good performance, the qHash() function should
1150	attempt to return different hash values for different keys to the
1151	largest extent possible.
1152
1153	For a key type \c{K}, the qHash function must have one of these signatures:
1154
1155	\snippet code/src_corelib_tools_qhash.cpp 32
1156
1157	The two-arguments overloads take an unsigned integer that should be used to
1158	seed the calculation of the hash function. This seed is provided by QHash
1159	in order to prevent a family of \l{algorithmic complexity attacks}. If both
1160	a one-argument and a two-arguments overload are defined for a key type,
1161	the latter is used by QHash (note that you can simply define a
1162	two-arguments version, and use a default value for the seed parameter).
1163
1164	Here's a partial list of the C++ and Qt types that can serve as keys in a
1165	QHash: any integer type (char, unsigned long, etc.), any pointer type,
1166	QChar, QString, and QByteArray. For all of these, the \c <QHash> header
1167	defines a qHash() function that computes an adequate hash value. Many other
1168	Qt classes also declare a qHash overload for their type; please refer to
1169	the documentation of each class.
1170
1171	If you want to use other types as the key, make sure that you provide
1172	operator==() and a qHash() implementation.
1173
1174	Example:
1175	\snippet code/src_corelib_tools_qhash.cpp 13
1176
1177	In the example above, we've relied on Qt's global qHash(const
1178	QString &, uint) to give us a hash value for the employee's name, and
1179	XOR'ed this with the day they were born to help produce unique
1180	hashes for people with the same name.
1181
1182	Note that the implementation of the qHash() overloads offered by Qt
1183	may change at any time. You \b{must not} rely on the fact that qHash()
1184	will give the same results (for the same inputs) across different Qt
1185	versions.
1186
1187	\section2 Algorithmic complexity attacks
1188
1189	All hash tables are vulnerable to a particular class of denial of service
1190	attacks, in which the attacker carefully pre-computes a set of different
1191	keys that are going to be hashed in the same bucket of a hash table (or
1192	even have the very same hash value). The attack aims at getting the
1193	worst-case algorithmic behavior (O(n) instead of amortized O(1), see
1194	\l{Algorithmic Complexity} for the details) when the data is fed into the
1195	table.
1196
1197	In order to avoid this worst-case behavior, the calculation of the hash
1198	value done by qHash() can be salted by a random seed, that nullifies the
1199	attack's extent. This seed is automatically generated by QHash once per
1200	process, and then passed by QHash as the second argument of the
1201	two-arguments overload of the qHash() function.
1202
1203	This randomization of QHash is enabled by default. Even though programs
1204	should never depend on a particular QHash ordering, there may be situations
1205	where you temporarily need deterministic behavior, for example for debugging or
1206	regression testing. To disable the randomization, define the environment
1207	variable \c QT_HASH_SEED to have the value 0. Alternatively, you can call
1208	the qSetGlobalQHashSeed() function with the value 0.
1209
1210	\sa QHashIterator, QMutableHashIterator, QMap, QSet
1211	*/
1212
1213	/*! \fn template <class Key, class T> QHash<Key, T>::QHash()
1214
1215	Constructs an empty hash.
1216
1217	\sa clear()
1218	*/
1219
1220	/*!
1221	\fn template <class Key, class T> QHash<Key, T>::QHash(QHash &&other)
1222
1223	Move-constructs a QHash instance, making it point at the same
1224	object that \a other was pointing to.
1225
1226	\since 5.2
1227	*/
1228
1229	/*! \fn template <class Key, class T> QHash<Key, T>::QHash(std::initializer_list<std::pair<Key,T> > list)
1230	\since 5.1
1231
1232	Constructs a hash with a copy of each of the elements in the
1233	initializer list \a list.
1234
1235	This function is only available if the program is being
1236	compiled in C++11 mode.
1237	*/
1238
1239	/*! \fn template <class Key, class T> template <class InputIterator> QHash<Key, T>::QHash(InputIterator begin, InputIterator end)
1240	\since 5.14
1241
1242	Constructs a hash with a copy of each of the elements in the iterator range
1243	[\a begin, \a end). Either the elements iterated by the range must be
1244	objects with \c{first} and \c{second} data members (like \c{QPair},
1245	\c{std::pair}, etc.) convertible to \c Key and to \c T respectively; or the
1246	iterators must have \c{key()} and \c{value()} member functions, returning a
1247	key convertible to \c Key and a value convertible to \c T respectively.
1248	*/
1249
1250	/*! \fn template <class Key, class T> QHash<Key, T>::QHash(const QHash &other)
1251
1252	Constructs a copy of \a other.
1253
1254	This operation occurs in \l{constant time}, because QHash is
1255	\l{implicitly shared}. This makes returning a QHash from a
1256	function very fast. If a shared instance is modified, it will be
1257	copied (copy-on-write), and this takes \l{linear time}.
1258
1259	\sa operator=()
1260	*/
1261
1262	/*! \fn template <class Key, class T> QHash<Key, T>::~QHash()
1263
1264	Destroys the hash. References to the values in the hash and all
1265	iterators of this hash become invalid.
1266	*/
1267
1268	/*! \fn template <class Key, class T> QHash &QHash<Key, T>::operator=(const QHash &other)
1269
1270	Assigns \a other to this hash and returns a reference to this hash.
1271	*/
1272
1273	/*!
1274	\fn template <class Key, class T> QHash &QHash<Key, T>::operator=(QHash &&other)
1275
1276	Move-assigns \a other to this QHash instance.
1277
1278	\since 5.2
1279	*/
1280
1281	/*! \fn template <class Key, class T> void QHash<Key, T>::swap(QHash &other)
1282	\since 4.8
1283
1284	Swaps hash \a other with this hash. This operation is very
1285	fast and never fails.
1286	*/
1287
1288	/*! \fn template <class Key, class T> void QMultiHash<Key, T>::swap(QMultiHash &other)
1289	\since 4.8
1290
1291	Swaps hash \a other with this hash. This operation is very
1292	fast and never fails.
1293	*/
1294
1295	/*! \fn template <class Key, class T> bool QHash<Key, T>::operator==(const QHash &other) const
1296
1297	Returns \c true if \a other is equal to this hash; otherwise returns
1298	false.
1299
1300	Two hashes are considered equal if they contain the same (key,
1301	value) pairs.
1302
1303	This function requires the value type to implement \c operator==().
1304
1305	\sa operator!=()
1306	*/
1307
1308	/*! \fn template <class Key, class T> bool QHash<Key, T>::operator!=(const QHash &other) const
1309
1310	Returns \c true if \a other is not equal to this hash; otherwise
1311	returns \c false.
1312
1313	Two hashes are considered equal if they contain the same (key,
1314	value) pairs.
1315
1316	This function requires the value type to implement \c operator==().
1317
1318	\sa operator==()
1319	*/
1320
1321	/*! \fn template <class Key, class T> int QHash<Key, T>::size() const
1322
1323	Returns the number of items in the hash.
1324
1325	\sa isEmpty(), count()
1326	*/
1327
1328	/*! \fn template <class Key, class T> bool QHash<Key, T>::isEmpty() const
1329
1330	Returns \c true if the hash contains no items; otherwise returns
1331	false.
1332
1333	\sa size()
1334	*/
1335
1336	/*! \fn template <class Key, class T> int QHash<Key, T>::capacity() const
1337
1338	Returns the number of buckets in the QHash's internal hash table.
1339
1340	The sole purpose of this function is to provide a means of fine
1341	tuning QHash's memory usage. In general, you will rarely ever
1342	need to call this function. If you want to know how many items are
1343	in the hash, call size().
1344
1345	\sa reserve(), squeeze()
1346	*/
1347
1348	/*! \fn template <class Key, class T> void QHash<Key, T>::reserve(int size)
1349
1350	Ensures that the QHash's internal hash table consists of at least
1351	\a size buckets.
1352
1353	This function is useful for code that needs to build a huge hash
1354	and wants to avoid repeated reallocation. For example:
1355
1356	\snippet code/src_corelib_tools_qhash.cpp 14
1357
1358	Ideally, \a size should be slightly more than the maximum number
1359	of items expected in the hash. \a size doesn't have to be prime,
1360	because QHash will use a prime number internally anyway. If \a size
1361	is an underestimate, the worst that will happen is that the QHash
1362	will be a bit slower.
1363
1364	In general, you will rarely ever need to call this function.
1365	QHash's internal hash table automatically shrinks or grows to
1366	provide good performance without wasting too much memory.
1367
1368	\sa squeeze(), capacity()
1369	*/
1370
1371	/*! \fn template <class Key, class T> void QHash<Key, T>::squeeze()
1372
1373	Reduces the size of the QHash's internal hash table to save
1374	memory.
1375
1376	The sole purpose of this function is to provide a means of fine
1377	tuning QHash's memory usage. In general, you will rarely ever
1378	need to call this function.
1379
1380	\sa reserve(), capacity()
1381	*/
1382
1383	/*! \fn template <class Key, class T> void QHash<Key, T>::detach()
1384
1385	\internal
1386
1387	Detaches this hash from any other hashes with which it may share
1388	data.
1389
1390	\sa isDetached()
1391	*/
1392
1393	/*! \fn template <class Key, class T> bool QHash<Key, T>::isDetached() const
1394
1395	\internal
1396
1397	Returns \c true if the hash's internal data isn't shared with any
1398	other hash object; otherwise returns \c false.
1399
1400	\sa detach()
1401	*/
1402
1403	/*! \fn template <class Key, class T> void QHash<Key, T>::setSharable(bool sharable)
1404
1405	\internal
1406	*/
1407
1408	/*! \fn template <class Key, class T> bool QHash<Key, T>::isSharedWith(const QHash &other) const
1409
1410	\internal
1411	*/
1412
1413	/*! \fn template <class Key, class T> void QHash<Key, T>::clear()
1414
1415	Removes all items from the hash.
1416
1417	\sa remove()
1418	*/
1419
1420	/*! \fn template <class Key, class T> int QHash<Key, T>::remove(const Key &key)
1421
1422	Removes all the items that have the \a key from the hash.
1423	Returns the number of items removed which is 1 if the key exists in the hash,
1424	and 0 otherwise.
1425
1426	\sa clear(), take(), QMultiHash::remove()
1427	*/
1428
1429	/*! \fn template <class Key, class T> T QHash<Key, T>::take(const Key &key)
1430
1431	Removes the item with the \a key from the hash and returns
1432	the value associated with it.
1433
1434	If the item does not exist in the hash, the function simply
1435	returns a \l{default-constructed value}. If there are multiple
1436	items for \a key in the hash, only the most recently inserted one
1437	is removed.
1438
1439	If you don't use the return value, remove() is more efficient.
1440
1441	\sa remove()
1442	*/
1443
1444	/*! \fn template <class Key, class T> bool QHash<Key, T>::contains(const Key &key) const
1445
1446	Returns \c true if the hash contains an item with the \a key;
1447	otherwise returns \c false.
1448
1449	\sa count(), QMultiHash::contains()
1450	*/
1451
1452	/*! \fn template <class Key, class T> const T QHash<Key, T>::value(const Key &key) const
1453
1454	Returns the value associated with the \a key.
1455
1456	If the hash contains no item with the \a key, the function
1457	returns a \l{default-constructed value}. If there are multiple
1458	items for the \a key in the hash, the value of the most recently
1459	inserted one is returned.
1460
1461	\sa key(), values(), contains(), operator[]()
1462	*/
1463
1464	/*! \fn template <class Key, class T> const T QHash<Key, T>::value(const Key &key, const T &defaultValue) const
1465	\overload
1466
1467	If the hash contains no item with the given \a key, the function returns
1468	\a defaultValue.
1469	*/
1470
1471	/*! \fn template <class Key, class T> T &QHash<Key, T>::operator[](const Key &key)
1472
1473	Returns the value associated with the \a key as a modifiable
1474	reference.
1475
1476	If the hash contains no item with the \a key, the function inserts
1477	a \l{default-constructed value} into the hash with the \a key, and
1478	returns a reference to it. If the hash contains multiple items
1479	with the \a key, this function returns a reference to the most
1480	recently inserted value.
1481
1482	\sa insert(), value()
1483	*/
1484
1485	/*! \fn template <class Key, class T> const T QHash<Key, T>::operator[](const Key &key) const
1486
1487	\overload
1488
1489	Same as value().
1490	*/
1491
1492	/*! \fn template <class Key, class T> QList<Key> QHash<Key, T>::uniqueKeys() const
1493	\since 4.2
1494	\obsolete Use QMultiHash for storing multiple values with the same key.
1495
1496	Returns a list containing all the keys in the map. Keys that occur multiple
1497	times in the map (because items were inserted with insertMulti(), or
1498	unite() was used) occur only once in the returned list.
1499
1500	\sa QMultiHash::uniqueKeys()
1501	*/
1502
1503	/*! \fn template <class Key, class T> QList<Key> QHash<Key, T>::keys() const
1504
1505	Returns a list containing all the keys in the hash, in an
1506	arbitrary order. Keys that occur multiple times in the hash
1507	(because the method is operating on a QMultiHash) also occur
1508	multiple times in the list.
1509
1510	The order is guaranteed to be the same as that used by values().
1511
1512	\sa QMultiMap::uniqueKeys(), values(), key()
1513	*/
1514
1515	/*! \fn template <class Key, class T> QList<Key> QHash<Key, T>::keys(const T &value) const
1516
1517	\overload
1518
1519	Returns a list containing all the keys associated with value \a
1520	value, in an arbitrary order.
1521
1522	This function can be slow (\l{linear time}), because QHash's
1523	internal data structure is optimized for fast lookup by key, not
1524	by value.
1525	*/
1526
1527	/*! \fn template <class Key, class T> QList<T> QHash<Key, T>::values() const
1528
1529	Returns a list containing all the values in the hash, in an
1530	arbitrary order. If a key is associated with multiple values, all of
1531	its values will be in the list, and not just the most recently
1532	inserted one.
1533
1534	The order is guaranteed to be the same as that used by keys().
1535
1536	\sa keys(), value()
1537	*/
1538
1539	/*! \fn template <class Key, class T> QList<T> QHash<Key, T>::values(const Key &key) const
1540	\overload
1541	\obsolete Use QMultiHash for storing multiple values with the same key.
1542
1543	Returns a list of all the values associated with the \a key,
1544	from the most recently inserted to the least recently inserted.
1545
1546	\sa count(), insertMulti()
1547	*/
1548
1549	/*! \fn template <class Key, class T> Key QHash<Key, T>::key(const T &value) const
1550
1551	Returns the first key mapped to \a value.
1552
1553	If the hash contains no item with the \a value, the function
1554	returns a \l{default-constructed value}{default-constructed key}.
1555
1556	This function can be slow (\l{linear time}), because QHash's
1557	internal data structure is optimized for fast lookup by key, not
1558	by value.
1559
1560	\sa value(), keys()
1561	*/
1562
1563	/*!
1564	\fn template <class Key, class T> Key QHash<Key, T>::key(const T &value, const Key &defaultKey) const
1565	\since 4.3
1566	\overload
1567
1568	Returns the first key mapped to \a value, or \a defaultKey if the
1569	hash contains no item mapped to \a value.
1570
1571	This function can be slow (\l{linear time}), because QHash's
1572	internal data structure is optimized for fast lookup by key, not
1573	by value.
1574	*/
1575
1576	/*! \fn template <class Key, class T> int QHash<Key, T>::count(const Key &key) const
1577
1578	Returns the number of items associated with the \a key.
1579
1580	\sa contains(), insertMulti()
1581	*/
1582
1583	/*! \fn template <class Key, class T> int QHash<Key, T>::count() const
1584
1585	\overload
1586
1587	Same as size().
1588	*/
1589
1590	/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::begin()
1591
1592	Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first item in
1593	the hash.
1594
1595	\sa constBegin(), end()
1596	*/
1597
1598	/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::begin() const
1599
1600	\overload
1601	*/
1602
1603	/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::cbegin() const
1604	\since 5.0
1605
1606	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item
1607	in the hash.
1608
1609	\sa begin(), cend()
1610	*/
1611
1612	/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::constBegin() const
1613
1614	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item
1615	in the hash.
1616
1617	\sa begin(), constEnd()
1618	*/
1619
1620	/*! \fn template <class Key, class T> QHash<Key, T>::key_iterator QHash<Key, T>::keyBegin() const
1621	\since 5.6
1622
1623	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first key
1624	in the hash.
1625
1626	\sa keyEnd()
1627	*/
1628
1629	/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::end()
1630
1631	Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary item
1632	after the last item in the hash.
1633
1634	\sa begin(), constEnd()
1635	*/
1636
1637	/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::end() const
1638
1639	\overload
1640	*/
1641
1642	/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::constEnd() const
1643
1644	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
1645	item after the last item in the hash.
1646
1647	\sa constBegin(), end()
1648	*/
1649
1650	/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::cend() const
1651	\since 5.0
1652
1653	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
1654	item after the last item in the hash.
1655
1656	\sa cbegin(), end()
1657	*/
1658
1659	/*! \fn template <class Key, class T> QHash<Key, T>::key_iterator QHash<Key, T>::keyEnd() const
1660	\since 5.6
1661
1662	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
1663	item after the last key in the hash.
1664
1665	\sa keyBegin()
1666	*/
1667
1668	/*! \fn template <class Key, class T> QHash<Key, T>::key_value_iterator QHash<Key, T>::keyValueBegin()
1669	\since 5.10
1670
1671	Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first entry
1672	in the hash.
1673
1674	\sa keyValueEnd()
1675	*/
1676
1677	/*! \fn template <class Key, class T> QHash<Key, T>::key_value_iterator QHash<Key, T>::keyValueEnd()
1678	\since 5.10
1679
1680	Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
1681	entry after the last entry in the hash.
1682
1683	\sa keyValueBegin()
1684	*/
1685
1686	/*! \fn template <class Key, class T> QHash<Key, T>::const_key_value_iterator QHash<Key, T>::keyValueBegin() const
1687	\since 5.10
1688
1689	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry
1690	in the hash.
1691
1692	\sa keyValueEnd()
1693	*/
1694
1695	/*! \fn template <class Key, class T> QHash<Key, T>::const_key_value_iterator QHash<Key, T>::constKeyValueBegin() const
1696	\since 5.10
1697
1698	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry
1699	in the hash.
1700
1701	\sa keyValueBegin()
1702	*/
1703
1704	/*! \fn template <class Key, class T> QHash<Key, T>::const_key_value_iterator QHash<Key, T>::keyValueEnd() const
1705	\since 5.10
1706
1707	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
1708	entry after the last entry in the hash.
1709
1710	\sa keyValueBegin()
1711	*/
1712
1713	/*! \fn template <class Key, class T> QHash<Key, T>::const_key_value_iterator QHash<Key, T>::constKeyValueEnd() const
1714	\since 5.10
1715
1716	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
1717	entry after the last entry in the hash.
1718
1719	\sa constKeyValueBegin()
1720	*/
1721
1722	/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::erase(const_iterator pos)
1723	\since 5.7
1724
1725	Removes the (key, value) pair associated with the iterator \a pos
1726	from the hash, and returns an iterator to the next item in the
1727	hash.
1728
1729	Unlike remove() and take(), this function never causes QHash to
1730	rehash its internal data structure. This means that it can safely
1731	be called while iterating, and won't affect the order of items in
1732	the hash. For example:
1733
1734	\snippet code/src_corelib_tools_qhash.cpp 15
1735
1736	\sa remove(), take(), find()
1737	*/
1738
1739	/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::erase(iterator pos)
1740	\overload
1741	*/
1742
1743	/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::find(const Key &key)
1744
1745	Returns an iterator pointing to the item with the \a key in the
1746	hash.
1747
1748	If the hash contains no item with the \a key, the function
1749	returns end().
1750
1751	If the hash contains multiple items with the \a key, this
1752	function returns an iterator that points to the most recently
1753	inserted value. The other values are accessible by incrementing
1754	the iterator. For example, here's some code that iterates over all
1755	the items with the same key:
1756
1757	\snippet code/src_corelib_tools_qhash.cpp 16
1758
1759	\sa value(), values(), QMultiHash::find()
1760	*/
1761
1762	/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::find(const Key &key) const
1763
1764	\overload
1765	*/
1766
1767	/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::constFind(const Key &key) const
1768	\since 4.1
1769
1770	Returns an iterator pointing to the item with the \a key in the
1771	hash.
1772
1773	If the hash contains no item with the \a key, the function
1774	returns constEnd().
1775
1776	\sa find(), QMultiHash::constFind()
1777	*/
1778
1779	/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::insert(const Key &key, const T &value)
1780
1781	Inserts a new item with the \a key and a value of \a value.
1782
1783	If there is already an item with the \a key, that item's value
1784	is replaced with \a value.
1785
1786	If there are multiple items with the \a key, the most
1787	recently inserted item's value is replaced with \a value.
1788	*/
1789
1790	/*! \fn template <class Key, class T> void QHash<Key, T>::insert(const QHash &other)
1791	\since 5.15
1792
1793	Inserts all the items in the \a other hash into this hash.
1794
1795	If a key is common to both hashes, its value will be replaced with the
1796	value stored in \a other.
1797
1798	\note If \a other contains multiple entries with the same key then the
1799	final value of the key is undefined.
1800	*/
1801
1802	/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::insertMulti(const Key &key, const T &value)
1803	\obsolete
1804
1805	Inserts a new item with the \a key and a value of \a value.
1806
1807	If there is already an item with the same key in the hash, this
1808	function will simply create a new one. (This behavior is
1809	different from insert(), which overwrites the value of an
1810	existing item.)
1811
1812	This function is obsolete. Use QMultiHash or QMultiMap instead.
1813
1814	\sa insert(), values()
1815	*/
1816
1817	/*! \fn template <class Key, class T> QHash &QHash<Key, T>::unite(const QHash &other)
1818	\obsolete
1819
1820	Inserts all the items in the \a other hash into this hash. If a
1821	key is common to both hashes, the resulting hash will contain the
1822	key multiple times.
1823	*/
1824
1825	/*! \fn template <class Key, class T> bool QHash<Key, T>::empty() const
1826
1827	This function is provided for STL compatibility. It is equivalent
1828	to isEmpty(), returning true if the hash is empty; otherwise
1829	returns \c false.
1830	*/
1831
1832	/*! \fn template <class Key, class T> QPair<iterator, iterator> QHash<Key, T>::equal_range(const Key &key)
1833	\since 5.7
1834
1835	Returns a pair of iterators delimiting the range of values \c{[first, second)}, that
1836	are stored under \a key. If the range is empty then both iterators will be equal to end().
1837	*/
1838
1839	/*!
1840	\fn template <class Key, class T> QPair<const_iterator, const_iterator> QHash<Key, T>::equal_range(const Key &key) const
1841	\overload
1842	\since 5.7
1843	*/
1844
1845	/*! \typedef QHash::ConstIterator
1846
1847	Qt-style synonym for QHash::const_iterator.
1848	*/
1849
1850	/*! \typedef QHash::Iterator
1851
1852	Qt-style synonym for QHash::iterator.
1853	*/
1854
1855	/*! \typedef QHash::difference_type
1856
1857	Typedef for ptrdiff_t. Provided for STL compatibility.
1858	*/
1859
1860	/*! \typedef QHash::key_type
1861
1862	Typedef for Key. Provided for STL compatibility.
1863	*/
1864
1865	/*! \typedef QHash::mapped_type
1866
1867	Typedef for T. Provided for STL compatibility.
1868	*/
1869
1870	/*! \typedef QHash::size_type
1871
1872	Typedef for int. Provided for STL compatibility.
1873	*/
1874
1875	/*! \typedef QHash::iterator::difference_type
1876	\internal
1877	*/
1878
1879	/*! \typedef QHash::iterator::iterator_category
1880	\internal
1881	*/
1882
1883	/*! \typedef QHash::iterator::pointer
1884	\internal
1885	*/
1886
1887	/*! \typedef QHash::iterator::reference
1888	\internal
1889	*/
1890
1891	/*! \typedef QHash::iterator::value_type
1892	\internal
1893	*/
1894
1895	/*! \typedef QHash::const_iterator::difference_type
1896	\internal
1897	*/
1898
1899	/*! \typedef QHash::const_iterator::iterator_category
1900	\internal
1901	*/
1902
1903	/*! \typedef QHash::const_iterator::pointer
1904	\internal
1905	*/
1906
1907	/*! \typedef QHash::const_iterator::reference
1908	\internal
1909	*/
1910
1911	/*! \typedef QHash::const_iterator::value_type
1912	\internal
1913	*/
1914
1915	/*! \typedef QHash::key_iterator::difference_type
1916	\internal
1917	*/
1918
1919	/*! \typedef QHash::key_iterator::iterator_category
1920	\internal
1921	*/
1922
1923	/*! \typedef QHash::key_iterator::pointer
1924	\internal
1925	*/
1926
1927	/*! \typedef QHash::key_iterator::reference
1928	\internal
1929	*/
1930
1931	/*! \typedef QHash::key_iterator::value_type
1932	\internal
1933	*/
1934
1935	/*! \class QHash::iterator
1936	\inmodule QtCore
1937	\brief The QHash::iterator class provides an STL-style non-const iterator for QHash and QMultiHash.
1938
1939	QHash features both \l{STL-style iterators} and \l{Java-style
1940	iterators}. The STL-style iterators are more low-level and more
1941	cumbersome to use; on the other hand, they are slightly faster
1942	and, for developers who already know STL, have the advantage of
1943	familiarity.
1944
1945	QHash\<Key, T\>::iterator allows you to iterate over a QHash (or
1946	QMultiHash) and to modify the value (but not the key) associated
1947	with a particular key. If you want to iterate over a const QHash,
1948	you should use QHash::const_iterator. It is generally good
1949	practice to use QHash::const_iterator on a non-const QHash as
1950	well, unless you need to change the QHash through the iterator.
1951	Const iterators are slightly faster, and can improve code
1952	readability.
1953
1954	The default QHash::iterator constructor creates an uninitialized
1955	iterator. You must initialize it using a QHash function like
1956	QHash::begin(), QHash::end(), or QHash::find() before you can
1957	start iterating. Here's a typical loop that prints all the (key,
1958	value) pairs stored in a hash:
1959
1960	\snippet code/src_corelib_tools_qhash.cpp 17
1961
1962	Unlike QMap, which orders its items by key, QHash stores its
1963	items in an arbitrary order.
1964
1965	Let's see a few examples of things we can do with a
1966	QHash::iterator that we cannot do with a QHash::const_iterator.
1967	Here's an example that increments every value stored in the QHash
1968	by 2:
1969
1970	\snippet code/src_corelib_tools_qhash.cpp 18
1971
1972	Here's an example that removes all the items whose key is a
1973	string that starts with an underscore character:
1974
1975	\snippet code/src_corelib_tools_qhash.cpp 19
1976
1977	The call to QHash::erase() removes the item pointed to by the
1978	iterator from the hash, and returns an iterator to the next item.
1979	Here's another way of removing an item while iterating:
1980
1981	\snippet code/src_corelib_tools_qhash.cpp 20
1982
1983	It might be tempting to write code like this:
1984
1985	\snippet code/src_corelib_tools_qhash.cpp 21
1986
1987	However, this will potentially crash in \c{++i}, because \c i is
1988	a dangling iterator after the call to erase().
1989
1990	Multiple iterators can be used on the same hash. However, be
1991	aware that any modification performed directly on the QHash has
1992	the potential of dramatically changing the order in which the
1993	items are stored in the hash, as they might cause QHash to rehash
1994	its internal data structure. There is one notable exception:
1995	QHash::erase(). This function can safely be called while
1996	iterating, and won't affect the order of items in the hash. If you
1997	need to keep iterators over a long period of time, we recommend
1998	that you use QMap rather than QHash.
1999
2000	\warning Iterators on implicitly shared containers do not work
2001	exactly like STL-iterators. You should avoid copying a container
2002	while iterators are active on that container. For more information,
2003	read \l{Implicit sharing iterator problem}.
2004
2005	\sa QHash::const_iterator, QHash::key_iterator, QMutableHashIterator
2006	*/
2007
2008	/*! \fn template <class Key, class T> QHash<Key, T>::iterator::iterator()
2009
2010	Constructs an uninitialized iterator.
2011
2012	Functions like key(), value(), and operator++() must not be
2013	called on an uninitialized iterator. Use operator=() to assign a
2014	value to it before using it.
2015
2016	\sa QHash::begin(), QHash::end()
2017	*/
2018
2019	/*! \fn template <class Key, class T> QHash<Key, T>::iterator::iterator(void *node)
2020
2021	\internal
2022	*/
2023
2024	/*! \fn template <class Key, class T> const Key &QHash<Key, T>::iterator::key() const
2025
2026	Returns the current item's key as a const reference.
2027
2028	There is no direct way of changing an item's key through an
2029	iterator, although it can be done by calling QHash::erase()
2030	followed by QHash::insert().
2031
2032	\sa value()
2033	*/
2034
2035	/*! \fn template <class Key, class T> T &QHash<Key, T>::iterator::value() const
2036
2037	Returns a modifiable reference to the current item's value.
2038
2039	You can change the value of an item by using value() on
2040	the left side of an assignment, for example:
2041
2042	\snippet code/src_corelib_tools_qhash.cpp 22
2043
2044	\sa key(), operator*()
2045	*/
2046
2047	/*! \fn template <class Key, class T> T &QHash<Key, T>::iterator::operator*() const
2048
2049	Returns a modifiable reference to the current item's value.
2050
2051	Same as value().
2052
2053	\sa key()
2054	*/
2055
2056	/*! \fn template <class Key, class T> T *QHash<Key, T>::iterator::operator->() const
2057
2058	Returns a pointer to the current item's value.
2059
2060	\sa value()
2061	*/
2062
2063	/*!
2064	\fn template <class Key, class T> bool QHash<Key, T>::iterator::operator==(const iterator &other) const
2065	\fn template <class Key, class T> bool QHash<Key, T>::iterator::operator==(const const_iterator &other) const
2066
2067	Returns \c true if \a other points to the same item as this
2068	iterator; otherwise returns \c false.
2069
2070	\sa operator!=()
2071	*/
2072
2073	/*!
2074	\fn template <class Key, class T> bool QHash<Key, T>::iterator::operator!=(const iterator &other) const
2075	\fn template <class Key, class T> bool QHash<Key, T>::iterator::operator!=(const const_iterator &other) const
2076
2077	Returns \c true if \a other points to a different item than this
2078	iterator; otherwise returns \c false.
2079
2080	\sa operator==()
2081	*/
2082
2083	/*!
2084	\fn template <class Key, class T> QHash<Key, T>::iterator &QHash<Key, T>::iterator::operator++()
2085
2086	The prefix ++ operator (\c{++i}) advances the iterator to the
2087	next item in the hash and returns an iterator to the new current
2088	item.
2089
2090	Calling this function on QHash::end() leads to undefined results.
2091
2092	\sa operator--()
2093	*/
2094
2095	/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::iterator::operator++(int)
2096
2097	\overload
2098
2099	The postfix ++ operator (\c{i++}) advances the iterator to the
2100	next item in the hash and returns an iterator to the previously
2101	current item.
2102	*/
2103
2104	/*!
2105	\fn template <class Key, class T> QHash<Key, T>::iterator &QHash<Key, T>::iterator::operator--()
2106	\obsolete This operator is deprecated in order to align with std::unordered_map functionality.
2107
2108	The prefix -- operator (\c{--i}) makes the preceding item
2109	current and returns an iterator pointing to the new current item.
2110
2111	Calling this function on QHash::begin() leads to undefined
2112	results.
2113
2114	\sa operator++()
2115	*/
2116
2117	/*!
2118	\fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::iterator::operator--(int)
2119	\obsolete This operator is deprecated in order to align with std::unordered_map functionality.
2120
2121	\overload
2122
2123	The postfix -- operator (\c{i--}) makes the preceding item
2124	current and returns an iterator pointing to the previously
2125	current item.
2126	*/
2127
2128	/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::iterator::operator+(int j) const
2129	\obsolete This operator is deprecated in order to align with std::unordered_map functionality.
2130
2131	Returns an iterator to the item at \a j positions forward from
2132	this iterator. (If \a j is negative, the iterator goes backward.)
2133
2134	This operation can be slow for large \a j values.
2135
2136	\sa operator-()
2137
2138	*/
2139
2140	/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::iterator::operator-(int j) const
2141	\obsolete This operator is deprecated in order to align with std::unordered_map functionality.
2142
2143	Returns an iterator to the item at \a j positions backward from
2144	this iterator. (If \a j is negative, the iterator goes forward.)
2145
2146	This operation can be slow for large \a j values.
2147
2148	\sa operator+()
2149	*/
2150
2151	/*! \fn template <class Key, class T> QHash<Key, T>::iterator &QHash<Key, T>::iterator::operator+=(int j)
2152	\obsolete This operator is deprecated in order to align with std::unordered_map functionality.
2153
2154	Advances the iterator by \a j items. (If \a j is negative, the
2155	iterator goes backward.)
2156
2157	\sa operator-=(), operator+()
2158	*/
2159
2160	/*! \fn template <class Key, class T> QHash<Key, T>::iterator &QHash<Key, T>::iterator::operator-=(int j)
2161	\obsolete This operator is deprecated in order to align with std::unordered_map functionality.
2162
2163	Makes the iterator go back by \a j items. (If \a j is negative,
2164	the iterator goes forward.)
2165
2166	\sa operator+=(), operator-()
2167	*/
2168
2169	/*! \class QHash::const_iterator
2170	\inmodule QtCore
2171	\brief The QHash::const_iterator class provides an STL-style const iterator for QHash and QMultiHash.
2172
2173	QHash features both \l{STL-style iterators} and \l{Java-style
2174	iterators}. The STL-style iterators are more low-level and more
2175	cumbersome to use; on the other hand, they are slightly faster
2176	and, for developers who already know STL, have the advantage of
2177	familiarity.
2178
2179	QHash\<Key, T\>::const_iterator allows you to iterate over a
2180	QHash (or a QMultiHash). If you want to modify the QHash as you
2181	iterate over it, you must use QHash::iterator instead. It is
2182	generally good practice to use QHash::const_iterator on a
2183	non-const QHash as well, unless you need to change the QHash
2184	through the iterator. Const iterators are slightly faster, and
2185	can improve code readability.
2186
2187	The default QHash::const_iterator constructor creates an
2188	uninitialized iterator. You must initialize it using a QHash
2189	function like QHash::constBegin(), QHash::constEnd(), or
2190	QHash::find() before you can start iterating. Here's a typical
2191	loop that prints all the (key, value) pairs stored in a hash:
2192
2193	\snippet code/src_corelib_tools_qhash.cpp 23
2194
2195	Unlike QMap, which orders its items by key, QHash stores its
2196	items in an arbitrary order. The only guarantee is that items that
2197	share the same key (because they were inserted using
2198	a QMultiHash) will appear consecutively, from the most
2199	recently to the least recently inserted value.
2200
2201	Multiple iterators can be used on the same hash. However, be aware
2202	that any modification performed directly on the QHash has the
2203	potential of dramatically changing the order in which the items
2204	are stored in the hash, as they might cause QHash to rehash its
2205	internal data structure. If you need to keep iterators over a long
2206	period of time, we recommend that you use QMap rather than QHash.
2207
2208	\warning Iterators on implicitly shared containers do not work
2209	exactly like STL-iterators. You should avoid copying a container
2210	while iterators are active on that container. For more information,
2211	read \l{Implicit sharing iterator problem}.
2212
2213	\sa QHash::iterator, QHashIterator
2214	*/
2215
2216	/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator::const_iterator()
2217
2218	Constructs an uninitialized iterator.
2219
2220	Functions like key(), value(), and operator++() must not be
2221	called on an uninitialized iterator. Use operator=() to assign a
2222	value to it before using it.
2223
2224	\sa QHash::constBegin(), QHash::constEnd()
2225	*/
2226
2227	/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator::const_iterator(void *node)
2228
2229	\internal
2230	*/
2231
2232	/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator::const_iterator(const iterator &other)
2233
2234	Constructs a copy of \a other.
2235	*/
2236
2237	/*! \fn template <class Key, class T> const Key &QHash<Key, T>::const_iterator::key() const
2238
2239	Returns the current item's key.
2240
2241	\sa value()
2242	*/
2243
2244	/*! \fn template <class Key, class T> const T &QHash<Key, T>::const_iterator::value() const
2245
2246	Returns the current item's value.
2247
2248	\sa key(), operator*()
2249	*/
2250
2251	/*! \fn template <class Key, class T> const T &QHash<Key, T>::const_iterator::operator*() const
2252
2253	Returns the current item's value.
2254
2255	Same as value().
2256
2257	\sa key()
2258	*/
2259
2260	/*! \fn template <class Key, class T> const T *QHash<Key, T>::const_iterator::operator->() const
2261
2262	Returns a pointer to the current item's value.
2263
2264	\sa value()
2265	*/
2266
2267	/*! \fn template <class Key, class T> bool QHash<Key, T>::const_iterator::operator==(const const_iterator &other) const
2268
2269	Returns \c true if \a other points to the same item as this
2270	iterator; otherwise returns \c false.
2271
2272	\sa operator!=()
2273	*/
2274
2275	/*! \fn template <class Key, class T> bool QHash<Key, T>::const_iterator::operator!=(const const_iterator &other) const
2276
2277	Returns \c true if \a other points to a different item than this
2278	iterator; otherwise returns \c false.
2279
2280	\sa operator==()
2281	*/
2282
2283	/*!
2284	\fn template <class Key, class T> QHash<Key, T>::const_iterator &QHash<Key, T>::const_iterator::operator++()
2285
2286	The prefix ++ operator (\c{++i}) advances the iterator to the
2287	next item in the hash and returns an iterator to the new current
2288	item.
2289
2290	Calling this function on QHash::end() leads to undefined results.
2291
2292	\sa operator--()
2293	*/
2294
2295	/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::const_iterator::operator++(int)
2296
2297	\overload
2298
2299	The postfix ++ operator (\c{i++}) advances the iterator to the
2300	next item in the hash and returns an iterator to the previously
2301	current item.
2302	*/
2303
2304	/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator &QHash<Key, T>::const_iterator::operator--()
2305	\obsolete This operator is deprecated in order to align with std::unordered_map functionality.
2306
2307	The prefix -- operator (\c{--i}) makes the preceding item
2308	current and returns an iterator pointing to the new current item.
2309
2310	Calling this function on QHash::begin() leads to undefined
2311	results.
2312
2313	\sa operator++()
2314	*/
2315
2316	/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::const_iterator::operator--(int)
2317	\obsolete This operator is deprecated in order to align with std::unordered_map functionality.
2318
2319	\overload
2320
2321	The postfix -- operator (\c{i--}) makes the preceding item
2322	current and returns an iterator pointing to the previously
2323	current item.
2324	*/
2325
2326	/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::const_iterator::operator+(int j) const
2327	\obsolete This operator is deprecated in order to align with std::unordered_map functionality.
2328
2329	Returns an iterator to the item at \a j positions forward from
2330	this iterator. (If \a j is negative, the iterator goes backward.)
2331
2332	This operation can be slow for large \a j values.
2333
2334	\sa operator-()
2335	*/
2336
2337	/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::const_iterator::operator-(int j) const
2338	\obsolete This operator is deprecated in order to align with std::unordered_map functionality.
2339
2340	Returns an iterator to the item at \a j positions backward from
2341	this iterator. (If \a j is negative, the iterator goes forward.)
2342
2343	This operation can be slow for large \a j values.
2344
2345	\sa operator+()
2346	*/
2347
2348	/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator &QHash<Key, T>::const_iterator::operator+=(int j)
2349	\obsolete This operator is deprecated in order to align with std::unordered_map functionality.
2350
2351	Advances the iterator by \a j items. (If \a j is negative, the
2352	iterator goes backward.)
2353
2354	This operation can be slow for large \a j values.
2355
2356	\sa operator-=(), operator+()
2357	*/
2358
2359	/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator &QHash<Key, T>::const_iterator::operator-=(int j)
2360	\obsolete This operator is deprecated in order to align with std::unordered_map functionality.
2361
2362	Makes the iterator go back by \a j items. (If \a j is negative,
2363	the iterator goes forward.)
2364
2365	This operation can be slow for large \a j values.
2366
2367	\sa operator+=(), operator-()
2368	*/
2369
2370	/*! \class QHash::key_iterator
2371	\inmodule QtCore
2372	\since 5.6
2373	\brief The QHash::key_iterator class provides an STL-style const iterator for QHash and QMultiHash keys.
2374
2375	QHash::key_iterator is essentially the same as QHash::const_iterator
2376	with the difference that operator*() and operator->() return a key
2377	instead of a value.
2378
2379	For most uses QHash::iterator and QHash::const_iterator should be used,
2380	you can easily access the key by calling QHash::iterator::key():
2381
2382	\snippet code/src_corelib_tools_qhash.cpp 27
2383
2384	However, to have interoperability between QHash's keys and STL-style
2385	algorithms we need an iterator that dereferences to a key instead
2386	of a value. With QHash::key_iterator we can apply an algorithm to a
2387	range of keys without having to call QHash::keys(), which is inefficient
2388	as it costs one QHash iteration and memory allocation to create a temporary
2389	QList.
2390
2391	\snippet code/src_corelib_tools_qhash.cpp 28
2392
2393	QHash::key_iterator is const, it's not possible to modify the key.
2394
2395	The default QHash::key_iterator constructor creates an uninitialized
2396	iterator. You must initialize it using a QHash function like
2397	QHash::keyBegin() or QHash::keyEnd().
2398
2399	\warning Iterators on implicitly shared containers do not work
2400	exactly like STL-iterators. You should avoid copying a container
2401	while iterators are active on that container. For more information,
2402	read \l{Implicit sharing iterator problem}.
2403
2404	\sa QHash::const_iterator, QHash::iterator
2405	*/
2406
2407	/*! \fn template <class Key, class T> const T &QHash<Key, T>::key_iterator::operator*() const
2408
2409	Returns the current item's key.
2410	*/
2411
2412	/*! \fn template <class Key, class T> const T *QHash<Key, T>::key_iterator::operator->() const
2413
2414	Returns a pointer to the current item's key.
2415	*/
2416
2417	/*! \fn template <class Key, class T> bool QHash<Key, T>::key_iterator::operator==(key_iterator other) const
2418
2419	Returns \c true if \a other points to the same item as this
2420	iterator; otherwise returns \c false.
2421
2422	\sa operator!=()
2423	*/
2424
2425	/*! \fn template <class Key, class T> bool QHash<Key, T>::key_iterator::operator!=(key_iterator other) const
2426
2427	Returns \c true if \a other points to a different item than this
2428	iterator; otherwise returns \c false.
2429
2430	\sa operator==()
2431	*/
2432
2433	/*!
2434	\fn template <class Key, class T> QHash<Key, T>::key_iterator &QHash<Key, T>::key_iterator::operator++()
2435
2436	The prefix ++ operator (\c{++i}) advances the iterator to the
2437	next item in the hash and returns an iterator to the new current
2438	item.
2439
2440	Calling this function on QHash::keyEnd() leads to undefined results.
2441
2442	\sa operator--()
2443	*/
2444
2445	/*! \fn template <class Key, class T> QHash<Key, T>::key_iterator QHash<Key, T>::key_iterator::operator++(int)
2446
2447	\overload
2448
2449	The postfix ++ operator (\c{i++}) advances the iterator to the
2450	next item in the hash and returns an iterator to the previous
2451	item.
2452	*/
2453
2454	/*! \fn template <class Key, class T> QHash<Key, T>::key_iterator &QHash<Key, T>::key_iterator::operator--()
2455	\obsolete This operator is deprecated in order to align with std::unordered_map functionality.
2456
2457	The prefix -- operator (\c{--i}) makes the preceding item
2458	current and returns an iterator pointing to the new current item.
2459
2460	Calling this function on QHash::keyBegin() leads to undefined
2461	results.
2462
2463	\sa operator++()
2464	*/
2465
2466	/*! \fn template <class Key, class T> QHash<Key, T>::key_iterator QHash<Key, T>::key_iterator::operator--(int)
2467	\obsolete This operator is deprecated in order to align with std::unordered_map functionality.
2468
2469	\overload
2470
2471	The postfix -- operator (\c{i--}) makes the preceding item
2472	current and returns an iterator pointing to the previous
2473	item.
2474	*/
2475
2476	/*! \fn template <class Key, class T> const_iterator QHash<Key, T>::key_iterator::base() const
2477	Returns the underlying const_iterator this key_iterator is based on.
2478	*/
2479
2480	/*! \typedef QHash::const_key_value_iterator
2481	\inmodule QtCore
2482	\since 5.10
2483	\brief The QMap::const_key_value_iterator typedef provides an STL-style const iterator for QHash and QMultiHash.
2484
2485	QHash::const_key_value_iterator is essentially the same as QHash::const_iterator
2486	with the difference that operator*() returns a key/value pair instead of a
2487	value.
2488
2489	\sa QKeyValueIterator
2490	*/
2491
2492	/*! \typedef QHash::key_value_iterator
2493	\inmodule QtCore
2494	\since 5.10
2495	\brief The QMap::key_value_iterator typedef provides an STL-style iterator for QHash and QMultiHash.
2496
2497	QHash::key_value_iterator is essentially the same as QHash::iterator
2498	with the difference that operator*() returns a key/value pair instead of a
2499	value.
2500
2501	\sa QKeyValueIterator
2502	*/
2503
2504	/*! \fn template <class Key, class T> QDataStream &operator<<(QDataStream &out, const QHash<Key, T>& hash)
2505	\relates QHash
2506
2507	Writes the hash \a hash to stream \a out.
2508
2509	This function requires the key and value types to implement \c
2510	operator<<().
2511
2512	\sa {Serializing Qt Data Types}
2513	*/
2514
2515	/*! \fn template <class Key, class T> QDataStream &operator>>(QDataStream &in, QHash<Key, T> &hash)
2516	\relates QHash
2517
2518	Reads a hash from stream \a in into \a hash.
2519
2520	This function requires the key and value types to implement \c
2521	operator>>().
2522
2523	\sa {Serializing Qt Data Types}
2524	*/
2525
2526	/*! \class QMultiHash
2527	\inmodule QtCore
2528	\brief The QMultiHash class is a convenience QHash subclass that provides multi-valued hashes.
2529
2530	\ingroup tools
2531	\ingroup shared
2532
2533	\reentrant
2534
2535	QMultiHash\<Key, T\> is one of Qt's generic \l{container classes}.
2536	It inherits QHash and extends it with a few convenience functions
2537	that make it more suitable than QHash for storing multi-valued
2538	hashes. A multi-valued hash is a hash that allows multiple values
2539	with the same key.
2540
2541	Because QMultiHash inherits QHash, all of QHash's functionality also
2542	applies to QMultiHash. For example, you can use isEmpty() to test
2543	whether the hash is empty, and you can traverse a QMultiHash using
2544	QHash's iterator classes (for example, QHashIterator). But opposed to
2545	QHash, it provides an insert() function will allow the insertion of
2546	multiple items with the same key. The replace() function corresponds to
2547	QHash::insert(). It also provides convenient operator+() and
2548	operator+=().
2549
2550	Unlike QMultiMap, QMultiHash does not provide and ordering of the
2551	inserted items. The only guarantee is that items that
2552	share the same key will appear consecutively, from the most
2553	recently to the least recently inserted value.
2554
2555	Example:
2556	\snippet code/src_corelib_tools_qhash.cpp 24
2557
2558	Unlike QHash, QMultiHash provides no operator[]. Use value() or
2559	replace() if you want to access the most recently inserted item
2560	with a certain key.
2561
2562	If you want to retrieve all the values for a single key, you can
2563	use values(const Key &key), which returns a QList<T>:
2564
2565	\snippet code/src_corelib_tools_qhash.cpp 25
2566
2567	The items that share the same key are available from most
2568	recently to least recently inserted.
2569
2570	A more efficient approach is to call find() to get
2571	the STL-style iterator for the first item with a key and iterate from
2572	there:
2573
2574	\snippet code/src_corelib_tools_qhash.cpp 26
2575
2576	QMultiHash's key and value data types must be \l{assignable data
2577	types}. You cannot, for example, store a QWidget as a value;
2578	instead, store a QWidget *. In addition, QMultiHash's key type
2579	must provide operator==(), and there must also be a qHash() function
2580	in the type's namespace that returns a hash value for an argument of the
2581	key's type. See the QHash documentation for details.
2582
2583	\sa QHash, QHashIterator, QMutableHashIterator, QMultiMap
2584	*/
2585
2586	/*! \fn template <class Key, class T> QMultiHash<Key, T>::QMultiHash()
2587
2588	Constructs an empty hash.
2589	*/
2590
2591	/*! \fn template <class Key, class T> QMultiHash<Key, T>::QMultiHash(std::initializer_list<std::pair<Key,T> > list)
2592	\since 5.1
2593
2594	Constructs a multi-hash with a copy of each of the elements in the
2595	initializer list \a list.
2596
2597	This function is only available if the program is being
2598	compiled in C++11 mode.
2599	*/
2600
2601	/*! \fn template <class Key, class T> QMultiHash<Key, T>::QMultiHash(const QHash<Key, T> &other)
2602
2603	Constructs a copy of \a other (which can be a QHash or a
2604	QMultiHash).
2605
2606	\sa operator=()
2607	*/
2608
2609	/*! \fn template <class Key, class T> template <class InputIterator> QMultiHash<Key, T>::QMultiHash(InputIterator begin, InputIterator end)
2610	\since 5.14
2611
2612	Constructs a multi-hash with a copy of each of the elements in the iterator range
2613	[\a begin, \a end). Either the elements iterated by the range must be
2614	objects with \c{first} and \c{second} data members (like \c{QPair},
2615	\c{std::pair}, etc.) convertible to \c Key and to \c T respectively; or the
2616	iterators must have \c{key()} and \c{value()} member functions, returning a
2617	key convertible to \c Key and a value convertible to \c T respectively.
2618	*/
2619
2620	/*! \fn template <class Key, class T> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::replace(const Key &key, const T &value)
2621
2622	Inserts a new item with the \a key and a value of \a value.
2623
2624	If there is already an item with the \a key, that item's value
2625	is replaced with \a value.
2626
2627	If there are multiple items with the \a key, the most
2628	recently inserted item's value is replaced with \a value.
2629
2630	\sa insert()
2631	*/
2632
2633	/*! \fn template <class Key, class T> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::insert(const Key &key, const T &value)
2634
2635	Inserts a new item with the \a key and a value of \a value.
2636
2637	If there is already an item with the same key in the hash, this
2638	function will simply create a new one. (This behavior is
2639	different from replace(), which overwrites the value of an
2640	existing item.)
2641
2642	\sa replace()
2643	*/
2644
2645	/*! \fn template <class Key, class T> QMultiHash &QMultiHash<Key, T>::unite(const QMultiHash &other)
2646	\since 5.13
2647
2648	Inserts all the items in the \a other hash into this hash
2649	and returns a reference to this hash.
2650
2651	\sa insert()
2652	*/
2653
2654	/*! \fn template <class Key, class T> QList<Key> QMultiHash<Key, T>::uniqueKeys() const
2655	\since 5.13
2656
2657	Returns a list containing all the keys in the map. Keys that occur multiple
2658	times in the map occur only once in the returned list.
2659
2660	\sa keys(), values()
2661	*/
2662
2663	/*! \fn template <class Key, class T> QList<T> QMultiHash<Key, T>::values(const Key &key) const
2664	\overload
2665
2666	Returns a list of all the values associated with the \a key,
2667	from the most recently inserted to the least recently inserted.
2668
2669	\sa count(), insert()
2670	*/
2671
2672	/*! \fn template <class Key, class T> QMultiHash &QMultiHash<Key, T>::operator+=(const QMultiHash &other)
2673
2674	Inserts all the items in the \a other hash into this hash
2675	and returns a reference to this hash.
2676
2677	\sa unite(), insert()
2678	*/
2679
2680	/*! \fn template <class Key, class T> QMultiHash QMultiHash<Key, T>::operator+(const QMultiHash &other) const
2681
2682	Returns a hash that contains all the items in this hash in
2683	addition to all the items in \a other. If a key is common to both
2684	hashes, the resulting hash will contain the key multiple times.
2685
2686	\sa operator+=()
2687	*/
2688
2689	/*!
2690	\fn template <class Key, class T> bool QMultiHash<Key, T>::contains(const Key &key, const T &value) const
2691	\since 4.3
2692
2693	Returns \c true if the hash contains an item with the \a key and
2694	\a value; otherwise returns \c false.
2695
2696	\sa QHash::contains()
2697	*/
2698
2699	/*!
2700	\fn template <class Key, class T> int QMultiHash<Key, T>::remove(const Key &key, const T &value)
2701	\since 4.3
2702
2703	Removes all the items that have the \a key and the value \a
2704	value from the hash. Returns the number of items removed.
2705
2706	\sa QHash::remove()
2707	*/
2708
2709	/*!
2710	\fn template <class Key, class T> int QMultiHash<Key, T>::count(const Key &key, const T &value) const
2711	\since 4.3
2712
2713	Returns the number of items with the \a key and \a value.
2714
2715	\sa QHash::count()
2716	*/
2717
2718	/*!
2719	\fn template <class Key, class T> typename QHash<Key, T>::iterator QMultiHash<Key, T>::find(const Key &key, const T &value)
2720	\since 4.3
2721
2722	Returns an iterator pointing to the item with the \a key and \a value.
2723	If the hash contains no such item, the function returns end().
2724
2725	If the hash contains multiple items with the \a key and \a value, the
2726	iterator returned points to the most recently inserted item.
2727
2728	\sa QHash::find()
2729	*/
2730
2731	/*!
2732	\fn template <class Key, class T> typename QHash<Key, T>::const_iterator QMultiHash<Key, T>::find(const Key &key, const T &value) const
2733	\since 4.3
2734	\overload
2735	*/
2736
2737	/*!
2738	\fn template <class Key, class T> typename QHash<Key, T>::const_iterator QMultiHash<Key, T>::constFind(const Key &key, const T &value) const
2739	\since 4.3
2740
2741	Returns an iterator pointing to the item with the \a key and the
2742	\a value in the hash.
2743
2744	If the hash contains no such item, the function returns
2745	constEnd().
2746
2747	\sa QHash::constFind()
2748	*/
2749
2750	/*!
2751	\fn template <class Key, class T> uint qHash(const QHash<Key, T> &key, uint seed = 0)
2752	\since 5.8
2753	\relates QHash
2754
2755	Returns the hash value for the \a key, using \a seed to seed the calculation.
2756
2757	Type \c T must be supported by qHash().
2758	*/
2759
2760	/*!
2761	\fn template <class Key, class T> uint qHash(const QMultiHash<Key, T> &key, uint seed = 0)
2762	\since 5.8
2763	\relates QMultiHash
2764
2765	Returns the hash value for the \a key, using \a seed to seed the calculation.
2766
2767	Type \c T must be supported by qHash().
2768	*/
2769
2770	QT_END_NAMESPACE
2771