1	// Copyright (C) 2020 The Qt Company Ltd.
2	// Copyright (C) 2021 Intel Corporation.
3	// Copyright (C) 2012 Giuseppe D'Angelo <dangelog@gmail.com>.
4	// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
5
6	// for rand_s, _CRT_RAND_S must be #defined before #including stdlib.h.
7	// put it at the beginning so some indirect inclusion doesn't break it
8	#ifndef _CRT_RAND_S
9	#define _CRT_RAND_S
10	#endif
11	#include <stdlib.h>
12	#include <stdint.h>
13
14	#include "qhash.h"
15
16	#ifdef truncate
17	#undef truncate
18	#endif
19
20	#include <qbitarray.h>
21	#include <qstring.h>
22	#include <qglobal.h>
23	#include <qbytearray.h>
24	#include <qdatetime.h>
25	#include <qbasicatomic.h>
26	#include <qendian.h>
27	#include <private/qrandom_p.h>
28	#include <private/qsimd_p.h>
29
30	#ifndef QT_BOOTSTRAPPED
31	#include <qcoreapplication.h>
32	#include <qrandom.h>
33	#include <private/qlocale_tools_p.h>
34	#endif // QT_BOOTSTRAPPED
35
36	// Implementation of SipHash algorithm
37	#include "../../3rdparty/siphash/siphash.cpp"
38
39	#include <array>
40	#include <limits.h>
41
42	#if defined(QT_NO_DEBUG) && !defined(NDEBUG)
43	# define NDEBUG
44	#endif
45	#include <assert.h>
46
47	#ifdef Q_CC_GNU
48	# define Q_DECL_HOT_FUNCTION __attribute__((hot))
49	#else
50	# define Q_DECL_HOT_FUNCTION
51	#endif
52
53	QT_BEGIN_NAMESPACE
54
55	void qt_from_latin1(char16_t *dst, const char *str, size_t size) noexcept; // qstring.cpp
56
57	// We assume that pointers and size_t have the same size. If that assumption should fail
58	// on a platform the code selecting the different methods below needs to be fixed.
59	static_assert(sizeof(size_t) == QT_POINTER_SIZE, "size_t and pointers have different size.");
60
61	namespace {
62	struct HashSeedStorage
63	{
64	static constexpr int SeedCount = 2;
65	QBasicAtomicInteger<quintptr> seeds[SeedCount] = { Q_BASIC_ATOMIC_INITIALIZER(0), Q_BASIC_ATOMIC_INITIALIZER(0) };
66
67	#if !QT_SUPPORTS_INIT_PRIORITY || defined(QT_BOOTSTRAPPED)
68	constexpr HashSeedStorage() = default;
69	#else
70	HashSeedStorage() { initialize(which: 0); }
71	#endif
72
73	enum State {
74	OverriddenByEnvironment = -1,
75	JustInitialized,
76	AlreadyInitialized
77	};
78	struct StateResult {
79	quintptr requestedSeed;
80	State state;
81	};
82
83	StateResult state(int which = -1);
84	Q_DECL_HOT_FUNCTION QHashSeed currentSeed(int which)
85	{
86	return { state(which).requestedSeed };
87	}
88
89	void resetSeed()
90	{
91	#ifndef QT_BOOTSTRAPPED
92	if (state().state < AlreadyInitialized)
93	return;
94
95	// update the public seed
96	QRandomGenerator *generator = QRandomGenerator::system();
97	seeds[0].storeRelaxed(newValue: sizeof(size_t) > sizeof(quint32)
98	? generator->generate64() : generator->generate());
99	#endif
100	}
101
102	void clearSeed()
103	{
104	state();
105	seeds[0].storeRelaxed(newValue: 0); // always write (smaller code)
106	}
107
108	private:
109	Q_NEVER_INLINE Q_DECL_COLD_FUNCTION StateResult initialize(int which) noexcept;
110	};
111
112	[[maybe_unused]] HashSeedStorage::StateResult HashSeedStorage::initialize(int which) noexcept
113	{
114	StateResult result = { .requestedSeed: 0, .state: OverriddenByEnvironment };
115	#ifdef QT_BOOTSTRAPPED
116	Q_UNUSED(which);
117	Q_UNREACHABLE_RETURN(result);
118	#else
119	// can't use qEnvironmentVariableIntValue (reentrancy)
120	const char *seedstr = getenv(name: "QT_HASH_SEED");
121	if (seedstr) {
122	auto r = qstrntoll(nptr: seedstr, size: strlen(s: seedstr), base: 10);
123	if (r.used > 0 && size_t(r.used) == strlen(s: seedstr)) {
124	if (r.result) {
125	// can't use qWarning here (reentrancy)
126	fprintf(stderr, format: "QT_HASH_SEED: forced seed value is not 0; ignored.\n");
127	}
128
129	// we don't have to store to the seed, since it's pre-initialized by
130	// the compiler to zero
131	return result;
132	}
133	}
134
135	// update the full seed
136	auto x = qt_initial_random_value();
137	for (int i = 0; i < SeedCount; ++i) {
138	seeds[i].storeRelaxed(newValue: x.data[i]);
139	if (which == i)
140	result.requestedSeed = x.data[i];
141	}
142	result.state = JustInitialized;
143	return result;
144	#endif
145	}
146
147	inline HashSeedStorage::StateResult HashSeedStorage::state(int which)
148	{
149	constexpr quintptr BadSeed = quintptr(Q_UINT64_C(0x5555'5555'5555'5555));
150	StateResult result = { .requestedSeed: BadSeed, .state: AlreadyInitialized };
151
152	#if defined(QT_BOOTSTRAPPED)
153	result = { 0, OverriddenByEnvironment };
154	#elif !QT_SUPPORTS_INIT_PRIORITY
155	// dynamic initialization
156	static auto once = [&]() {
157	result = initialize(which);
158	return true;
159	}();
160	Q_UNUSED(once);
161	#endif
162
163	if (result.state == AlreadyInitialized && which >= 0)
164	return { .requestedSeed: seeds[which].loadRelaxed(), .state: AlreadyInitialized };
165	return result;
166	}
167	} // unnamed namespace
168
169	/*
170	The QHash seed itself.
171	*/
172	#ifdef Q_DECL_INIT_PRIORITY
173	Q_DECL_INIT_PRIORITY(05)
174	#else
175	Q_CONSTINIT
176	#endif
177	static HashSeedStorage qt_qhash_seed;
178
179	/*
180	* Hashing for memory segments is based on the public domain MurmurHash2 by
181	* Austin Appleby. See http://murmurhash.googlepages.com/
182	*/
183	#if QT_POINTER_SIZE == 4
184	Q_NEVER_INLINE Q_DECL_HOT_FUNCTION
185	static inline uint murmurhash(const void *key, uint len, uint seed) noexcept
186	{
187	// 'm' and 'r' are mixing constants generated offline.
188	// They're not really 'magic', they just happen to work well.
189
190	const unsigned int m = 0x5bd1e995;
191	const int r = 24;
192
193	// Initialize the hash to a 'random' value
194
195	unsigned int h = seed ^ len;
196
197	// Mix 4 bytes at a time into the hash
198
199	const unsigned char *data = reinterpret_cast<const unsigned char *>(key);
200	const unsigned char *end = data + (len & ~3);
201
202	while (data != end) {
203	size_t k;
204	memcpy(&k, data, sizeof(uint));
205
206	k *= m;
207	k ^= k >> r;
208	k *= m;
209
210	h *= m;
211	h ^= k;
212
213	data += 4;
214	}
215
216	// Handle the last few bytes of the input array
217	len &= 3;
218	if (len) {
219	unsigned int k = 0;
220	end += len;
221
222	while (data != end) {
223	k <<= 8;
224	k |= *data;
225	++data;
226	}
227	h ^= k;
228	h *= m;
229	}
230
231	// Do a few final mixes of the hash to ensure the last few
232	// bytes are well-incorporated.
233
234	h ^= h >> 13;
235	h *= m;
236	h ^= h >> 15;
237
238	return h;
239	}
240
241	#else
242	Q_NEVER_INLINE Q_DECL_HOT_FUNCTION
243	static inline uint64_t murmurhash(const void *key, uint64_t len, uint64_t seed) noexcept
244	{
245	const uint64_t m = 0xc6a4a7935bd1e995ULL;
246	const int r = 47;
247
248	uint64_t h = seed ^ (len * m);
249
250	const unsigned char *data = reinterpret_cast<const unsigned char *>(key);
251	const unsigned char *end = data + (len & ~7ul);
252
253	while (data != end) {
254	uint64_t k;
255	memcpy(dest: &k, src: data, n: sizeof(uint64_t));
256
257	k *= m;
258	k ^= k >> r;
259	k *= m;
260
261	h ^= k;
262	h *= m;
263
264	data += 8;
265	}
266
267	len &= 7;
268	if (len) {
269	// handle the last few bytes of input
270	size_t k = 0;
271	end += len;
272
273	while (data != end) {
274	k <<= 8;
275	k |= *data;
276	++data;
277	}
278	h ^= k;
279	h *= m;
280	}
281
282	h ^= h >> r;
283	h *= m;
284	h ^= h >> r;
285
286	return h;
287	}
288
289	#endif
290
291	enum ZeroExtension {
292	None = 0,
293	ByteToWord = 1,
294	};
295
296	template <ZeroExtension = None> static size_t
297	qHashBits_fallback(const uchar *p, size_t size, size_t seed, size_t seed2) noexcept;
298	template <> size_t qHashBits_fallback<None>(const uchar *p, size_t size, size_t seed, size_t seed2) noexcept
299	{
300	if (size <= QT_POINTER_SIZE)
301	return murmurhash(key: p, len: size, seed);
302
303	return siphash(in: reinterpret_cast<const uchar *>(p), inlen: size, seed, seed2);
304	}
305
306	template <> size_t qHashBits_fallback<ByteToWord>(const uchar *data, size_t size, size_t seed, size_t seed2) noexcept
307	{
308	auto quick_from_latin1 = [](char16_t *dest, const uchar *data, size_t size) {
309	// Quick, "inlined" version for very short blocks
310	std::copy_n(first: data, n: size, result: dest);
311	};
312	if (size <= QT_POINTER_SIZE / 2) {
313	std::array<char16_t, QT_POINTER_SIZE / 2> buf;
314	quick_from_latin1(buf.data(), data, size);
315	return murmurhash(key: buf.data(), len: size * 2, seed);
316	}
317
318	constexpr size_t TailSizeMask = sizeof(void *) / 2 - 1;
319	std::array<char16_t, 256> buf;
320	SipHash<> siphash(size * 2, seed, seed2);
321	ptrdiff_t offset = 0;
322	for ( ; offset + buf.size() < size; offset += buf.size()) {
323	qt_from_latin1(dst: buf.data(), str: reinterpret_cast<const char *>(data) + offset, size: buf.size());
324	siphash.addBlock(in: reinterpret_cast<uint8_t *>(buf.data()), inlen: sizeof(buf));
325	}
326	if (size_t n = size - offset; n > TailSizeMask) {
327	n &= ~TailSizeMask;
328	qt_from_latin1(dst: buf.data(), str: reinterpret_cast<const char *>(data) + offset, size: n);
329	siphash.addBlock(in: reinterpret_cast<uint8_t *>(buf.data()), inlen: n * 2);
330	offset += n;
331	}
332
333	quick_from_latin1(buf.data(), data + offset, size - offset);
334	return siphash.finalize(in: reinterpret_cast<uint8_t *>(buf.data()), left: (size - offset) * 2);
335	}
336
337	#if defined(__SANITIZE_ADDRESS__) || defined(__SANITIZE_THREAD__) // GCC
338	# define QHASH_AES_SANITIZER_BUILD
339	#elif __has_feature(address_sanitizer) || __has_feature(thread_sanitizer) // Clang
340	# define QHASH_AES_SANITIZER_BUILD
341	#endif
342
343	// When built with a sanitizer, aeshash() is rightfully reported to have a
344	// heap-buffer-overflow issue. However, we consider it to be safe in this
345	// specific case and overcome the problem by correctly discarding the
346	// out-of-range bits. To allow building the code with sanitizer,
347	// QHASH_AES_SANITIZER_BUILD is used to disable aeshash() usage.
348	#if QT_COMPILER_SUPPORTS_HERE(AES) && QT_COMPILER_SUPPORTS_HERE(SSE4_2) && \
349	!defined(QHASH_AES_SANITIZER_BUILD)
350	# define AESHASH
351	# define QT_FUNCTION_TARGET_STRING_AES_AVX2 "avx2,aes"
352	# define QT_FUNCTION_TARGET_STRING_AES_AVX512 \
353	QT_FUNCTION_TARGET_STRING_ARCH_SKYLAKE_AVX512 "," \
354	QT_FUNCTION_TARGET_STRING_AES
355	# define QT_FUNCTION_TARGET_STRING_VAES_AVX512 \
356	QT_FUNCTION_TARGET_STRING_ARCH_SKYLAKE_AVX512 "," \
357	QT_FUNCTION_TARGET_STRING_VAES
358	# undef QHASH_AES_SANITIZER_BUILD
359	# if QT_POINTER_SIZE == 8
360	# define mm_set1_epz _mm_set1_epi64x
361	# define mm_cvtsz_si128 _mm_cvtsi64_si128
362	# define mm_cvtsi128_sz _mm_cvtsi128_si64
363	# define mm256_set1_epz _mm256_set1_epi64x
364	# else
365	# define mm_set1_epz _mm_set1_epi32
366	# define mm_cvtsz_si128 _mm_cvtsi32_si128
367	# define mm_cvtsi128_sz _mm_cvtsi128_si32
368	# define mm256_set1_epz _mm256_set1_epi32
369	# endif
370
371	namespace {
372	// This is inspired by the algorithm in the Go language. See:
373	// https://github.com/golang/go/blob/01b6cf09fc9f272d9db3d30b4c93982f4911d120/src/runtime/asm_amd64.s#L1105
374	// https://github.com/golang/go/blob/01b6cf09fc9f272d9db3d30b4c93982f4911d120/src/runtime/asm_386.s#L908
375	//
376	// Even though we're using the AESENC instruction from the CPU, this code
377	// is not encryption and this routine makes no claim to be
378	// cryptographically secure. We're simply using the instruction that performs
379	// the scrambling round (step 3 in [1]) because it's just very good at
380	// spreading the bits around.
381	//
382	// Note on Latin-1 hashing (ZX == ByteToWord): for simplicity of the
383	// algorithm, we pass sizes equivalent to the UTF-16 content (ZX == None).
384	// That means we must multiply by 2 on entry, divide by 2 on pointer
385	// advancing, and load half as much data from memory (though we produce
386	// exactly as much data in registers). The compilers appear to optimize
387	// this out.
388	//
389	// [1] https://en.wikipedia.org/wiki/Advanced_Encryption_Standard#High-level_description_of_the_algorithm
390
391	template <ZeroExtension ZX, typename T> static const T *advance(const T *ptr, ptrdiff_t n)
392	{
393	if constexpr (ZX == None)
394	return ptr + n;
395
396	// see note above on ZX == ByteToWord hashing
397	auto p = reinterpret_cast<const uchar *>(ptr);
398	n *= sizeof(T);
399	return reinterpret_cast<const T *>(p + n/2);
400	}
401
402	template <ZeroExtension> static __m128i loadu128(const void *ptr);
403	template <> Q_ALWAYS_INLINE QT_FUNCTION_TARGET(AES) __m128i loadu128<None>(const void *ptr)
404	{
405	return _mm_loadu_si128(p: reinterpret_cast<const __m128i *>(ptr));
406	}
407	template <> Q_ALWAYS_INLINE QT_FUNCTION_TARGET(AES) __m128i loadu128<ByteToWord>(const void *ptr)
408	{
409	// use a MOVQ followed by PMOVZXBW
410	// the compiler usually combines them as a single, loading PMOVZXBW
411	__m128i data = _mm_loadl_epi64(p: static_cast<const __m128i *>(ptr));
412	return _mm_cvtepu8_epi16(V: data);
413	}
414
415	// hash 16 bytes, running 3 scramble rounds of AES on itself (like label "final1")
416	Q_ALWAYS_INLINE static void QT_FUNCTION_TARGET(AES) QT_VECTORCALL
417	hash16bytes(__m128i &state0, __m128i data)
418	{
419	state0 = _mm_xor_si128(a: state0, b: data);
420	state0 = _mm_aesenc_si128(V: state0, R: state0);
421	state0 = _mm_aesenc_si128(V: state0, R: state0);
422	state0 = _mm_aesenc_si128(V: state0, R: state0);
423	}
424
425	// hash twice 16 bytes, running 2 scramble rounds of AES on itself
426	template <ZeroExtension ZX>
427	static void QT_FUNCTION_TARGET(AES) QT_VECTORCALL
428	hash2x16bytes(__m128i &state0, __m128i &state1, const __m128i *src0, const __m128i *src1)
429	{
430	__m128i data0 = loadu128<ZX>(src0);
431	__m128i data1 = loadu128<ZX>(src1);
432	state0 = _mm_xor_si128(a: data0, b: state0);
433	state1 = _mm_xor_si128(a: data1, b: state1);
434	state0 = _mm_aesenc_si128(V: state0, R: state0);
435	state1 = _mm_aesenc_si128(V: state1, R: state1);
436	state0 = _mm_aesenc_si128(V: state0, R: state0);
437	state1 = _mm_aesenc_si128(V: state1, R: state1);
438	}
439
440	struct AESHashSeed
441	{
442	__m128i state0;
443	__m128i mseed2;
444	AESHashSeed(size_t seed, size_t seed2) QT_FUNCTION_TARGET(AES);
445	__m128i state1() const QT_FUNCTION_TARGET(AES);
446	__m256i state0_256() const QT_FUNCTION_TARGET(AES_AVX2)
447	{ return _mm256_set_m128i(hi: state1(), lo: state0); }
448	};
449	} // unnamed namespace
450
451	Q_ALWAYS_INLINE AESHashSeed::AESHashSeed(size_t seed, size_t seed2)
452	{
453	__m128i mseed = mm_cvtsz_si128(a: seed);
454	mseed2 = mm_set1_epz(q: seed2);
455
456	// mseed (epi16) = [ seed, seed >> 16, seed >> 32, seed >> 48, len, 0, 0, 0 ]
457	mseed = _mm_insert_epi16(mseed, short(seed), 4);
458	// mseed (epi16) = [ seed, seed >> 16, seed >> 32, seed >> 48, len, len, len, len ]
459	mseed = _mm_shufflehi_epi16(mseed, 0);
460
461	// merge with the process-global seed
462	__m128i key = _mm_xor_si128(a: mseed, b: mseed2);
463
464	// scramble the key
465	__m128i state0 = _mm_aesenc_si128(V: key, R: key);
466	this->state0 = state0;
467	}
468
469	Q_ALWAYS_INLINE __m128i AESHashSeed::state1() const
470	{
471	{
472	// unlike the Go code, we don't have more per-process seed
473	__m128i state1 = _mm_aesenc_si128(V: state0, R: mseed2);
474	return state1;
475	}
476	}
477
478	template <ZeroExtension ZX>
479	static size_t QT_FUNCTION_TARGET(AES) QT_VECTORCALL
480	aeshash128_16to32(__m128i state0, __m128i state1, const __m128i *src, const __m128i *srcend)
481	{
482	{
483	const __m128i *src2 = advance<ZX>(srcend, -1);
484	if (advance<ZX>(src, 1) < srcend) {
485	// epilogue: between 16 and 31 bytes
486	hash2x16bytes<ZX>(state0, state1, src, src2);
487	} else if (src != srcend) {
488	// epilogue: between 1 and 16 bytes, overlap with the end
489	__m128i data = loadu128<ZX>(src2);
490	hash16bytes(state0, data);
491	}
492
493	// combine results:
494	state0 = _mm_xor_si128(a: state0, b: state1);
495	}
496
497	return mm_cvtsi128_sz(a: state0);
498	}
499
500	// load all 16 bytes and mask off the bytes past the end of the source
501	static const qint8 maskarray[] = {
502	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
503	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
504	};
505
506	// load 16 bytes ending at the data end, then shuffle them to the beginning
507	static const qint8 shufflecontrol[] = {
508	1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
509	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
510	};
511
512	template <ZeroExtension ZX>
513	static size_t QT_FUNCTION_TARGET(AES) QT_VECTORCALL
514	aeshash128_lt16(__m128i state0, const __m128i *src, const __m128i *srcend, size_t len)
515	{
516	if (len) {
517	// We're going to load 16 bytes and mask zero the part we don't care
518	// (the hash of a short string is different from the hash of a longer
519	// including NULLs at the end because the length is in the key)
520	// WARNING: this may produce valgrind warnings, but it's safe
521
522	constexpr quintptr CachelineSize = 64;
523	__m128i data;
524
525	if ((quintptr(src) & (CachelineSize / 2)) == 0) {
526	// lower half of the cacheline:
527	__m128i mask = _mm_loadu_si128(p: reinterpret_cast<const __m128i *>(maskarray + 15 - len));
528	data = loadu128<ZX>(src);
529	data = _mm_and_si128(a: data, b: mask);
530	} else {
531	// upper half of the cacheline:
532	__m128i control = _mm_loadu_si128(p: reinterpret_cast<const __m128i *>(shufflecontrol + 15 - len));
533	data = loadu128<ZX>(advance<ZX>(srcend, -1));
534	data = _mm_shuffle_epi8(a: data, b: control);
535	}
536
537	hash16bytes(state0, data);
538	}
539	return mm_cvtsi128_sz(a: state0);
540	}
541
542	template <ZeroExtension ZX>
543	static size_t QT_FUNCTION_TARGET(AES) QT_VECTORCALL
544	aeshash128_ge32(__m128i state0, __m128i state1, const __m128i *src, const __m128i *srcend)
545	{
546	// main loop: scramble two 16-byte blocks
547	for ( ; advance<ZX>(src, 2) < srcend; src = advance<ZX>(src, 2))
548	hash2x16bytes<ZX>(state0, state1, src, advance<ZX>(src, 1));
549
550	return aeshash128_16to32<ZX>(state0, state1, src, srcend);
551	}
552
553	# if QT_COMPILER_SUPPORTS_HERE(VAES)
554	template <ZeroExtension> static __m256i loadu256(const void *ptr);
555	template <> Q_ALWAYS_INLINE QT_FUNCTION_TARGET(VAES) __m256i loadu256<None>(const void *ptr)
556	{
557	return _mm256_loadu_si256(p: reinterpret_cast<const __m256i *>(ptr));
558	}
559	template <> Q_ALWAYS_INLINE QT_FUNCTION_TARGET(VAES) __m256i loadu256<ByteToWord>(const void *ptr)
560	{
561	// VPMOVZXBW xmm, ymm
562	__m128i data = _mm_loadu_si128(p: reinterpret_cast<const __m128i *>(ptr));
563	return _mm256_cvtepu8_epi16(V: data);
564	}
565
566	template <ZeroExtension ZX>
567	static size_t QT_FUNCTION_TARGET(VAES_AVX512) QT_VECTORCALL
568	aeshash256_lt32_avx256(__m256i state0, const uchar *p, size_t len)
569	{
570	__m128i state0_128 = _mm256_castsi256_si128(a: state0);
571	if (len) {
572	__m256i data;
573	if constexpr (ZX == None) {
574	__mmask32 mask = _bzhi_u32(X: -1, Y: unsigned(len));
575	data = _mm256_maskz_loadu_epi8(U: mask, P: p);
576	} else {
577	__mmask16 mask = _bzhi_u32(X: -1, Y: unsigned(len) / 2);
578	__m128i data0 = _mm_maskz_loadu_epi8(U: mask, P: p);
579	data = _mm256_cvtepu8_epi16(V: data0);
580	}
581	__m128i data0 = _mm256_castsi256_si128(a: data);
582	if (len >= sizeof(__m128i)) {
583	state0 = _mm256_xor_si256(a: state0, b: data);
584	state0 = _mm256_aesenc_epi128(A: state0, B: state0);
585	state0 = _mm256_aesenc_epi128(A: state0, B: state0);
586	// we're XOR'ing the two halves so we skip the third AESENC
587	// state0 = _mm256_aesenc_epi128(state0, state0);
588
589	// XOR the two halves and extract
590	__m128i low = _mm256_extracti128_si256(state0, 0);
591	__m128i high = _mm256_extracti128_si256(state0, 1);
592	state0_128 = _mm_xor_si128(a: low, b: high);
593	} else {
594	hash16bytes(state0&: state0_128, data: data0);
595	}
596	}
597	return mm_cvtsi128_sz(a: state0_128);
598	}
599
600	template <ZeroExtension ZX>
601	static size_t QT_FUNCTION_TARGET(VAES) QT_VECTORCALL
602	aeshash256_ge32(__m256i state0, const __m128i *s, const __m128i *end, size_t len)
603	{
604	static const auto hash32bytes = [](__m256i &state0, __m256i data) QT_FUNCTION_TARGET(VAES) {
605	state0 = _mm256_xor_si256(a: state0, b: data);
606	state0 = _mm256_aesenc_epi128(A: state0, B: state0);
607	state0 = _mm256_aesenc_epi128(A: state0, B: state0);
608	state0 = _mm256_aesenc_epi128(A: state0, B: state0);
609	};
610
611	// hash twice 32 bytes, running 2 scramble rounds of AES on itself
612	const auto hash2x32bytes = [](__m256i &state0, __m256i &state1, const void *src0,
613	const void *src1) QT_FUNCTION_TARGET(VAES) {
614	__m256i data0 = loadu256<ZX>(src0);
615	__m256i data1 = loadu256<ZX>(src1);
616	state0 = _mm256_xor_si256(a: data0, b: state0);
617	state1 = _mm256_xor_si256(a: data1, b: state1);
618	state0 = _mm256_aesenc_epi128(A: state0, B: state0);
619	state1 = _mm256_aesenc_epi128(A: state1, B: state1);
620	state0 = _mm256_aesenc_epi128(A: state0, B: state0);
621	state1 = _mm256_aesenc_epi128(A: state1, B: state1);
622	};
623
624	const __m256i *src = reinterpret_cast<const __m256i *>(s);
625	const __m256i *srcend = reinterpret_cast<const __m256i *>(end);
626
627	__m256i state1 = _mm256_aesenc_epi128(A: state0, mm256_set1_epz(q: len));
628
629	// main loop: scramble two 32-byte blocks
630	for ( ; advance<ZX>(src, 2) < srcend; src = advance<ZX>(src, 2))
631	hash2x32bytes(state0, state1, src, advance<ZX>(src, 1));
632
633	const __m256i *src2 = advance<ZX>(srcend, -1);
634	if (advance<ZX>(src, 1) < srcend) {
635	// epilogue: between 32 and 31 bytes
636	hash2x32bytes(state0, state1, src, src2);
637	} else if (src != srcend) {
638	// epilogue: between 1 and 32 bytes, overlap with the end
639	__m256i data = loadu256<ZX>(src2);
640	hash32bytes(state0, data);
641	}
642
643	// combine results:
644	state0 = _mm256_xor_si256(a: state0, b: state1);
645
646	// XOR the two halves and extract
647	__m128i low = _mm256_extracti128_si256(state0, 0);
648	__m128i high = _mm256_extracti128_si256(state0, 1);
649	return mm_cvtsi128_sz(a: _mm_xor_si128(a: low, b: high));
650	}
651
652	template <ZeroExtension ZX>
653	static size_t QT_FUNCTION_TARGET(VAES)
654	aeshash256(const uchar *p, size_t len, size_t seed, size_t seed2) noexcept
655	{
656	AESHashSeed state(seed, seed2);
657	auto src = reinterpret_cast<const __m128i *>(p);
658	const auto srcend = reinterpret_cast<const __m128i *>(advance<ZX>(p, len));
659
660	if (len < sizeof(__m128i))
661	return aeshash128_lt16<ZX>(state.state0, src, srcend, len);
662
663	if (len <= sizeof(__m256i))
664	return aeshash128_16to32<ZX>(state.state0, state.state1(), src, srcend);
665
666	return aeshash256_ge32<ZX>(state.state0_256(), src, srcend, len);
667	}
668
669	template <ZeroExtension ZX>
670	static size_t QT_FUNCTION_TARGET(VAES_AVX512)
671	aeshash256_avx256(const uchar *p, size_t len, size_t seed, size_t seed2) noexcept
672	{
673	AESHashSeed state(seed, seed2);
674	auto src = reinterpret_cast<const __m128i *>(p);
675	const auto srcend = reinterpret_cast<const __m128i *>(advance<ZX>(p, len));
676
677	if (len <= sizeof(__m256i))
678	return aeshash256_lt32_avx256<ZX>(state.state0_256(), p, len);
679
680	return aeshash256_ge32<ZX>(state.state0_256(), src, srcend, len);
681	}
682	# endif // VAES
683
684	template <ZeroExtension ZX>
685	static size_t QT_FUNCTION_TARGET(AES)
686	aeshash128(const uchar *p, size_t len, size_t seed, size_t seed2) noexcept
687	{
688	AESHashSeed state(seed, seed2);
689	auto src = reinterpret_cast<const __m128i *>(p);
690	const auto srcend = reinterpret_cast<const __m128i *>(advance<ZX>(p, len));
691
692	if (len < sizeof(__m128i))
693	return aeshash128_lt16<ZX>(state.state0, src, srcend, len);
694
695	if (len <= sizeof(__m256i))
696	return aeshash128_16to32<ZX>(state.state0, state.state1(), src, srcend);
697
698	return aeshash128_ge32<ZX>(state.state0, state.state1(), src, srcend);
699	}
700
701	template <ZeroExtension ZX = None>
702	static size_t aeshash(const uchar *p, size_t len, size_t seed, size_t seed2) noexcept
703	{
704	if constexpr (ZX == ByteToWord)
705	len *= 2; // see note above on ZX == ByteToWord hashing
706
707	# if QT_COMPILER_SUPPORTS_HERE(VAES)
708	if (qCpuHasFeature(VAES)) {
709	if (qCpuHasFeature(AVX512VL))
710	return aeshash256_avx256<ZX>(p, len, seed, seed2);
711	return aeshash256<ZX>(p, len, seed, seed2);
712	}
713	# endif
714	return aeshash128<ZX>(p, len, seed, seed2);
715	}
716	#endif // x86 AESNI
717
718	#if defined(Q_PROCESSOR_ARM) && QT_COMPILER_SUPPORTS_HERE(CRYPTO) && !defined(QHASH_AES_SANITIZER_BUILD) && !defined(QT_BOOTSTRAPPED)
719	QT_FUNCTION_TARGET(AES)
720	static size_t aeshash(const uchar *p, size_t len, size_t seed, size_t seed2) noexcept
721	{
722	uint8x16_t key;
723	# if QT_POINTER_SIZE == 8
724	uint64x2_t vseed = vcombine_u64(vcreate_u64(seed), vcreate_u64(seed2));
725	key = vreinterpretq_u8_u64(vseed);
726	# else
727
728	uint32x2_t vseed = vmov_n_u32(seed);
729	vseed = vset_lane_u32(seed2, vseed, 1);
730	key = vreinterpretq_u8_u32(vcombine_u32(vseed, vseed));
731	# endif
732
733	// Compared to x86 AES, ARM splits each round into two instructions
734	// and includes the pre-xor instead of the post-xor.
735	const auto hash16bytes = [](uint8x16_t &state0, uint8x16_t data) QT_FUNCTION_TARGET(AES) {
736	auto state1 = state0;
737	state0 = vaeseq_u8(state0, data);
738	state0 = vaesmcq_u8(state0);
739	auto state2 = state0;
740	state0 = vaeseq_u8(state0, state1);
741	state0 = vaesmcq_u8(state0);
742	auto state3 = state0;
743	state0 = vaeseq_u8(state0, state2);
744	state0 = vaesmcq_u8(state0);
745	state0 = veorq_u8(state0, state3);
746	};
747
748	uint8x16_t state0 = key;
749
750	if (len < 8)
751	goto lt8;
752	if (len < 16)
753	goto lt16;
754	if (len < 32)
755	goto lt32;
756
757	// rounds of 32 bytes
758	{
759	// Make state1 = ~state0:
760	uint8x16_t state1 = veorq_u8(state0, vdupq_n_u8(255));
761
762	// do simplified rounds of 32 bytes: unlike the Go code, we only
763	// scramble twice and we keep 256 bits of state
764	const auto *e = p + len - 31;
765	while (p < e) {
766	uint8x16_t data0 = vld1q_u8(p);
767	uint8x16_t data1 = vld1q_u8(p + 16);
768	auto oldstate0 = state0;
769	auto oldstate1 = state1;
770	state0 = vaeseq_u8(state0, data0);
771	state1 = vaeseq_u8(state1, data1);
772	state0 = vaesmcq_u8(state0);
773	state1 = vaesmcq_u8(state1);
774	auto laststate0 = state0;
775	auto laststate1 = state1;
776	state0 = vaeseq_u8(state0, oldstate0);
777	state1 = vaeseq_u8(state1, oldstate1);
778	state0 = vaesmcq_u8(state0);
779	state1 = vaesmcq_u8(state1);
780	state0 = veorq_u8(state0, laststate0);
781	state1 = veorq_u8(state1, laststate1);
782	p += 32;
783	}
784	state0 = veorq_u8(state0, state1);
785	}
786	len &= 0x1f;
787
788	// do we still have 16 or more bytes?
789	if (len & 0x10) {
790	lt32:
791	uint8x16_t data = vld1q_u8(p);
792	hash16bytes(state0, data);
793	p += 16;
794	}
795	len &= 0xf;
796
797	if (len & 0x08) {
798	lt16:
799	uint8x8_t data8 = vld1_u8(p);
800	uint8x16_t data = vcombine_u8(data8, vdup_n_u8(0));
801	hash16bytes(state0, data);
802	p += 8;
803	}
804	len &= 0x7;
805
806	lt8:
807	if (len) {
808	// load the last chunk of data
809	// We're going to load 8 bytes and mask zero the part we don't care
810	// (the hash of a short string is different from the hash of a longer
811	// including NULLs at the end because the length is in the key)
812	// WARNING: this may produce valgrind warnings, but it's safe
813
814	uint8x8_t data8;
815
816	if (Q_LIKELY(quintptr(p + 8) & 0xff8)) {
817	// same page, we definitely can't fault:
818	// load all 8 bytes and mask off the bytes past the end of the source
819	static const qint8 maskarray[] = {
820	-1, -1, -1, -1, -1, -1, -1,
821	0, 0, 0, 0, 0, 0, 0,
822	};
823	uint8x8_t mask = vld1_u8(reinterpret_cast<const quint8 *>(maskarray) + 7 - len);
824	data8 = vld1_u8(p);
825	data8 = vand_u8(data8, mask);
826	} else {
827	// too close to the end of the page, it could fault:
828	// load 8 bytes ending at the data end, then shuffle them to the beginning
829	static const qint8 shufflecontrol[] = {
830	1, 2, 3, 4, 5, 6, 7,
831	-1, -1, -1, -1, -1, -1, -1,
832	};
833	uint8x8_t control = vld1_u8(reinterpret_cast<const quint8 *>(shufflecontrol) + 7 - len);
834	data8 = vld1_u8(p - 8 + len);
835	data8 = vtbl1_u8(data8, control);
836	}
837	uint8x16_t data = vcombine_u8(data8, vdup_n_u8(0));
838	hash16bytes(state0, data);
839	}
840
841	// extract state0
842	# if QT_POINTER_SIZE == 8
843	return vgetq_lane_u64(vreinterpretq_u64_u8(state0), 0);
844	# else
845	return vgetq_lane_u32(vreinterpretq_u32_u8(state0), 0);
846	# endif
847	}
848	#endif
849
850	size_t qHashBits(const void *p, size_t size, size_t seed) noexcept
851	{
852	#ifdef QT_BOOTSTRAPPED
853	// the seed is always 0 in bootstrapped mode (no seed generation code),
854	// so help the compiler do dead code elimination
855	seed = 0;
856	#endif
857	// mix in the length as a secondary seed. For seed == 0, seed2 must be
858	// size, to match what we used to do prior to Qt 6.2.
859	size_t seed2 = size;
860	if (seed)
861	seed2 = qt_qhash_seed.currentSeed(which: 1);
862
863	auto data = reinterpret_cast<const uchar *>(p);
864	#ifdef AESHASH
865	if (seed && qCpuHasFeature(AES) && qCpuHasFeature(SSE4_2))
866	return aeshash(p: data, len: size, seed, seed2);
867	#elif defined(Q_PROCESSOR_ARM) && QT_COMPILER_SUPPORTS_HERE(CRYPTO) && !defined(QHASH_AES_SANITIZER_BUILD) && !defined(QT_BOOTSTRAPPED)
868	if (seed && qCpuHasFeature(AES))
869	return aeshash(data, size, seed, seed2);
870	#endif
871
872	return qHashBits_fallback<>(p: data, size, seed, seed2);
873	}
874
875	size_t qHash(QByteArrayView key, size_t seed) noexcept
876	{
877	return qHashBits(p: key.constData(), size: size_t(key.size()), seed);
878	}
879
880	size_t qHash(QStringView key, size_t seed) noexcept
881	{
882	return qHashBits(p: key.data(), size: key.size()*sizeof(QChar), seed);
883	}
884
885	#ifndef QT_BOOTSTRAPPED
886	size_t qHash(const QBitArray &bitArray, size_t seed) noexcept
887	{
888	qsizetype m = bitArray.d.size() - 1;
889	size_t result = qHashBits(p: reinterpret_cast<const uchar *>(bitArray.d.constData()), size: size_t(qMax(a: 0, b: m)), seed);
890
891	// deal with the last 0 to 7 bits manually, because we can't trust that
892	// the padding is initialized to 0 in bitArray.d
893	qsizetype n = bitArray.size();
894	if (n & 0x7)
895	result = ((result << 4) + bitArray.d.at(i: m)) & ((1 << n) - 1);
896	return result;
897	}
898	#endif
899
900	size_t qHash(QLatin1StringView key, size_t seed) noexcept
901	{
902	#ifdef QT_BOOTSTRAPPED
903	// the seed is always 0 in bootstrapped mode (no seed generation code),
904	// so help the compiler do dead code elimination
905	seed = 0;
906	#endif
907
908	auto data = reinterpret_cast<const uchar *>(key.data());
909	size_t size = key.size();
910
911	// Mix in the length as a secondary seed.
912	// Multiplied by 2 to match the byte size of the equiavlent UTF-16 string.
913	size_t seed2 = size * 2;
914	if (seed)
915	seed2 = qt_qhash_seed.currentSeed(which: 1);
916
917	#if defined(AESHASH)
918	if (seed && qCpuHasFeature(AES) && qCpuHasFeature(SSE4_2))
919	return aeshash<ByteToWord>(p: data, len: size, seed, seed2);
920	#endif
921	return qHashBits_fallback<ByteToWord>(data, size, seed, seed2);
922	}
923
924	/*!
925	\class QHashSeed
926	\inmodule QtCore
927	\since 6.2
928
929	The QHashSeed class is used to convey the QHash seed. This is used
930	internally by QHash and provides three static member functions to allow
931	users to obtain the hash and to reset it.
932
933	QHash and the qHash() functions implement what is called as "salted hash".
934	The intent is that different applications and different instances of the
935	same application will produce different hashing values for the same input,
936	thus causing the ordering of elements in QHash to be unpredictable by
937	external observers. This improves the applications' resilience against
938	attacks that attempt to force hashing tables into degenerate mode.
939
940	Most applications will not need to deal directly with the hash seed, as
941	QHash will do so when needed. However, applications may wish to use this
942	for their own purposes in the same way as QHash does: as an
943	application-global random value (but see \l QRandomGenerator too). Note
944	that the global hash seed may change during the application's lifetime, if
945	the resetRandomGlobalSeed() function is called. Users of the global hash
946	need to store the value they are using and not rely on getting it again.
947
948	This class also implements functionality to set the hash seed to a
949	deterministic value, which the qHash() functions will take to mean that
950	they should use a fixed hashing function on their data too. This
951	functionality is only meant to be used in debugging applications. This
952	behavior can also be controlled by setting the \c QT_HASH_SEED environment
953	variable to the value zero (any other value is ignored).
954
955	\sa QHash, QRandomGenerator
956	*/
957
958	/*!
959	\fn QHashSeed::QHashSeed(size_t data)
960
961	Constructs a new QHashSeed object using \a data as the seed.
962	*/
963
964	/*!
965	\fn QHashSeed::operator size_t() const
966
967	Converts the returned hash seed into a \c size_t.
968	*/
969
970	/*!
971	\threadsafe
972
973	Returns the current global QHash seed. The value returned by this function
974	will be zero if setDeterministicGlobalSeed() has been called or if the
975	\c{QT_HASH_SEED} environment variable is set to zero.
976	*/
977	QHashSeed QHashSeed::globalSeed() noexcept
978	{
979	return qt_qhash_seed.currentSeed(which: 0);
980	}
981
982	/*!
983	\threadsafe
984
985	Forces the Qt hash seed to a deterministic value (zero) and asks the
986	qHash() functions to use a pre-determined hashing function. This mode is
987	only useful for debugging and should not be used in production code.
988
989	Regular operation can be restored by calling resetRandomGlobalSeed().
990	*/
991	void QHashSeed::setDeterministicGlobalSeed()
992	{
993	qt_qhash_seed.clearSeed();
994	}
995
996	/*!
997	\threadsafe
998
999	Reseeds the Qt hashing seed to a new, random value. Calling this function
1000	is not necessary, but long-running applications may want to do so after a
1001	long period of time in which information about its hash may have been
1002	exposed to potential attackers.
1003
1004	If the environment variable \c QT_HASH_SEED is set to zero, calling this
1005	function will result in a no-op.
1006
1007	Qt never calls this function during the execution of the application, but
1008	unless the \c QT_HASH_SEED variable is set to 0, the hash seed returned by
1009	globalSeed() will be a random value as if this function had been called.
1010	*/
1011	void QHashSeed::resetRandomGlobalSeed()
1012	{
1013	qt_qhash_seed.resetSeed();
1014	}
1015
1016	#if QT_DEPRECATED_SINCE(6,6)
1017	/*! \relates QHash
1018	\since 5.6
1019	\deprecated [6.6] Use QHashSeed::globalSeed() instead.
1020
1021	Returns the current global QHash seed.
1022
1023	The seed is set in any newly created QHash. See \l{qHash} about how this seed
1024	is being used by QHash.
1025
1026	\sa QHashSeed, QHashSeed::globalSeed()
1027	*/
1028	int qGlobalQHashSeed()
1029	{
1030	return int(QHashSeed::globalSeed() & INT_MAX);
1031	}
1032
1033	/*! \relates QHash
1034	\since 5.6
1035	\deprecated [6.6] Use QHashSeed instead.
1036
1037	Sets the global QHash seed to \a newSeed.
1038
1039	Manually setting the global QHash seed value should be done only for testing
1040	and debugging purposes, when deterministic and reproducible behavior on a QHash
1041	is needed. We discourage to do it in production code as it can make your
1042	application susceptible to \l{algorithmic complexity attacks}.
1043
1044	From Qt 5.10 and onwards, the only allowed values are 0 and -1. Passing the
1045	value -1 will reinitialize the global QHash seed to a random value, while
1046	the value of 0 is used to request a stable algorithm for C++ primitive
1047	types types (like \c int) and string types (QString, QByteArray).
1048
1049	The seed is set in any newly created QHash. See \l{qHash} about how this seed
1050	is being used by QHash.
1051
1052	If the environment variable \c QT_HASH_SEED is set, calling this function will
1053	result in a no-op.
1054
1055	\sa QHashSeed::globalSeed(), QHashSeed
1056	*/
1057	void qSetGlobalQHashSeed(int newSeed)
1058	{
1059	if (Q_LIKELY(newSeed == 0 || newSeed == -1)) {
1060	if (newSeed == 0)
1061	QHashSeed::setDeterministicGlobalSeed();
1062	else
1063	QHashSeed::resetRandomGlobalSeed();
1064	} else {
1065	// can't use qWarning here (reentrancy)
1066	fprintf(stderr, format: "qSetGlobalQHashSeed: forced seed value is not 0; ignoring call\n");
1067	}
1068	}
1069	#endif // QT_DEPRECATED_SINCE(6,6)
1070
1071	/*!
1072	\internal
1073
1074	Private copy of the implementation of the Qt 4 qHash algorithm for strings,
1075	(that is, QChar-based arrays, so all QString-like classes),
1076	to be used wherever the result is somehow stored or reused across multiple
1077	Qt versions. The public qHash implementation can change at any time,
1078	therefore one must not rely on the fact that it will always give the same
1079	results.
1080
1081	The qt_hash functions must *never* change their results.
1082
1083	This function can hash discontiguous memory by invoking it on each chunk,
1084	passing the previous's result in the next call's \a chained argument.
1085	*/
1086	uint qt_hash(QStringView key, uint chained) noexcept
1087	{
1088	uint h = chained;
1089
1090	for (auto c: key) {
1091	h = (h << 4) + c.unicode();
1092	h ^= (h & 0xf0000000) >> 23;
1093	}
1094	h &= 0x0fffffff;
1095	return h;
1096	}
1097
1098	/*!
1099	\fn template <typename T1, typename T2> size_t qHash(const std::pair<T1, T2> &key, size_t seed = 0)
1100	\since 5.7
1101	\qhashbuiltinTS{T1}{T2}
1102	*/
1103
1104	/*!
1105	\fn template <typename... T> size_t qHashMulti(size_t seed, const T &...args)
1106	\relates QHash
1107	\since 6.0
1108
1109	Returns the hash value for the \a{args}, using \a seed to seed
1110	the calculation, by successively applying qHash() to each
1111	element and combining the hash values into a single one.
1112
1113	Note that the order of the arguments is significant. If order does
1114	not matter, use qHashMultiCommutative() instead. If you are hashing raw
1115	memory, use qHashBits(); if you are hashing a range, use qHashRange().
1116
1117	This function is provided as a convenience to implement qHash() for
1118	your own custom types. For example, here's how you could implement
1119	a qHash() overload for a class \c{Employee}:
1120
1121	\snippet code/src_corelib_tools_qhash.cpp 13
1122
1123	\sa qHashMultiCommutative, qHashRange
1124	*/
1125
1126	/*!
1127	\fn template <typename... T> size_t qHashMultiCommutative(size_t seed, const T &...args)
1128	\relates QHash
1129	\since 6.0
1130
1131	Returns the hash value for the \a{args}, using \a seed to seed
1132	the calculation, by successively applying qHash() to each
1133	element and combining the hash values into a single one.
1134
1135	The order of the arguments is insignificant. If order does
1136	matter, use qHashMulti() instead, as it may produce better quality
1137	hashing. If you are hashing raw memory, use qHashBits(); if you are
1138	hashing a range, use qHashRange().
1139
1140	This function is provided as a convenience to implement qHash() for
1141	your own custom types.
1142
1143	\sa qHashMulti, qHashRange
1144	*/
1145
1146	/*! \fn template <typename InputIterator> size_t qHashRange(InputIterator first, InputIterator last, size_t seed = 0)
1147	\relates QHash
1148	\since 5.5
1149
1150	Returns the hash value for the range [\a{first},\a{last}), using \a seed
1151	to seed the calculation, by successively applying qHash() to each
1152	element and combining the hash values into a single one.
1153
1154	The return value of this function depends on the order of elements
1155	in the range. That means that
1156
1157	\snippet code/src_corelib_tools_qhash.cpp 30
1158
1159	and
1160	\snippet code/src_corelib_tools_qhash.cpp 31
1161
1162	hash to \b{different} values. If order does not matter, for example for hash
1163	tables, use qHashRangeCommutative() instead. If you are hashing raw
1164	memory, use qHashBits().
1165
1166	Use this function only to implement qHash() for your own custom
1167	types. For example, here's how you could implement a qHash() overload for
1168	std::vector<int>:
1169
1170	\snippet code/src_corelib_tools_qhash.cpp qhashrange
1171
1172	It bears repeating that the implementation of qHashRange() - like
1173	the qHash() overloads offered by Qt - may change at any time. You
1174	\b{must not} rely on the fact that qHashRange() will give the same
1175	results (for the same inputs) across different Qt versions, even
1176	if qHash() for the element type would.
1177
1178	\sa qHashBits(), qHashRangeCommutative()
1179	*/
1180
1181	/*! \fn template <typename InputIterator> size_t qHashRangeCommutative(InputIterator first, InputIterator last, size_t seed = 0)
1182	\relates QHash
1183	\since 5.5
1184
1185	Returns the hash value for the range [\a{first},\a{last}), using \a seed
1186	to seed the calculation, by successively applying qHash() to each
1187	element and combining the hash values into a single one.
1188
1189	The return value of this function does not depend on the order of
1190	elements in the range. That means that
1191
1192	\snippet code/src_corelib_tools_qhash.cpp 30
1193
1194	and
1195	\snippet code/src_corelib_tools_qhash.cpp 31
1196
1197	hash to the \b{same} values. If order matters, for example, for vectors
1198	and arrays, use qHashRange() instead. If you are hashing raw
1199	memory, use qHashBits().
1200
1201	Use this function only to implement qHash() for your own custom
1202	types. For example, here's how you could implement a qHash() overload for
1203	std::unordered_set<int>:
1204
1205	\snippet code/src_corelib_tools_qhash.cpp qhashrangecommutative
1206
1207	It bears repeating that the implementation of
1208	qHashRangeCommutative() - like the qHash() overloads offered by Qt
1209	- may change at any time. You \b{must not} rely on the fact that
1210	qHashRangeCommutative() will give the same results (for the same
1211	inputs) across different Qt versions, even if qHash() for the
1212	element type would.
1213
1214	\sa qHashBits(), qHashRange()
1215	*/
1216
1217	/*! \fn size_t qHashBits(const void *p, size_t len, size_t seed = 0)
1218	\relates QHash
1219	\since 5.4
1220
1221	Returns the hash value for the memory block of size \a len pointed
1222	to by \a p, using \a seed to seed the calculation.
1223
1224	Use this function only to implement qHash() for your own custom
1225	types. For example, here's how you could implement a qHash() overload for
1226	std::vector<int>:
1227
1228	\snippet code/src_corelib_tools_qhash.cpp qhashbits
1229
1230	This takes advantage of the fact that std::vector lays out its data
1231	contiguously. If that is not the case, or the contained type has
1232	padding, you should use qHashRange() instead.
1233
1234	It bears repeating that the implementation of qHashBits() - like
1235	the qHash() overloads offered by Qt - may change at any time. You
1236	\b{must not} rely on the fact that qHashBits() will give the same
1237	results (for the same inputs) across different Qt versions.
1238
1239	\sa qHashRange(), qHashRangeCommutative()
1240	*/
1241
1242	/*!
1243	\fn template <typename T, std::enable_if_t<std::is_same_v<T, bool>, bool> = true> size_t qHash(T key, size_t seed)
1244	\since 6.9
1245
1246	\qhashbuiltin
1247
1248	\note This is qHash(bool), constrained to accept only arguments of type bool,
1249	not arguments of types that merely convert to bool.
1250
1251	\note In Qt versions prior to 6.9, this overload was unintendedly provided by
1252	an undocumented 1-to-2-arg qHash adapter template function, with identical behavior.
1253	*/
1254
1255	/*! \fn size_t qHash(char key, size_t seed = 0)
1256	\since 5.0
1257	\qhashbuiltin
1258	*/
1259
1260	/*! \fn size_t qHash(uchar key, size_t seed = 0)
1261	\since 5.0
1262	\qhashbuiltin
1263	*/
1264
1265	/*! \fn size_t qHash(signed char key, size_t seed = 0)
1266	\since 5.0
1267	\qhashbuiltin
1268	*/
1269
1270	/*! \fn size_t qHash(ushort key, size_t seed = 0)
1271	\since 5.0
1272	\qhashbuiltin
1273	*/
1274
1275	/*! \fn size_t qHash(short key, size_t seed = 0)
1276	\since 5.0
1277	\qhashbuiltin
1278	*/
1279
1280	/*! \fn size_t qHash(uint key, size_t seed = 0)
1281	\since 5.0
1282	\qhashbuiltin
1283	*/
1284
1285	/*! \fn size_t qHash(int key, size_t seed = 0)
1286	\since 5.0
1287	\qhashbuiltin
1288	*/
1289
1290	/*! \fn size_t qHash(ulong key, size_t seed = 0)
1291	\since 5.0
1292	\qhashbuiltin
1293	*/
1294
1295	/*! \fn size_t qHash(long key, size_t seed = 0)
1296	\since 5.0
1297	\qhashbuiltin
1298	*/
1299
1300	/*! \fn size_t qHash(quint64 key, size_t seed = 0)
1301	\since 5.0
1302	\qhashbuiltin
1303	*/
1304
1305	/*! \fn size_t qHash(qint64 key, size_t seed = 0)
1306	\since 5.0
1307	\qhashbuiltin
1308	*/
1309
1310	/*! \fn size_t qHash(quint128 key, size_t seed = 0)
1311	\since 6.8
1312	\qhashbuiltin
1313
1314	\note This function is only available on platforms that support a native
1315	128-bit integer type.
1316	*/
1317
1318	/*! \fn size_t qHash(qint128 key, size_t seed = 0)
1319	\since 6.8
1320	\qhashbuiltin
1321
1322	\note This function is only available on platforms that support a native
1323	128-bit integer type.
1324	*/
1325
1326	/*! \fn size_t qHash(char8_t key, size_t seed = 0)
1327	\since 6.0
1328	\qhashbuiltin
1329	*/
1330
1331	/*! \fn size_t qHash(char16_t key, size_t seed = 0)
1332	\since 6.0
1333	\qhashbuiltin
1334	*/
1335
1336	/*! \fn size_t qHash(char32_t key, size_t seed = 0)
1337	\since 6.0
1338	\qhashbuiltin
1339	*/
1340
1341	/*! \fn size_t qHash(wchar_t key, size_t seed = 0)
1342	\since 6.0
1343	\qhashbuiltin
1344	*/
1345
1346	/*! \fn size_t qHash(float key, size_t seed = 0) noexcept
1347	\since 5.3
1348	\qhashbuiltin
1349	*/
1350
1351	/*!
1352	\since 5.3
1353	\qhashbuiltin
1354	*/
1355	size_t qHash(double key, size_t seed) noexcept
1356	{
1357	// ensure -0 gets mapped to 0
1358	key += 0.0;
1359	if constexpr (sizeof(double) == sizeof(size_t)) {
1360	size_t k;
1361	memcpy(dest: &k, src: &key, n: sizeof(double));
1362	return QHashPrivate::hash(key: k, seed);
1363	} else {
1364	return murmurhash(key: &key, len: sizeof(key), seed);
1365	}
1366	}
1367
1368	/*!
1369	\since 5.3
1370	\qhashbuiltin
1371	*/
1372	size_t qHash(long double key, size_t seed) noexcept
1373	{
1374	// ensure -0 gets mapped to 0
1375	key += static_cast<long double>(0.0);
1376	if constexpr (sizeof(long double) == sizeof(size_t)) {
1377	size_t k;
1378	memcpy(dest: &k, src: &key, n: sizeof(long double));
1379	return QHashPrivate::hash(key: k, seed);
1380	} else {
1381	return murmurhash(key: &key, len: sizeof(key), seed);
1382	}
1383	}
1384
1385	/*!
1386	\fn template <typename Enum, std::enable_if_t<std::is_enum_v<Enum>, bool> = true> size_t qHash(Enum key, size_t seed)
1387	\since 6.5
1388	\qhashbuiltin
1389
1390	\note Prior to Qt 6.5, unscoped enums relied on the integer overloads of this
1391	function due to implicit conversion to their underlying integer types.
1392	For scoped enums, you had to implement an overload yourself. This is still the
1393	backwards-compatible fix to remain compatible with older Qt versions.
1394	*/
1395
1396	/*! \fn size_t qHash(const QChar key, size_t seed = 0)
1397	\since 5.0
1398	\qhashold{QHash}
1399	*/
1400
1401	/*! \fn size_t qHash(const QByteArray &key, size_t seed = 0)
1402	\since 5.0
1403	\qhashold{QHash}
1404	*/
1405
1406	/*! \fn size_t qHash(QByteArrayView key, size_t seed = 0)
1407	\since 6.0
1408	\qhashold{QHash}
1409	*/
1410
1411	/*! \fn size_t qHash(const QBitArray &key, size_t seed = 0)
1412	\since 5.0
1413	\qhashold{QHash}
1414	*/
1415
1416	/*! \fn size_t qHash(const QString &key, size_t seed = 0)
1417	\since 5.0
1418	\qhashold{QHash}
1419	*/
1420
1421	/*! \fn size_t qHash(QLatin1StringView key, size_t seed = 0)
1422	\since 5.0
1423	\qhashold{QHash}
1424	*/
1425
1426	/*! \fn template <class T> size_t qHash(const T *key, size_t seed = 0)
1427	\since 5.0
1428	\qhashbuiltin
1429	*/
1430
1431	/*! \fn size_t qHash(std::nullptr_t key, size_t seed = 0)
1432	\since 6.0
1433	\qhashbuiltin
1434	*/
1435
1436	/*! \fn template<typename T> bool qHashEquals(const T &a, const T &b)
1437	\relates QHash
1438	\since 6.0
1439	\internal
1440
1441	This method is being used by QHash to compare two keys. Returns true if the
1442	keys \a a and \a b are considered equal for hashing purposes.
1443
1444	The default implementation returns the result of (a == b). It can be reimplemented
1445	for a certain type if the equality operator is not suitable for hashing purposes.
1446	This is for example the case if the equality operator uses qFuzzyCompare to compare
1447	floating point values.
1448	*/
1449
1450
1451	/*!
1452	\class QHash
1453	\inmodule QtCore
1454	\brief The QHash class is a template class that provides a hash-table-based dictionary.
1455	\compares equality
1456
1457	\ingroup tools
1458	\ingroup shared
1459
1460	\reentrant
1461
1462	QHash\<Key, T\> is one of Qt's generic \l{container classes}. It
1463	stores (key, value) pairs and provides very fast lookup of the
1464	value associated with a key.
1465
1466	QHash provides very similar functionality to QMap. The
1467	differences are:
1468
1469	\list
1470	\li QHash provides faster lookups than QMap. (See \l{Algorithmic
1471	Complexity} for details.)
1472	\li When iterating over a QMap, the items are always sorted by
1473	key. With QHash, the items are arbitrarily ordered.
1474	\li The key type of a QMap must provide operator<(). The key
1475	type of a QHash must provide operator==() and a global
1476	hash function called qHash() (see \l{qHash}).
1477	\endlist
1478
1479	Here's an example QHash with QString keys and \c int values:
1480	\snippet code/src_corelib_tools_qhash.cpp 0
1481
1482	To insert a (key, value) pair into the hash, you can use operator[]():
1483
1484	\snippet code/src_corelib_tools_qhash.cpp 1
1485
1486	This inserts the following three (key, value) pairs into the
1487	QHash: ("one", 1), ("three", 3), and ("seven", 7). Another way to
1488	insert items into the hash is to use insert():
1489
1490	\snippet code/src_corelib_tools_qhash.cpp 2
1491
1492	To look up a value, use operator[]() or value():
1493
1494	\snippet code/src_corelib_tools_qhash.cpp 3
1495
1496	If there is no item with the specified key in the hash, these
1497	functions return a \l{default-constructed value}.
1498
1499	If you want to check whether the hash contains a particular key,
1500	use contains():
1501
1502	\snippet code/src_corelib_tools_qhash.cpp 4
1503
1504	There is also a value() overload that uses its second argument as
1505	a default value if there is no item with the specified key:
1506
1507	\snippet code/src_corelib_tools_qhash.cpp 5
1508
1509	In general, we recommend that you use contains() and value()
1510	rather than operator[]() for looking up a key in a hash. The
1511	reason is that operator[]() silently inserts an item into the
1512	hash if no item exists with the same key (unless the hash is
1513	const). For example, the following code snippet will create 1000
1514	items in memory:
1515
1516	\snippet code/src_corelib_tools_qhash.cpp 6
1517
1518	To avoid this problem, replace \c hash[i] with \c hash.value(i)
1519	in the code above.
1520
1521	Internally, QHash uses a hash table to perform lookups. This
1522	hash table automatically grows to
1523	provide fast lookups without wasting too much memory. You can
1524	still control the size of the hash table by calling reserve() if
1525	you already know approximately how many items the QHash will
1526	contain, but this isn't necessary to obtain good performance. You
1527	can also call capacity() to retrieve the hash table's size.
1528
1529	QHash will not shrink automatically if items are removed from the
1530	table. To minimize the memory used by the hash, call squeeze().
1531
1532	To iterate through all the (key, value) pairs stored in a
1533	QHash, use \l {asKeyValueRange}():
1534
1535	\snippet code/src_corelib_tools_qhash.cpp 8
1536
1537	This function returns a range object that can be used with structured
1538	bindings. For manual iterator control, you can also use traditional
1539	\l{STL-style iterators} (QHash::const_iterator and QHash::iterator):
1540
1541	\snippet code/src_corelib_tools_qhash.cpp qhash-iterator-stl-style
1542
1543	To modify values, use iterators:
1544
1545	\snippet code/src_corelib_tools_qhash.cpp qhash-iterator-modify-values
1546
1547	QHash also provides \l{Java-style iterators} (QHashIterator and
1548	QMutableHashIterator) for compatibility.
1549
1550	QHash is unordered, so an iterator's sequence cannot be assumed
1551	to be predictable. If ordering by key is required, use a QMap.
1552
1553	A QHash allows only one value per key. If you call
1554	insert() with a key that already exists in the QHash, the
1555	previous value is erased. For example:
1556
1557	\snippet code/src_corelib_tools_qhash.cpp 9
1558
1559	If you need to store multiple entries for the same key in the
1560	hash table, use \l{QMultiHash}.
1561
1562	If you only need to extract the values from a hash (not the keys),
1563	you can also use range-based for:
1564
1565	\snippet code/src_corelib_tools_qhash.cpp 12
1566
1567	Items can be removed from the hash in several ways. One way is to
1568	call remove(); this will remove any item with the given key.
1569	Another way is to use QMutableHashIterator::remove(). In addition,
1570	you can clear the entire hash using clear().
1571
1572	QHash's key and value data types must be \l{assignable data
1573	types}. You cannot, for example, store a QWidget as a value;
1574	instead, store a QWidget *.
1575
1576	\target qHash
1577	\section2 The hashing function
1578
1579	A QHash's key type has additional requirements other than being an
1580	assignable data type: it must provide operator==(), and there must also be
1581	a hashing function that returns a hash value for an argument of the
1582	key's type.
1583
1584	The hashing function computes a numeric value based on a key. It
1585	can use any algorithm imaginable, as long as it always returns
1586	the same value if given the same argument. In other words, if
1587	\c{e1 == e2}, then \c{hash(e1) == hash(e2)} must hold as well.
1588	However, to obtain good performance, the hashing function should
1589	attempt to return different hash values for different keys to the
1590	largest extent possible.
1591
1592	A hashing function for a key type \c{K} may be provided in two
1593	different ways.
1594
1595	The first way is by having an overload of \c{qHash()} in \c{K}'s
1596	namespace. The \c{qHash()} function must have one of these signatures:
1597
1598	\snippet code/src_corelib_tools_qhash.cpp 32
1599
1600	The two-arguments overloads take an unsigned integer that should be used to
1601	seed the calculation of the hash function. This seed is provided by QHash
1602	in order to prevent a family of \l{algorithmic complexity attacks}.
1603
1604	\note In Qt 6 it is possible to define a \c{qHash()} overload
1605	taking only one argument; support for this is deprecated. Starting
1606	with Qt 7, it will be mandatory to use a two-arguments overload. If
1607	both a one-argument and a two-arguments overload are defined for a
1608	key type, the latter is used by QHash (note that you can simply
1609	define a two-arguments version, and use a default value for the
1610	seed parameter).
1611
1612	The second way to provide a hashing function is by specializing
1613	the \c{std::hash} class for the key type \c{K}, and providing a
1614	suitable function call operator for it:
1615
1616	\snippet code/src_corelib_tools_qhash.cpp 33
1617
1618	The seed argument has the same meaning as for \c{qHash()},
1619	and may be left out.
1620
1621	This second way allows to reuse the same hash function between
1622	QHash and the C++ Standard Library unordered associative containers.
1623	If both a \c{qHash()} overload and a \c{std::hash} specializations
1624	are provided for a type, then the \c{qHash()} overload is preferred.
1625
1626	Here's a partial list of the C++ and Qt types that can serve as keys in a
1627	QHash: any integer type (char, unsigned long, etc.), any pointer type,
1628	QChar, QString, and QByteArray. For all of these, the \c <QHash> header
1629	defines a qHash() function that computes an adequate hash value. Many other
1630	Qt classes also declare a qHash overload for their type; please refer to
1631	the documentation of each class.
1632
1633	If you want to use other types as the key, make sure that you provide
1634	operator==() and a hash implementation.
1635
1636	The convenience qHashMulti() function can be used to implement
1637	qHash() for a custom type, where one usually wants to produce a
1638	hash value from multiple fields:
1639
1640	Example:
1641	\snippet code/src_corelib_tools_qhash.cpp 13
1642
1643	In the example above, we've relied on Qt's own implementation of
1644	qHash() for QString and QDate to give us a hash value for the
1645	employee's name and date of birth respectively.
1646
1647	Note that the implementation of the qHash() overloads offered by Qt
1648	may change at any time. You \b{must not} rely on the fact that qHash()
1649	will give the same results (for the same inputs) across different Qt
1650	versions.
1651
1652	\section2 Algorithmic complexity attacks
1653
1654	All hash tables are vulnerable to a particular class of denial of service
1655	attacks, in which the attacker carefully pre-computes a set of different
1656	keys that are going to be hashed in the same bucket of a hash table (or
1657	even have the very same hash value). The attack aims at getting the
1658	worst-case algorithmic behavior (O(n) instead of amortized O(1), see
1659	\l{Algorithmic Complexity} for the details) when the data is fed into the
1660	table.
1661
1662	In order to avoid this worst-case behavior, the calculation of the hash
1663	value done by qHash() can be salted by a random seed, that nullifies the
1664	attack's extent. This seed is automatically generated by QHash once per
1665	process, and then passed by QHash as the second argument of the
1666	two-arguments overload of the qHash() function.
1667
1668	This randomization of QHash is enabled by default. Even though programs
1669	should never depend on a particular QHash ordering, there may be situations
1670	where you temporarily need deterministic behavior, for example for debugging or
1671	regression testing. To disable the randomization, define the environment
1672	variable \c QT_HASH_SEED to have the value 0. Alternatively, you can call
1673	the QHashSeed::setDeterministicGlobalSeed() function.
1674
1675	\sa QHashIterator, QMutableHashIterator, QMap, QSet
1676	*/
1677
1678	/*! \fn template <class Key, class T> QHash<Key, T>::QHash()
1679
1680	Constructs an empty hash.
1681
1682	\sa clear()
1683	*/
1684
1685	/*!
1686	\fn template <class Key, class T> QHash<Key, T>::QHash(QHash &&other)
1687
1688	Move-constructs a QHash instance, making it point at the same
1689	object that \a other was pointing to.
1690
1691	\since 5.2
1692	*/
1693
1694	/*! \fn template <class Key, class T> QHash<Key, T>::QHash(std::initializer_list<std::pair<Key,T> > list)
1695	\since 5.1
1696
1697	Constructs a hash with a copy of each of the elements in the
1698	initializer list \a list.
1699	*/
1700
1701	/*! \fn template <class Key, class T> template <class InputIterator> QHash<Key, T>::QHash(InputIterator begin, InputIterator end)
1702	\since 5.14
1703
1704	Constructs a hash with a copy of each of the elements in the iterator range
1705	[\a begin, \a end). Either the elements iterated by the range must be
1706	objects with \c{first} and \c{second} data members (like \c{std::pair}),
1707	convertible to \c Key and to \c T respectively; or the
1708	iterators must have \c{key()} and \c{value()} member functions, returning a
1709	key convertible to \c Key and a value convertible to \c T respectively.
1710	*/
1711
1712	/*! \fn template <class Key, class T> QHash<Key, T>::QHash(const QHash &other)
1713
1714	Constructs a copy of \a other.
1715
1716	This operation occurs in \l{constant time}, because QHash is
1717	\l{implicitly shared}. This makes returning a QHash from a
1718	function very fast. If a shared instance is modified, it will be
1719	copied (copy-on-write), and this takes \l{linear time}.
1720
1721	\sa operator=()
1722	*/
1723
1724	/*! \fn template <class Key, class T> QHash<Key, T>::~QHash()
1725
1726	Destroys the hash. References to the values in the hash and all
1727	iterators of this hash become invalid.
1728	*/
1729
1730	/*! \fn template <class Key, class T> QHash &QHash<Key, T>::operator=(const QHash &other)
1731
1732	Assigns \a other to this hash and returns a reference to this hash.
1733	*/
1734
1735	/*!
1736	\fn template <class Key, class T> QHash &QHash<Key, T>::operator=(QHash &&other)
1737
1738	Move-assigns \a other to this QHash instance.
1739
1740	\since 5.2
1741	*/
1742
1743	/*! \fn template <class Key, class T> void QHash<Key, T>::swap(QHash &other)
1744	\since 4.8
1745	\memberswap{hash}
1746	*/
1747
1748	/*! \fn template <class Key, class T> void QMultiHash<Key, T>::swap(QMultiHash &other)
1749	\since 4.8
1750	\memberswap{multi-hash}
1751	*/
1752
1753	/*! \fn template <class Key, class T> bool QHash<Key, T>::operator==(const QHash &lhs, const QHash &rhs)
1754
1755	Returns \c true if \a lhs hash is equal to \a rhs hash; otherwise returns
1756	\c false.
1757
1758	Two hashes are considered equal if they contain the same (key,
1759	value) pairs.
1760
1761	This function requires the value type to implement \c operator==().
1762
1763	\sa operator!=()
1764	*/
1765
1766	/*! \fn template <class Key, class T> bool QHash<Key, T>::operator!=(const QHash &lhs, const QHash &rhs)
1767
1768	Returns \c true if \a lhs hash is not equal to \a rhs hash; otherwise
1769	returns \c false.
1770
1771	Two hashes are considered equal if they contain the same (key,
1772	value) pairs.
1773
1774	This function requires the value type to implement \c operator==().
1775
1776	\sa operator==()
1777	*/
1778
1779	/*! \fn template <class Key, class T> qsizetype QHash<Key, T>::size() const
1780
1781	Returns the number of items in the hash.
1782
1783	\sa isEmpty(), count()
1784	*/
1785
1786	/*! \fn template <class Key, class T> bool QHash<Key, T>::isEmpty() const
1787
1788	Returns \c true if the hash contains no items; otherwise returns
1789	false.
1790
1791	\sa size()
1792	*/
1793
1794	/*! \fn template <class Key, class T> qsizetype QHash<Key, T>::capacity() const
1795
1796	Returns the number of buckets in the QHash's internal hash table.
1797
1798	The sole purpose of this function is to provide a means of fine
1799	tuning QHash's memory usage. In general, you will rarely ever
1800	need to call this function. If you want to know how many items are
1801	in the hash, call size().
1802
1803	\sa reserve(), squeeze()
1804	*/
1805
1806	/*! \fn template <class Key, class T> float QHash<Key, T>::load_factor() const noexcept
1807
1808	Returns the current load factor of the QHash's internal hash table.
1809	This is the same as capacity()/size(). The implementation used
1810	will aim to keep the load factor between 0.25 and 0.5. This avoids
1811	having too many hash table collisions that would degrade performance.
1812
1813	Even with a low load factor, the implementation of the hash table has a
1814	very low memory overhead.
1815
1816	This method purely exists for diagnostic purposes and you should rarely
1817	need to call it yourself.
1818
1819	\sa reserve(), squeeze()
1820	*/
1821
1822
1823	/*! \fn template <class Key, class T> void QHash<Key, T>::reserve(qsizetype size)
1824
1825	Ensures that the QHash's internal hash table has space to store at
1826	least \a size items without having to grow the hash table.
1827
1828	This implies that the hash table will contain at least 2 * \a size buckets
1829	to ensure good performance
1830
1831	This function is useful for code that needs to build a huge hash
1832	and wants to avoid repeated reallocation. For example:
1833
1834	\snippet code/src_corelib_tools_qhash.cpp 14
1835
1836	Ideally, \a size should be the maximum number of items expected
1837	in the hash. QHash will then choose the smallest possible
1838	number of buckets that will allow storing \a size items in the table
1839	without having to grow the internal hash table. If \a size
1840	is an underestimate, the worst that will happen is that the QHash
1841	will be a bit slower.
1842
1843	In general, you will rarely ever need to call this function.
1844	QHash's internal hash table automatically grows to
1845	provide good performance without wasting too much memory.
1846
1847	\sa squeeze(), capacity()
1848	*/
1849
1850	/*! \fn template <class Key, class T> void QHash<Key, T>::squeeze()
1851
1852	Reduces the size of the QHash's internal hash table to save
1853	memory.
1854
1855	The sole purpose of this function is to provide a means of fine
1856	tuning QHash's memory usage. In general, you will rarely ever
1857	need to call this function.
1858
1859	\sa reserve(), capacity()
1860	*/
1861
1862	/*! \fn template <class Key, class T> void QHash<Key, T>::detach()
1863
1864	\internal
1865
1866	Detaches this hash from any other hashes with which it may share
1867	data.
1868
1869	\sa isDetached()
1870	*/
1871
1872	/*! \fn template <class Key, class T> bool QHash<Key, T>::isDetached() const
1873
1874	\internal
1875
1876	Returns \c true if the hash's internal data isn't shared with any
1877	other hash object; otherwise returns \c false.
1878
1879	\sa detach()
1880	*/
1881
1882	/*! \fn template <class Key, class T> bool QHash<Key, T>::isSharedWith(const QHash &other) const
1883
1884	\internal
1885
1886	Returns true if the internal hash table of this QHash is shared with \a other, otherwise false.
1887	*/
1888
1889	/*! \fn template <class Key, class T> void QHash<Key, T>::clear()
1890
1891	Removes all items from the hash and frees up all memory used by it.
1892
1893	\sa remove()
1894	*/
1895
1896	/*! \fn template <class Key, class T> bool QHash<Key, T>::remove(const Key &key)
1897
1898	Removes the item that has the \a key from the hash.
1899	Returns true if the key exists in the hash and the item has been removed,
1900	and false otherwise.
1901
1902	\sa clear(), take()
1903	*/
1904
1905	/*! \fn template <class Key, class T> template <typename Predicate> qsizetype QHash<Key, T>::removeIf(Predicate pred)
1906	\since 6.1
1907
1908	Removes all elements for which the predicate \a pred returns true
1909	from the hash.
1910
1911	The function supports predicates which take either an argument of
1912	type \c{QHash<Key, T>::iterator}, or an argument of type
1913	\c{std::pair<const Key &, T &>}.
1914
1915	Returns the number of elements removed, if any.
1916
1917	\sa clear(), take()
1918	*/
1919
1920	/*! \fn template <class Key, class T> T QHash<Key, T>::take(const Key &key)
1921
1922	Removes the item with the \a key from the hash and returns
1923	the value associated with it.
1924
1925	If the item does not exist in the hash, the function simply
1926	returns a \l{default-constructed value}.
1927
1928	If you don't use the return value, remove() is more efficient.
1929
1930	\sa remove()
1931	*/
1932
1933	/*! \fn template <class Key, class T> bool QHash<Key, T>::contains(const Key &key) const
1934
1935	Returns \c true if the hash contains an item with the \a key;
1936	otherwise returns \c false.
1937
1938	\sa count()
1939	*/
1940
1941	/*! \fn template <class Key, class T> T QHash<Key, T>::value(const Key &key) const
1942	\fn template <class Key, class T> T QHash<Key, T>::value(const Key &key, const T &defaultValue) const
1943	\overload
1944
1945	Returns the value associated with the \a key.
1946
1947	If the hash contains no item with the \a key, the function
1948	returns \a defaultValue, or a \l{default-constructed value} if this
1949	parameter has not been supplied.
1950	*/
1951
1952	/*! \fn template <class Key, class T> T &QHash<Key, T>::operator[](const Key &key)
1953
1954	Returns the value associated with the \a key as a modifiable
1955	reference.
1956
1957	If the hash contains no item with the \a key, the function inserts
1958	a \l{default-constructed value} into the hash with the \a key, and
1959	returns a reference to it.
1960
1961	//! [qhash-iterator-invalidation-func-desc]
1962	\warning Returned iterators/references should be considered invalidated
1963	the next time you call a non-const function on the hash, or when the
1964	hash is destroyed.
1965	//! [qhash-iterator-invalidation-func-desc]
1966
1967	\sa insert(), value()
1968	*/
1969
1970	/*! \fn template <class Key, class T> const T QHash<Key, T>::operator[](const Key &key) const
1971
1972	\overload
1973
1974	Same as value().
1975	*/
1976
1977	/*! \fn template <class Key, class T> QList<Key> QHash<Key, T>::keys() const
1978
1979	Returns a list containing all the keys in the hash, in an
1980	arbitrary order.
1981
1982	The order is guaranteed to be the same as that used by values().
1983
1984	This function creates a new list, in \l {linear time}. The time and memory
1985	use that entails can be avoided by iterating from \l keyBegin() to
1986	\l keyEnd().
1987
1988	\sa values(), key()
1989	*/
1990
1991	/*! \fn template <class Key, class T> QList<Key> QHash<Key, T>::keys(const T &value) const
1992
1993	\overload
1994
1995	Returns a list containing all the keys associated with value \a
1996	value, in an arbitrary order.
1997
1998	This function can be slow (\l{linear time}), because QHash's
1999	internal data structure is optimized for fast lookup by key, not
2000	by value.
2001	*/
2002
2003	/*! \fn template <class Key, class T> QList<T> QHash<Key, T>::values() const
2004
2005	Returns a list containing all the values in the hash, in an
2006	arbitrary order.
2007
2008	The order is guaranteed to be the same as that used by keys().
2009
2010	This function creates a new list, in \l {linear time}. The time and memory
2011	use that entails can be avoided by iterating from \l keyValueBegin() to
2012	\l keyValueEnd().
2013
2014	\sa keys(), value()
2015	*/
2016
2017	/*!
2018	\fn template <class Key, class T> Key QHash<Key, T>::key(const T &value) const
2019	\fn template <class Key, class T> Key QHash<Key, T>::key(const T &value, const Key &defaultKey) const
2020	\since 4.3
2021
2022	Returns the first key mapped to \a value. If the hash contains no item
2023	mapped to \a value, returns \a defaultKey, or a \l{default-constructed
2024	value}{default-constructed key} if this parameter has not been supplied.
2025
2026	This function can be slow (\l{linear time}), because QHash's
2027	internal data structure is optimized for fast lookup by key, not
2028	by value.
2029	*/
2030
2031	/*! \fn template <class Key, class T> qsizetype QHash<Key, T>::count(const Key &key) const
2032
2033	Returns the number of items associated with the \a key.
2034
2035	\sa contains()
2036	*/
2037
2038	/*! \fn template <class Key, class T> qsizetype QHash<Key, T>::count() const
2039
2040	\overload
2041
2042	Same as size().
2043	*/
2044
2045	/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::begin()
2046
2047	Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first item in
2048	the hash.
2049
2050	\include qhash.cpp qhash-iterator-invalidation-func-desc
2051
2052	\sa constBegin(), end()
2053	*/
2054
2055	/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::begin() const
2056
2057	\overload
2058
2059	\include qhash.cpp qhash-iterator-invalidation-func-desc
2060	*/
2061
2062	/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::cbegin() const
2063	\since 5.0
2064
2065	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item
2066	in the hash.
2067
2068	\include qhash.cpp qhash-iterator-invalidation-func-desc
2069
2070	\sa begin(), cend()
2071	*/
2072
2073	/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::constBegin() const
2074
2075	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item
2076	in the hash.
2077
2078	\include qhash.cpp qhash-iterator-invalidation-func-desc
2079
2080	\sa begin(), constEnd()
2081	*/
2082
2083	/*! \fn template <class Key, class T> QHash<Key, T>::key_iterator QHash<Key, T>::keyBegin() const
2084	\since 5.6
2085
2086	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first key
2087	in the hash.
2088
2089	\include qhash.cpp qhash-iterator-invalidation-func-desc
2090
2091	\sa keyEnd()
2092	*/
2093
2094	/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::end()
2095
2096	Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary item
2097	after the last item in the hash.
2098
2099	\include qhash.cpp qhash-iterator-invalidation-func-desc
2100
2101	\sa begin(), constEnd()
2102	*/
2103
2104	/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::end() const
2105
2106	\overload
2107
2108	\include qhash.cpp qhash-iterator-invalidation-func-desc
2109	*/
2110
2111	/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::constEnd() const
2112
2113	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
2114	item after the last item in the hash.
2115
2116	\include qhash.cpp qhash-iterator-invalidation-func-desc
2117
2118	\sa constBegin(), end()
2119	*/
2120
2121	/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::cend() const
2122	\since 5.0
2123
2124	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
2125	item after the last item in the hash.
2126
2127	\include qhash.cpp qhash-iterator-invalidation-func-desc
2128
2129	\sa cbegin(), end()
2130	*/
2131
2132	/*! \fn template <class Key, class T> QHash<Key, T>::key_iterator QHash<Key, T>::keyEnd() const
2133	\since 5.6
2134
2135	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
2136	item after the last key in the hash.
2137
2138	\include qhash.cpp qhash-iterator-invalidation-func-desc
2139
2140	\sa keyBegin()
2141	*/
2142
2143	/*! \fn template <class Key, class T> QHash<Key, T>::key_value_iterator QHash<Key, T>::keyValueBegin()
2144	\since 5.10
2145
2146	Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first entry
2147	in the hash.
2148
2149	\include qhash.cpp qhash-iterator-invalidation-func-desc
2150
2151	\sa keyValueEnd()
2152	*/
2153
2154	/*! \fn template <class Key, class T> QHash<Key, T>::key_value_iterator QHash<Key, T>::keyValueEnd()
2155	\since 5.10
2156
2157	Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
2158	entry after the last entry in the hash.
2159
2160	\include qhash.cpp qhash-iterator-invalidation-func-desc
2161
2162	\sa keyValueBegin()
2163	*/
2164
2165	/*! \fn template <class Key, class T> QHash<Key, T>::const_key_value_iterator QHash<Key, T>::keyValueBegin() const
2166	\since 5.10
2167
2168	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry
2169	in the hash.
2170
2171	\include qhash.cpp qhash-iterator-invalidation-func-desc
2172
2173	\sa keyValueEnd()
2174	*/
2175
2176	/*! \fn template <class Key, class T> QHash<Key, T>::const_key_value_iterator QHash<Key, T>::constKeyValueBegin() const
2177	\since 5.10
2178
2179	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry
2180	in the hash.
2181
2182	\include qhash.cpp qhash-iterator-invalidation-func-desc
2183
2184	\sa keyValueBegin()
2185	*/
2186
2187	/*! \fn template <class Key, class T> QHash<Key, T>::const_key_value_iterator QHash<Key, T>::keyValueEnd() const
2188	\since 5.10
2189
2190	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
2191	entry after the last entry in the hash.
2192
2193	\include qhash.cpp qhash-iterator-invalidation-func-desc
2194
2195	\sa keyValueBegin()
2196	*/
2197
2198	/*! \fn template <class Key, class T> QHash<Key, T>::const_key_value_iterator QHash<Key, T>::constKeyValueEnd() const
2199	\since 5.10
2200
2201	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
2202	entry after the last entry in the hash.
2203
2204	\include qhash.cpp qhash-iterator-invalidation-func-desc
2205
2206	\sa constKeyValueBegin()
2207	*/
2208
2209	/*! \fn template <class Key, class T> auto QHash<Key, T>::asKeyValueRange() &
2210	\fn template <class Key, class T> auto QHash<Key, T>::asKeyValueRange() const &
2211	\fn template <class Key, class T> auto QHash<Key, T>::asKeyValueRange() &&
2212	\fn template <class Key, class T> auto QHash<Key, T>::asKeyValueRange() const &&
2213	\since 6.4
2214
2215	Returns a range object that allows iteration over this hash as
2216	key/value pairs. For instance, this range object can be used in a
2217	range-based for loop, in combination with a structured binding declaration:
2218
2219	\snippet code/src_corelib_tools_qhash.cpp 34
2220
2221	Note that both the key and the value obtained this way are
2222	references to the ones in the hash. Specifically, mutating the value
2223	will modify the hash itself.
2224
2225	\include qhash.cpp qhash-iterator-invalidation-func-desc
2226
2227	\sa QKeyValueIterator
2228	*/
2229
2230	/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::erase(const_iterator pos)
2231	\since 5.7
2232
2233	Removes the (key, value) pair associated with the iterator \a pos
2234	from the hash, and returns an iterator to the next item in the
2235	hash.
2236
2237	This function never causes QHash to
2238	rehash its internal data structure. This means that it can safely
2239	be called while iterating, and won't affect the order of items in
2240	the hash. For example:
2241
2242	\snippet code/src_corelib_tools_qhash.cpp 15
2243
2244	\include qhash.cpp qhash-iterator-invalidation-func-desc
2245
2246	\sa remove(), take(), find()
2247	*/
2248
2249	/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::find(const Key &key)
2250
2251	Returns an iterator pointing to the item with the \a key in the
2252	hash.
2253
2254	If the hash contains no item with the \a key, the function
2255	returns end().
2256
2257	If the hash contains multiple items with the \a key, this
2258	function returns an iterator that points to the most recently
2259	inserted value. The other values are accessible by incrementing
2260	the iterator. For example, here's some code that iterates over all
2261	the items with the same key:
2262
2263	\snippet code/src_corelib_tools_qhash.cpp 16
2264
2265	\include qhash.cpp qhash-iterator-invalidation-func-desc
2266
2267	\sa value(), values()
2268	*/
2269
2270	/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::find(const Key &key) const
2271
2272	\overload
2273
2274	\include qhash.cpp qhash-iterator-invalidation-func-desc
2275	*/
2276
2277	/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::constFind(const Key &key) const
2278	\since 4.1
2279
2280	Returns an iterator pointing to the item with the \a key in the
2281	hash.
2282
2283	If the hash contains no item with the \a key, the function
2284	returns constEnd().
2285
2286	\include qhash.cpp qhash-iterator-invalidation-func-desc
2287
2288	\sa find()
2289	*/
2290
2291	/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::insert(const Key &key, const T &value)
2292
2293	Inserts a new item with the \a key and a value of \a value.
2294
2295	If there is already an item with the \a key, that item's value
2296	is replaced with \a value.
2297
2298	Returns an iterator pointing to the new/updated element.
2299
2300	\include qhash.cpp qhash-iterator-invalidation-func-desc
2301	*/
2302
2303	/*!
2304	\fn template <class Key, class T> template <typename ...Args> QHash<Key, T>::iterator QHash<Key, T>::emplace(const Key &key, Args&&... args)
2305	\fn template <class Key, class T> template <typename ...Args> QHash<Key, T>::iterator QHash<Key, T>::emplace(Key &&key, Args&&... args)
2306
2307	Inserts a new element into the container. This new element
2308	is constructed in-place using \a args as the arguments for its
2309	construction.
2310
2311	Returns an iterator pointing to the new element.
2312
2313	\include qhash.cpp qhash-iterator-invalidation-func-desc
2314	*/
2315
2316	/*!
2317	\class QHash::TryEmplaceResult
2318	\inmodule QtCore
2319	\since 6.9
2320	\ingroup tools
2321	\brief The TryEmplaceResult class is used to represent the result of a tryEmplace() operation.
2322
2323	The \c{TryEmplaceResult} class is used in QHash to represent the result
2324	of a tryEmplace() operation. It holds an \l{iterator} to the newly
2325	created item, or to the pre-existing item that prevented the insertion, and
2326	a boolean, \l{inserted}, denoting whether the insertion took place.
2327
2328	\sa QHash, QHash::tryEmplace()
2329	*/
2330
2331	/*!
2332	\variable QHash::TryEmplaceResult::iterator
2333
2334	Holds the iterator to the newly inserted element, or the element that
2335	prevented the insertion.
2336	*/
2337
2338	/*!
2339	\variable QHash::TryEmplaceResult::inserted
2340
2341	This value is \c{false} if there was already an entry with the same key.
2342	*/
2343
2344	/*!
2345	\fn template <class Key, class T> template <typename... Args> QHash<Key, T>::TryEmplaceResult QHash<Key, T>::tryEmplace(const Key &key, Args &&...args)
2346	\fn template <class Key, class T> template <typename... Args> QHash<Key, T>::TryEmplaceResult QHash<Key, T>::tryEmplace(Key &&key, Args &&...args)
2347	\fn template <class Key, class T> template <typename K, typename... Args, QHash<Key, T>::if_heterogeneously_searchable<K> = true, QHash<Key, T>::if_key_constructible_from<K> = true> QHash<Key, T>::TryEmplaceResult QHash<Key, T>::tryEmplace(K &&key, Args &&...args)
2348	\since 6.9
2349
2350	Inserts a new item with the \a key and a value constructed from \a args.
2351	If an item with \a key already exists, no insertion takes place.
2352
2353	Returns an instance of \l{TryEmplaceResult}, a structure that holds an
2354	\l{QHash::TryEmplaceResult::}{iterator} to the newly created item, or
2355	to the pre-existing item that prevented the insertion, and a boolean,
2356	\l{QHash::TryEmplaceResult::}{inserted}, denoting whether the insertion
2357	took place.
2358
2359	For example, this can be used to avoid the pattern of comparing old and
2360	new size or double-lookups. Where you might previously have written code like:
2361
2362	\code
2363	QHash<int, MyType> hash;
2364	// [...]
2365	int myKey = getKey();
2366	qsizetype oldSize = hash.size();
2367	MyType &elem = hash[myKey];
2368	if (oldSize != hash.size()) // Size changed: new element!
2369	initialize(elem);
2370	// [use elem...]
2371	\endcode
2372
2373	You can instead write:
2374
2375	\code
2376	QHash<int, MyType> hash;
2377	// [...]
2378	int myKey = getKey();
2379	auto result = hash.tryEmplace(myKey);
2380	if (result.inserted) // New element!
2381	initialize(*result.iterator);
2382	// [use result.iterator...]
2383	\endcode
2384
2385	\sa emplace(), tryInsert(), insertOrAssign()
2386	*/
2387
2388	/*!
2389	\fn template <class Key, class T> QHash<Key, T>::TryEmplaceResult QHash<Key, T>::tryInsert(const Key &key, const T &value)
2390	\fn template <class Key, class T> template <typename K, QHash<Key, T>::if_heterogeneously_searchable<K> = true, QHash<Key, T>::if_key_constructible_from<K> = true> QHash<Key, T>::TryEmplaceResult QHash<Key, T>::tryInsert(K &&key, const T &value)
2391	\since 6.9
2392
2393	Inserts a new item with the \a key and a value of \a value.
2394	If an item with \a key already exists, no insertion takes place.
2395
2396	Returns an instance of \l{TryEmplaceResult}, a structure that holds an
2397	\l{QHash::TryEmplaceResult::}{iterator} to the newly created item, or to the pre-existing item
2398	that prevented the insertion, and a boolean, \l{QHash::TryEmplaceResult::}{inserted}, denoting
2399	whether the insertion took place.
2400
2401	\sa insert(), tryEmplace(), insertOrAssign()
2402	*/
2403
2404	/*!
2405	\fn template <class Key, class T> template <typename K, typename... Args, QHash<Key, T>::if_heterogeneously_searchable<K> = true, QHash<Key, T>::if_key_constructible_from<K> = true> iterator QHash<Key, T>::try_emplace(const_iterator hint, K &&key, Args &&...args)
2406	\fn template <class Key, class T> template <typename... Args> iterator QHash<Key, T>::try_emplace(const_iterator hint, const Key &key, Args &&...args)
2407	\fn template <class Key, class T> template <typename... Args> iterator QHash<Key, T>::try_emplace(const_iterator hint, Key &&key, Args &&...args)
2408	\since 6.9
2409
2410	Inserts a new item with the \a key and a value constructed from \a args.
2411	If an item with \a key already exists, no insertion takes place.
2412
2413	Returns the iterator of the inserted item, or to the item that prevented the
2414	insertion.
2415
2416	\a hint is ignored.
2417
2418	These functions are provided for compatibility with the standard library.
2419
2420	\sa emplace(), tryEmplace(), tryInsert(), insertOrAssign()
2421	*/
2422
2423	/*!
2424	\fn template <class Key, class T> template <typename... Args> std::pair<iterator, bool> QHash<Key, T>::try_emplace(const Key &key, Args &&...args)
2425	\fn template <class Key, class T> template <typename... Args> std::pair<iterator, bool> QHash<Key, T>::try_emplace(Key &&key, Args &&...args)
2426	\fn template <class Key, class T> template <typename K, typename... Args, QHash<Key, T>::if_heterogeneously_searchable<K> = true, QHash<Key, T>::if_key_constructible_from<K> = true> std::pair<iterator, bool> QHash<Key, T>::try_emplace(K &&key, Args &&...args)
2427	\since 6.9
2428
2429	Inserts a new item with the \a key and a value constructed from \a args.
2430	If an item with \a key already exists, no insertion takes place.
2431
2432	Returns a pair consisting of an iterator to the inserted item (or to the
2433	item that prevented the insertion), and a bool denoting whether the
2434	insertion took place.
2435
2436	These functions are provided for compatibility with the standard library.
2437
2438	\sa emplace(), tryEmplace(), tryInsert(), insertOrAssign()
2439	*/
2440
2441	/*!
2442	\fn template <class Key, class T> template <typename Value> QHash<Key, T>::TryEmplaceResult QHash<Key, T>::insertOrAssign(const Key &key, Value &&value)
2443	\fn template <class Key, class T> template <typename Value> QHash<Key, T>::TryEmplaceResult QHash<Key, T>::insertOrAssign(Key &&key, Value &&value)
2444	\fn template <class Key, class T> template <typename K, typename Value, QHash<Key, T>::if_heterogeneously_searchable<K> = true, QHash<Key, T>::if_key_constructible_from<K> = true> QHash<Key, T>::TryEmplaceResult QHash<Key, T>::insertOrAssign(K &&key, Value &&value)
2445	\since 6.9
2446
2447	Attempts to insert an item with the \a key and \a value.
2448	If an item with \a key already exists its value is overwritten with \a value.
2449
2450	Returns an instance of \l{TryEmplaceResult}, a structure that holds an
2451	\l{QHash::TryEmplaceResult::}{iterator} to the item, and a boolean,
2452	\l{QHash::TryEmplaceResult::}{inserted}, denoting whether the item was newly created (\c{true})
2453	or if it previously existed (\c{false}).
2454
2455	\sa insert(), tryEmplace(), tryInsert()
2456	*/
2457
2458	/*!
2459	\fn template <class Key, class T> template <typename Value> std::pair<QHash<Key, T>::key_value_iterator, bool> QHash<Key, T>::insert_or_assign(const Key &key, Value &&value)
2460	\fn template <class Key, class T> template <typename Value> std::pair<QHash<Key, T>::key_value_iterator, bool> QHash<Key, T>::insert_or_assign(Key &&key, Value &&value)
2461	\fn template <class Key, class T> template <typename K, typename Value, QHash<Key, T>::if_heterogeneously_searchable<K> = true, QHash<Key, T>::if_key_constructible_from<K> = true> std::pair<QHash<Key, T>::key_value_iterator, bool> QHash<Key, T>::insert_or_assign(K &&key, Value &&value)
2462	\since 6.9
2463
2464	Attempts to insert an item with the \a key and \a value.
2465	If an item with \a key already exists its value is overwritten with \a value.
2466
2467	Returns a pair consisting of an iterator pointing to the item, and a
2468	boolean, denoting whether the item was newly created (\c{true}) or if it
2469	previously existed (\c{false}).
2470
2471	These functions are provided for compatibility with the standard library.
2472
2473	\sa insert(), tryEmplace(), tryInsert(), insertOrAssign()
2474	*/
2475
2476	/*!
2477	\fn template <class Key, class T> template <typename Value> std::pair<QHash<Key, T>::key_value_iterator, bool> QHash<Key, T>::insert_or_assign(const_iterator hint, const Key &key, Value &&value)
2478	\fn template <class Key, class T> template <typename Value> std::pair<QHash<Key, T>::key_value_iterator, bool> QHash<Key, T>::insert_or_assign(const_iterator hint, Key &&key, Value &&value)
2479	\fn template <class Key, class T> template <typename K, typename Value, QHash<Key, T>::if_heterogeneously_searchable<K> = true, QHash<Key, T>::if_key_constructible_from<K> = true> std::pair<QHash<Key, T>::key_value_iterator, bool> QHash<Key, T>::insert_or_assign(const_iterator hint, K &&key, Value &&value)
2480	\since 6.9
2481
2482	Attempts to insert an item with the \a key and \a value.
2483	If an item with \a key already exists its value is overwritten with \a value.
2484
2485	Returns a pair consisting of an iterator pointing to the item, and a
2486	boolean, denoting whether the item was newly created (\c{true}) or if it
2487	previously existed (\c{false}).
2488
2489	\a hint is ignored.
2490
2491	These functions are provided for compatibility with the standard library.
2492
2493	\sa insert(), tryEmplace(), insertOrAssign()
2494	*/
2495
2496	/*! \fn template <class Key, class T> void QHash<Key, T>::insert(const QHash &other)
2497	\since 5.15
2498
2499	Inserts all the items in the \a other hash into this hash.
2500
2501	If a key is common to both hashes, its value will be replaced with the
2502	value stored in \a other.
2503	*/
2504
2505	/*! \fn template <class Key, class T> bool QHash<Key, T>::empty() const
2506
2507	This function is provided for STL compatibility. It is equivalent
2508	to isEmpty(), returning true if the hash is empty; otherwise
2509	returns \c false.
2510	*/
2511
2512	/*! \fn template <class Key, class T> std::pair<iterator, iterator> QMultiHash<Key, T>::equal_range(const Key &key)
2513	\since 5.7
2514
2515	Returns a pair of iterators delimiting the range of values \c{[first, second)}, that
2516	are stored under \a key. If the range is empty then both iterators will be equal to end().
2517
2518	\include qhash.cpp qhash-iterator-invalidation-func-desc
2519	*/
2520
2521	/*!
2522	\fn template <class Key, class T> std::pair<const_iterator, const_iterator> QMultiHash<Key, T>::equal_range(const Key &key) const
2523	\overload
2524	\since 5.7
2525
2526	\include qhash.cpp qhash-iterator-invalidation-func-desc
2527	*/
2528
2529	/*! \typedef QHash::ConstIterator
2530
2531	Qt-style synonym for QHash::const_iterator.
2532	*/
2533
2534	/*! \typedef QHash::Iterator
2535
2536	Qt-style synonym for QHash::iterator.
2537	*/
2538
2539	/*! \typedef QHash::difference_type
2540
2541	Typedef for ptrdiff_t. Provided for STL compatibility.
2542	*/
2543
2544	/*! \typedef QHash::key_type
2545
2546	Typedef for Key. Provided for STL compatibility.
2547	*/
2548
2549	/*! \typedef QHash::mapped_type
2550
2551	Typedef for T. Provided for STL compatibility.
2552	*/
2553
2554	/*! \typedef QHash::size_type
2555
2556	Typedef for int. Provided for STL compatibility.
2557	*/
2558
2559	/*! \typedef QHash::iterator::difference_type
2560	\internal
2561	*/
2562
2563	/*! \typedef QHash::iterator::iterator_category
2564	\internal
2565	*/
2566
2567	/*! \typedef QHash::iterator::pointer
2568	\internal
2569	*/
2570
2571	/*! \typedef QHash::iterator::reference
2572	\internal
2573	*/
2574
2575	/*! \typedef QHash::iterator::value_type
2576	\internal
2577	*/
2578
2579	/*! \typedef QHash::const_iterator::difference_type
2580	\internal
2581	*/
2582
2583	/*! \typedef QHash::const_iterator::iterator_category
2584	\internal
2585	*/
2586
2587	/*! \typedef QHash::const_iterator::pointer
2588	\internal
2589	*/
2590
2591	/*! \typedef QHash::const_iterator::reference
2592	\internal
2593	*/
2594
2595	/*! \typedef QHash::const_iterator::value_type
2596	\internal
2597	*/
2598
2599	/*! \typedef QHash::key_iterator::difference_type
2600	\internal
2601	*/
2602
2603	/*! \typedef QHash::key_iterator::iterator_category
2604	\internal
2605	*/
2606
2607	/*! \typedef QHash::key_iterator::pointer
2608	\internal
2609	*/
2610
2611	/*! \typedef QHash::key_iterator::reference
2612	\internal
2613	*/
2614
2615	/*! \typedef QHash::key_iterator::value_type
2616	\internal
2617	*/
2618
2619	/*! \class QHash::iterator
2620	\inmodule QtCore
2621	\brief The QHash::iterator class provides an STL-style non-const iterator for QHash.
2622
2623	QHash\<Key, T\>::iterator allows you to iterate over a QHash
2624	and to modify the value (but not the key) associated
2625	with a particular key. If you want to iterate over a const QHash,
2626	you should use QHash::const_iterator. It is generally good
2627	practice to use QHash::const_iterator on a non-const QHash as
2628	well, unless you need to change the QHash through the iterator.
2629	Const iterators are slightly faster, and can improve code
2630	readability.
2631
2632	The default QHash::iterator constructor creates an uninitialized
2633	iterator. You must initialize it using a QHash function like
2634	QHash::begin(), QHash::end(), or QHash::find() before you can
2635	start iterating. Here's a typical loop that prints all the (key,
2636	value) pairs stored in a hash:
2637
2638	\snippet code/src_corelib_tools_qhash.cpp 17
2639
2640	Unlike QMap, which orders its items by key, QHash stores its
2641	items in an arbitrary order.
2642
2643	Here's an example that increments every value stored in the QHash
2644	by 2:
2645
2646	\snippet code/src_corelib_tools_qhash.cpp 18
2647
2648	To remove elements from a QHash you can use erase_if(QHash\<Key, T\> &map, Predicate pred):
2649
2650	\snippet code/src_corelib_tools_qhash.cpp 21
2651
2652	Multiple iterators can be used on the same hash. However, be aware
2653	that any modification performed directly on the QHash (inserting and
2654	removing items) can cause the iterators to become invalid.
2655
2656	Inserting items into the hash or calling methods such as QHash::reserve()
2657	or QHash::squeeze() can invalidate all iterators pointing into the hash.
2658	Iterators are guaranteed to stay valid only as long as the QHash doesn't have
2659	to grow/shrink its internal hash table.
2660	Using any iterator after a rehashing operation has occurred will lead to undefined behavior.
2661
2662	If you need to keep iterators over a long period of time, we recommend
2663	that you use QMap rather than QHash.
2664
2665	\warning Iterators on implicitly shared containers do not work
2666	exactly like STL-iterators. You should avoid copying a container
2667	while iterators are active on that container. For more information,
2668	read \l{Implicit sharing iterator problem}.
2669
2670	\sa QHash::const_iterator, QHash::key_iterator, QHash::key_value_iterator
2671	*/
2672
2673	/*! \fn template <class Key, class T> QHash<Key, T>::iterator::iterator()
2674
2675	Constructs an uninitialized iterator.
2676
2677	Functions like key(), value(), and operator++() must not be
2678	called on an uninitialized iterator. Use operator=() to assign a
2679	value to it before using it.
2680
2681	\sa QHash::begin(), QHash::end()
2682	*/
2683
2684	/*! \fn template <class Key, class T> const Key &QHash<Key, T>::iterator::key() const
2685
2686	Returns the current item's key as a const reference.
2687
2688	There is no direct way of changing an item's key through an
2689	iterator, although it can be done by calling QHash::erase()
2690	followed by QHash::insert().
2691
2692	\sa value()
2693	*/
2694
2695	/*! \fn template <class Key, class T> T &QHash<Key, T>::iterator::value() const
2696
2697	Returns a modifiable reference to the current item's value.
2698
2699	You can change the value of an item by using value() on
2700	the left side of an assignment, for example:
2701
2702	\snippet code/src_corelib_tools_qhash.cpp 22
2703
2704	\sa key(), operator*()
2705	*/
2706
2707	/*! \fn template <class Key, class T> T &QHash<Key, T>::iterator::operator*() const
2708
2709	Returns a modifiable reference to the current item's value.
2710
2711	Same as value().
2712
2713	\sa key()
2714	*/
2715
2716	/*! \fn template <class Key, class T> T *QHash<Key, T>::iterator::operator->() const
2717
2718	Returns a pointer to the current item's value.
2719
2720	\sa value()
2721	*/
2722
2723	/*!
2724	\fn template <class Key, class T> bool QHash<Key, T>::iterator::operator==(const iterator &other) const
2725	\fn template <class Key, class T> bool QHash<Key, T>::iterator::operator==(const const_iterator &other) const
2726
2727	Returns \c true if \a other points to the same item as this
2728	iterator; otherwise returns \c false.
2729
2730	\sa operator!=()
2731	*/
2732
2733	/*!
2734	\fn template <class Key, class T> bool QHash<Key, T>::iterator::operator!=(const iterator &other) const
2735	\fn template <class Key, class T> bool QHash<Key, T>::iterator::operator!=(const const_iterator &other) const
2736
2737	Returns \c true if \a other points to a different item than this
2738	iterator; otherwise returns \c false.
2739
2740	\sa operator==()
2741	*/
2742
2743	/*!
2744	\fn template <class Key, class T> QHash<Key, T>::iterator &QHash<Key, T>::iterator::operator++()
2745
2746	The prefix ++ operator (\c{++i}) advances the iterator to the
2747	next item in the hash and returns an iterator to the new current
2748	item.
2749
2750	Calling this function on QHash::end() leads to undefined results.
2751	*/
2752
2753	/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::iterator::operator++(int)
2754
2755	\overload
2756
2757	The postfix ++ operator (\c{i++}) advances the iterator to the
2758	next item in the hash and returns an iterator to the previously
2759	current item.
2760	*/
2761
2762	/*! \class QHash::const_iterator
2763	\inmodule QtCore
2764	\brief The QHash::const_iterator class provides an STL-style const iterator for QHash.
2765
2766	QHash\<Key, T\>::const_iterator allows you to iterate over a
2767	QHash. If you want to modify the QHash as you
2768	iterate over it, you must use QHash::iterator instead. It is
2769	generally good practice to use QHash::const_iterator on a
2770	non-const QHash as well, unless you need to change the QHash
2771	through the iterator. Const iterators are slightly faster, and
2772	can improve code readability.
2773
2774	The default QHash::const_iterator constructor creates an
2775	uninitialized iterator. You must initialize it using a QHash
2776	function like QHash::cbegin(), QHash::cend(), or
2777	QHash::constFind() before you can start iterating. Here's a typical
2778	loop that prints all the (key, value) pairs stored in a hash:
2779
2780	\snippet code/src_corelib_tools_qhash.cpp 23
2781
2782	Unlike QMap, which orders its items by key, QHash stores its
2783	items in an arbitrary order. The only guarantee is that items that
2784	share the same key (because they were inserted using
2785	a QMultiHash) will appear consecutively, from the most
2786	recently to the least recently inserted value.
2787
2788	Multiple iterators can be used on the same hash. However, be aware
2789	that any modification performed directly on the QHash (inserting and
2790	removing items) can cause the iterators to become invalid.
2791
2792	Inserting items into the hash or calling methods such as QHash::reserve()
2793	or QHash::squeeze() can invalidate all iterators pointing into the hash.
2794	Iterators are guaranteed to stay valid only as long as the QHash doesn't have
2795	to grow/shrink its internal hash table.
2796	Using any iterator after a rehashing operation has occurred will lead to undefined behavior.
2797
2798	You can however safely use iterators to remove entries from the hash
2799	using the QHash::erase() method. This function can safely be called while
2800	iterating, and won't affect the order of items in the hash.
2801
2802	\warning Iterators on implicitly shared containers do not work
2803	exactly like STL-iterators. You should avoid copying a container
2804	while iterators are active on that container. For more information,
2805	read \l{Implicit sharing iterator problem}.
2806
2807	\sa QHash::iterator, QHash::key_iterator, QHash::const_key_value_iterator
2808	*/
2809
2810	/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator::const_iterator()
2811
2812	Constructs an uninitialized iterator.
2813
2814	Functions like key(), value(), and operator++() must not be
2815	called on an uninitialized iterator. Use operator=() to assign a
2816	value to it before using it.
2817
2818	\sa QHash::constBegin(), QHash::constEnd()
2819	*/
2820
2821	/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator::const_iterator(const iterator &other)
2822
2823	Constructs a copy of \a other.
2824	*/
2825
2826	/*! \fn template <class Key, class T> const Key &QHash<Key, T>::const_iterator::key() const
2827
2828	Returns the current item's key.
2829
2830	\sa value()
2831	*/
2832
2833	/*! \fn template <class Key, class T> const T &QHash<Key, T>::const_iterator::value() const
2834
2835	Returns the current item's value.
2836
2837	\sa key(), operator*()
2838	*/
2839
2840	/*! \fn template <class Key, class T> const T &QHash<Key, T>::const_iterator::operator*() const
2841
2842	Returns the current item's value.
2843
2844	Same as value().
2845
2846	\sa key()
2847	*/
2848
2849	/*! \fn template <class Key, class T> const T *QHash<Key, T>::const_iterator::operator->() const
2850
2851	Returns a pointer to the current item's value.
2852
2853	\sa value()
2854	*/
2855
2856	/*! \fn template <class Key, class T> bool QHash<Key, T>::const_iterator::operator==(const const_iterator &other) const
2857
2858	Returns \c true if \a other points to the same item as this
2859	iterator; otherwise returns \c false.
2860
2861	\sa operator!=()
2862	*/
2863
2864	/*! \fn template <class Key, class T> bool QHash<Key, T>::const_iterator::operator!=(const const_iterator &other) const
2865
2866	Returns \c true if \a other points to a different item than this
2867	iterator; otherwise returns \c false.
2868
2869	\sa operator==()
2870	*/
2871
2872	/*!
2873	\fn template <class Key, class T> QHash<Key, T>::const_iterator &QHash<Key, T>::const_iterator::operator++()
2874
2875	The prefix ++ operator (\c{++i}) advances the iterator to the
2876	next item in the hash and returns an iterator to the new current
2877	item.
2878
2879	Calling this function on QHash::end() leads to undefined results.
2880	*/
2881
2882	/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::const_iterator::operator++(int)
2883
2884	\overload
2885
2886	The postfix ++ operator (\c{i++}) advances the iterator to the
2887	next item in the hash and returns an iterator to the previously
2888	current item.
2889	*/
2890
2891	/*! \class QHash::key_iterator
2892	\inmodule QtCore
2893	\since 5.6
2894	\brief The QHash::key_iterator class provides an STL-style const iterator for QHash keys.
2895
2896	QHash::key_iterator is essentially the same as QHash::const_iterator
2897	with the difference that operator*() and operator->() return a key
2898	instead of a value.
2899
2900	For most uses QHash::iterator and QHash::const_iterator should be used,
2901	you can easily access the key by calling QHash::iterator::key():
2902
2903	\snippet code/src_corelib_tools_qhash.cpp 27
2904
2905	However, to have interoperability between QHash's keys and STL-style
2906	algorithms we need an iterator that dereferences to a key instead
2907	of a value. With QHash::key_iterator we can apply an algorithm to a
2908	range of keys without having to call QHash::keys(), which is inefficient
2909	as it costs one QHash iteration and memory allocation to create a temporary
2910	QList.
2911
2912	\snippet code/src_corelib_tools_qhash.cpp 28
2913
2914	QHash::key_iterator is const, it's not possible to modify the key.
2915
2916	The default QHash::key_iterator constructor creates an uninitialized
2917	iterator. You must initialize it using a QHash function like
2918	QHash::keyBegin() or QHash::keyEnd().
2919
2920	\warning Iterators on implicitly shared containers do not work
2921	exactly like STL-iterators. You should avoid copying a container
2922	while iterators are active on that container. For more information,
2923	read \l{Implicit sharing iterator problem}.
2924
2925	\sa QHash::const_iterator, QHash::iterator
2926	*/
2927
2928	/*! \fn template <class Key, class T> const T &QHash<Key, T>::key_iterator::operator*() const
2929
2930	Returns the current item's key.
2931	*/
2932
2933	/*! \fn template <class Key, class T> const T *QHash<Key, T>::key_iterator::operator->() const
2934
2935	Returns a pointer to the current item's key.
2936	*/
2937
2938	/*! \fn template <class Key, class T> bool QHash<Key, T>::key_iterator::operator==(key_iterator other) const
2939
2940	Returns \c true if \a other points to the same item as this
2941	iterator; otherwise returns \c false.
2942
2943	\sa operator!=()
2944	*/
2945
2946	/*! \fn template <class Key, class T> bool QHash<Key, T>::key_iterator::operator!=(key_iterator other) const
2947
2948	Returns \c true if \a other points to a different item than this
2949	iterator; otherwise returns \c false.
2950
2951	\sa operator==()
2952	*/
2953
2954	/*!
2955	\fn template <class Key, class T> QHash<Key, T>::key_iterator &QHash<Key, T>::key_iterator::operator++()
2956
2957	The prefix ++ operator (\c{++i}) advances the iterator to the
2958	next item in the hash and returns an iterator to the new current
2959	item.
2960
2961	Calling this function on QHash::keyEnd() leads to undefined results.
2962
2963	*/
2964
2965	/*! \fn template <class Key, class T> QHash<Key, T>::key_iterator QHash<Key, T>::key_iterator::operator++(int)
2966
2967	\overload
2968
2969	The postfix ++ operator (\c{i++}) advances the iterator to the
2970	next item in the hash and returns an iterator to the previous
2971	item.
2972	*/
2973
2974	/*! \fn template <class Key, class T> const_iterator QHash<Key, T>::key_iterator::base() const
2975	Returns the underlying const_iterator this key_iterator is based on.
2976	*/
2977
2978	/*! \typedef QHash::const_key_value_iterator
2979	\inmodule QtCore
2980	\since 5.10
2981	\brief The QHash::const_key_value_iterator typedef provides an STL-style const iterator for QHash.
2982
2983	QHash::const_key_value_iterator is essentially the same as QHash::const_iterator
2984	with the difference that operator*() returns a key/value pair instead of a
2985	value.
2986
2987	\sa QKeyValueIterator
2988	*/
2989
2990	/*! \typedef QHash::key_value_iterator
2991	\inmodule QtCore
2992	\since 5.10
2993	\brief The QHash::key_value_iterator typedef provides an STL-style iterator for QHash.
2994
2995	QHash::key_value_iterator is essentially the same as QHash::iterator
2996	with the difference that operator*() returns a key/value pair instead of a
2997	value.
2998
2999	\sa QKeyValueIterator
3000	*/
3001
3002	/*! \fn template <class Key, class T> QDataStream &operator<<(QDataStream &out, const QHash<Key, T>& hash)
3003	\relates QHash
3004
3005	Writes the hash \a hash to stream \a out.
3006
3007	This function requires the key and value types to implement \c
3008	operator<<().
3009
3010	\sa {Serializing Qt Data Types}
3011	*/
3012
3013	/*! \fn template <class Key, class T> QDataStream &operator>>(QDataStream &in, QHash<Key, T> &hash)
3014	\relates QHash
3015
3016	Reads a hash from stream \a in into \a hash.
3017
3018	This function requires the key and value types to implement \c
3019	operator>>().
3020
3021	\sa {Serializing Qt Data Types}
3022	*/
3023
3024	/*! \class QMultiHash
3025	\inmodule QtCore
3026	\brief The QMultiHash class provides a multi-valued hash table.
3027	\compares equality
3028
3029	\ingroup tools
3030	\ingroup shared
3031
3032	\reentrant
3033
3034	QMultiHash\<Key, T\> is one of Qt's generic \l{container classes}.
3035	It provides a hash table that allows multiple values for the same key.
3036
3037	QMultiHash mostly mirrors QHash's API. For example, you can use isEmpty() to test
3038	whether the hash is empty, and you can traverse a QMultiHash using
3039	QHash's iterator classes (for example, QHashIterator). But opposed to
3040	QHash, it provides an insert() function that allows the insertion of
3041	multiple items with the same key. The replace() function corresponds to
3042	QHash::insert(). It also provides convenient operator+() and
3043	operator+=().
3044
3045	Unlike QMultiMap, QMultiHash does not provide ordering of the
3046	inserted items. The only guarantee is that items that
3047	share the same key will appear consecutively, from the most
3048	recently to the least recently inserted value.
3049
3050	Example:
3051	\snippet code/src_corelib_tools_qhash.cpp 24
3052
3053	Unlike QHash, QMultiHash provides no operator[]. Use value() or
3054	replace() if you want to access the most recently inserted item
3055	with a certain key.
3056
3057	If you want to retrieve all the values for a single key, you can
3058	use values(const Key &key), which returns a QList<T>:
3059
3060	\snippet code/src_corelib_tools_qhash.cpp 25
3061
3062	The items that share the same key are available from most
3063	recently to least recently inserted.
3064
3065	A more efficient approach is to call find() to get
3066	the STL-style iterator for the first item with a key and iterate from
3067	there:
3068
3069	\snippet code/src_corelib_tools_qhash.cpp 26
3070
3071	QMultiHash's key and value data types must be \l{assignable data
3072	types}. You cannot, for example, store a QWidget as a value;
3073	instead, store a QWidget *. In addition, QMultiHash's key type
3074	must provide operator==(), and there must also be a qHash() function
3075	in the type's namespace that returns a hash value for an argument of the
3076	key's type. See the QHash documentation for details.
3077
3078	\sa QHash, QHashIterator, QMutableHashIterator, QMultiMap
3079	*/
3080
3081	/*! \fn template <class Key, class T> QMultiHash<Key, T>::QMultiHash()
3082
3083	Constructs an empty hash.
3084	*/
3085
3086	/*! \fn template <class Key, class T> QMultiHash<Key, T>::QMultiHash(std::initializer_list<std::pair<Key,T> > list)
3087	\since 5.1
3088
3089	Constructs a multi-hash with a copy of each of the elements in the
3090	initializer list \a list.
3091	*/
3092
3093	/*! \fn template <class Key, class T> QMultiHash<Key, T>::QMultiHash(const QHash<Key, T> &other)
3094
3095	Constructs a copy of \a other (which can be a QHash or a
3096	QMultiHash).
3097	*/
3098
3099	/*! \fn template <class Key, class T> template <class InputIterator> QMultiHash<Key, T>::QMultiHash(InputIterator begin, InputIterator end)
3100	\since 5.14
3101
3102	Constructs a multi-hash with a copy of each of the elements in the iterator range
3103	[\a begin, \a end). Either the elements iterated by the range must be
3104	objects with \c{first} and \c{second} data members (like \c{std::pair}),
3105	convertible to \c Key and to \c T respectively; or the
3106	iterators must have \c{key()} and \c{value()} member functions, returning a
3107	key convertible to \c Key and a value convertible to \c T respectively.
3108	*/
3109
3110	/*! \fn template <class Key, class T> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::replace(const Key &key, const T &value)
3111
3112	Inserts a new item with the \a key and a value of \a value.
3113
3114	If there is already an item with the \a key, that item's value
3115	is replaced with \a value.
3116
3117	If there are multiple items with the \a key, the most
3118	recently inserted item's value is replaced with \a value.
3119
3120	Returns an iterator pointing to the new/updated element.
3121
3122	\include qhash.cpp qhash-iterator-invalidation-func-desc
3123
3124	\sa insert()
3125	*/
3126
3127	/*! \fn template <class Key, class T> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::insert(const Key &key, const T &value)
3128
3129	Inserts a new item with the \a key and a value of \a value.
3130
3131	If there is already an item with the same key in the hash, this
3132	function will simply create a new one. (This behavior is
3133	different from replace(), which overwrites the value of an
3134	existing item.)
3135
3136	Returns an iterator pointing to the new element.
3137
3138	\include qhash.cpp qhash-iterator-invalidation-func-desc
3139
3140	\sa replace()
3141	*/
3142
3143	/*!
3144	\fn template <class Key, class T> template <typename ...Args> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::emplace(const Key &key, Args&&... args)
3145	\fn template <class Key, class T> template <typename ...Args> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::emplace(Key &&key, Args&&... args)
3146
3147	Inserts a new element into the container. This new element
3148	is constructed in-place using \a args as the arguments for its
3149	construction.
3150
3151	If there is already an item with the same key in the hash, this
3152	function will simply create a new one. (This behavior is
3153	different from replace(), which overwrites the value of an
3154	existing item.)
3155
3156	Returns an iterator pointing to the new element.
3157
3158	\include qhash.cpp qhash-iterator-invalidation-func-desc
3159
3160	\sa insert
3161	*/
3162
3163	/*!
3164	\fn template <class Key, class T> template <typename ...Args> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::emplaceReplace(const Key &key, Args&&... args)
3165	\fn template <class Key, class T> template <typename ...Args> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::emplaceReplace(Key &&key, Args&&... args)
3166
3167	Inserts a new element into the container. This new element
3168	is constructed in-place using \a args as the arguments for its
3169	construction.
3170
3171	If there is already an item with the same key in the hash, that item's
3172	value is replaced with a value constructed from \a args.
3173
3174	Returns an iterator pointing to the new element.
3175
3176	\include qhash.cpp qhash-iterator-invalidation-func-desc
3177
3178	\sa replace, emplace
3179	*/
3180
3181	/*! \fn template <class Key, class T> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::erase(const_iterator pos)
3182	\since 5.7
3183
3184	Removes the (key, value) pair associated with the iterator \a pos
3185	from the hash, and returns an iterator to the next item in the
3186	hash.
3187
3188	This function never causes QMultiHash to
3189	rehash its internal data structure. This means that it can safely
3190	be called while iterating, and won't affect the order of items in
3191	the hash. For example:
3192
3193	\snippet code/src_corelib_tools_qhash.cpp 15multihash
3194
3195	\include qhash.cpp qhash-iterator-invalidation-func-desc
3196
3197	\sa remove(), take(), find()
3198	*/
3199
3200	/*! \fn template <class Key, class T> QMultiHash &QMultiHash<Key, T>::unite(const QMultiHash &other)
3201	\since 5.13
3202
3203	Inserts all the items in the \a other hash into this hash
3204	and returns a reference to this hash.
3205
3206	\sa insert()
3207	*/
3208
3209
3210	/*! \fn template <class Key, class T> QMultiHash &QMultiHash<Key, T>::unite(const QHash<Key, T> &other)
3211	\since 6.0
3212
3213	Inserts all the items in the \a other hash into this hash
3214	and returns a reference to this hash.
3215
3216	\sa insert()
3217	*/
3218
3219	/*! \fn template <class Key, class T> QList<Key> QMultiHash<Key, T>::uniqueKeys() const
3220	\since 5.13
3221
3222	Returns a list containing all the keys in the map. Keys that occur multiple
3223	times in the map occur only once in the returned list.
3224
3225	\sa keys(), values()
3226	*/
3227
3228	/*! \fn template <class Key, class T> T QMultiHash<Key, T>::value(const Key &key) const
3229	\fn template <class Key, class T> T QMultiHash<Key, T>::value(const Key &key, const T &defaultValue) const
3230
3231	Returns the value associated with the \a key.
3232
3233	If the hash contains no item with the \a key, the function
3234	returns \a defaultValue, or a \l{default-constructed value} if this
3235	parameter has not been supplied.
3236
3237	If there are multiple
3238	items for the \a key in the hash, the value of the most recently
3239	inserted one is returned.
3240	*/
3241
3242	/*! \fn template <class Key, class T> QList<T> QMultiHash<Key, T>::values(const Key &key) const
3243	\overload
3244
3245	Returns a list of all the values associated with the \a key,
3246	from the most recently inserted to the least recently inserted.
3247
3248	\sa count(), insert()
3249	*/
3250
3251	/*! \fn template <class Key, class T> T &QMultiHash<Key, T>::operator[](const Key &key)
3252
3253	Returns the value associated with the \a key as a modifiable reference.
3254
3255	If the hash contains no item with the \a key, the function inserts
3256	a \l{default-constructed value} into the hash with the \a key, and
3257	returns a reference to it.
3258
3259	If the hash contains multiple items with the \a key, this function returns
3260	a reference to the most recently inserted value.
3261
3262	\include qhash.cpp qhash-iterator-invalidation-func-desc
3263
3264	\sa insert(), value()
3265	*/
3266
3267	/*!
3268	\fn template <class Key, class T> bool QMultiHash<Key, T>::operator==(const QMultiHash &lhs, const QMultiHash &rhs)
3269
3270	Returns \c true if \a lhs multihash equals to the \a rhs multihash;
3271	otherwise returns \c false.
3272
3273	Two multihashes are considered equal if they contain the same (key, value)
3274	pairs.
3275
3276	This function requires the value type to implement \c {operator==()}.
3277
3278	\sa operator!=()
3279	*/
3280
3281	/*!
3282	\fn template <class Key, class T> bool QMultiHash<Key, T>::operator!=(const QMultiHash &lhs, const QMultiHash &rhs)
3283
3284	Returns \c true if \a lhs multihash is not equal to the \a rhs multihash;
3285	otherwise returns \c false.
3286
3287	Two multihashes are considered equal if they contain the same (key, value)
3288	pairs.
3289
3290	This function requires the value type to implement \c {operator==()}.
3291
3292	\sa operator==()
3293	*/
3294
3295	/*! \fn template <class Key, class T> QMultiHash &QMultiHash<Key, T>::operator+=(const QMultiHash &other)
3296
3297	Inserts all the items in the \a other hash into this hash
3298	and returns a reference to this hash.
3299
3300	\sa unite(), insert()
3301	*/
3302
3303	/*! \fn template <class Key, class T> QMultiHash QMultiHash<Key, T>::operator+(const QMultiHash &other) const
3304
3305	Returns a hash that contains all the items in this hash in
3306	addition to all the items in \a other. If a key is common to both
3307	hashes, the resulting hash will contain the key multiple times.
3308
3309	\sa operator+=()
3310	*/
3311
3312	/*!
3313	\fn template <class Key, class T> bool QMultiHash<Key, T>::contains(const Key &key, const T &value) const
3314	\since 4.3
3315
3316	Returns \c true if the hash contains an item with the \a key and
3317	\a value; otherwise returns \c false.
3318
3319	\sa contains()
3320	*/
3321
3322	/*!
3323	\fn template <class Key, class T> qsizetype QMultiHash<Key, T>::remove(const Key &key)
3324	\since 4.3
3325
3326	Removes all the items that have the \a key from the hash.
3327	Returns the number of items removed.
3328
3329	\sa remove()
3330	*/
3331
3332	/*!
3333	\fn template <class Key, class T> qsizetype QMultiHash<Key, T>::remove(const Key &key, const T &value)
3334	\since 4.3
3335
3336	Removes all the items that have the \a key and the value \a
3337	value from the hash. Returns the number of items removed.
3338
3339	\sa remove()
3340	*/
3341
3342	/*!
3343	\fn template <class Key, class T> void QMultiHash<Key, T>::clear()
3344	\since 4.3
3345
3346	Removes all items from the hash and frees up all memory used by it.
3347
3348	\sa remove()
3349	*/
3350
3351	/*! \fn template <class Key, class T> template <typename Predicate> qsizetype QMultiHash<Key, T>::removeIf(Predicate pred)
3352	\since 6.1
3353
3354	Removes all elements for which the predicate \a pred returns true
3355	from the multi hash.
3356
3357	The function supports predicates which take either an argument of
3358	type \c{QMultiHash<Key, T>::iterator}, or an argument of type
3359	\c{std::pair<const Key &, T &>}.
3360
3361	Returns the number of elements removed, if any.
3362
3363	\sa clear(), take()
3364	*/
3365
3366	/*! \fn template <class Key, class T> T QMultiHash<Key, T>::take(const Key &key)
3367
3368	Removes the item with the \a key from the hash and returns
3369	the value associated with it.
3370
3371	If the item does not exist in the hash, the function simply
3372	returns a \l{default-constructed value}. If there are multiple
3373	items for \a key in the hash, only the most recently inserted one
3374	is removed.
3375
3376	If you don't use the return value, remove() is more efficient.
3377
3378	\sa remove()
3379	*/
3380
3381	/*! \fn template <class Key, class T> QList<Key> QMultiHash<Key, T>::keys() const
3382
3383	Returns a list containing all the keys in the hash, in an
3384	arbitrary order. Keys that occur multiple times in the hash
3385	also occur multiple times in the list.
3386
3387	The order is guaranteed to be the same as that used by values().
3388
3389	This function creates a new list, in \l {linear time}. The time and memory
3390	use that entails can be avoided by iterating from \l keyBegin() to
3391	\l keyEnd().
3392
3393	\sa values(), key()
3394	*/
3395
3396	/*! \fn template <class Key, class T> QList<T> QMultiHash<Key, T>::values() const
3397
3398	Returns a list containing all the values in the hash, in an
3399	arbitrary order. If a key is associated with multiple values, all of
3400	its values will be in the list, and not just the most recently
3401	inserted one.
3402
3403	The order is guaranteed to be the same as that used by keys().
3404
3405	This function creates a new list, in \l {linear time}. The time and memory
3406	use that entails can be avoided by iterating from \l keyValueBegin() to
3407	\l keyValueEnd().
3408
3409	\sa keys(), value()
3410	*/
3411
3412	/*!
3413	\fn template <class Key, class T> Key QMultiHash<Key, T>::key(const T &value) const
3414	\fn template <class Key, class T> Key QMultiHash<Key, T>::key(const T &value, const Key &defaultKey) const
3415	\since 4.3
3416
3417	Returns the first key mapped to \a value. If the hash contains no item
3418	mapped to \a value, returns \a defaultKey, or a \l{default-constructed
3419	value}{default-constructed key} if this parameter has not been supplied.
3420
3421	This function can be slow (\l{linear time}), because QMultiHash's
3422	internal data structure is optimized for fast lookup by key, not
3423	by value.
3424	*/
3425
3426	/*!
3427	\fn template <class Key, class T> qsizetype QMultiHash<Key, T>::count(const Key &key, const T &value) const
3428	\since 4.3
3429
3430	Returns the number of items with the \a key and \a value.
3431
3432	\sa count()
3433	*/
3434
3435	/*!
3436	\fn template <class Key, class T> typename QMultiHash<Key, T>::iterator QMultiHash<Key, T>::find(const Key &key, const T &value)
3437	\since 4.3
3438
3439	Returns an iterator pointing to the item with the \a key and \a value.
3440	If the hash contains no such item, the function returns end().
3441
3442	If the hash contains multiple items with the \a key and \a value, the
3443	iterator returned points to the most recently inserted item.
3444
3445	\include qhash.cpp qhash-iterator-invalidation-func-desc
3446	*/
3447
3448	/*!
3449	\fn template <class Key, class T> typename QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::find(const Key &key, const T &value) const
3450	\since 4.3
3451	\overload
3452
3453	\include qhash.cpp qhash-iterator-invalidation-func-desc
3454	*/
3455
3456	/*!
3457	\fn template <class Key, class T> typename QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::constFind(const Key &key, const T &value) const
3458	\since 4.3
3459
3460	Returns an iterator pointing to the item with the \a key and the
3461	\a value in the hash.
3462
3463	If the hash contains no such item, the function returns
3464	constEnd().
3465
3466	\include qhash.cpp qhash-iterator-invalidation-func-desc
3467	*/
3468
3469	/*! \fn template <class Key, class T> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::begin()
3470
3471	Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first item in
3472	the hash.
3473
3474	\include qhash.cpp qhash-iterator-invalidation-func-desc
3475
3476	\sa constBegin(), end()
3477	*/
3478
3479	/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::begin() const
3480
3481	\overload
3482
3483	\include qhash.cpp qhash-iterator-invalidation-func-desc
3484	*/
3485
3486	/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::cbegin() const
3487	\since 5.0
3488
3489	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item
3490	in the hash.
3491
3492	\include qhash.cpp qhash-iterator-invalidation-func-desc
3493
3494	\sa begin(), cend()
3495	*/
3496
3497	/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::constBegin() const
3498
3499	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item
3500	in the hash.
3501
3502	\include qhash.cpp qhash-iterator-invalidation-func-desc
3503
3504	\sa begin(), constEnd()
3505	*/
3506
3507	/*! \fn template <class Key, class T> QMultiHash<Key, T>::key_iterator QMultiHash<Key, T>::keyBegin() const
3508	\since 5.6
3509
3510	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first key
3511	in the hash.
3512
3513	\include qhash.cpp qhash-iterator-invalidation-func-desc
3514
3515	\sa keyEnd()
3516	*/
3517
3518	/*! \fn template <class Key, class T> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::end()
3519
3520	Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary item
3521	after the last item in the hash.
3522
3523	\include qhash.cpp qhash-iterator-invalidation-func-desc
3524
3525	\sa begin(), constEnd()
3526	*/
3527
3528	/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::end() const
3529
3530	\overload
3531	*/
3532
3533	/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::constEnd() const
3534
3535	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
3536	item after the last item in the hash.
3537
3538	\include qhash.cpp qhash-iterator-invalidation-func-desc
3539
3540	\sa constBegin(), end()
3541	*/
3542
3543	/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::cend() const
3544	\since 5.0
3545
3546	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
3547	item after the last item in the hash.
3548
3549	\include qhash.cpp qhash-iterator-invalidation-func-desc
3550
3551	\sa cbegin(), end()
3552	*/
3553
3554	/*! \fn template <class Key, class T> QMultiHash<Key, T>::key_iterator QMultiHash<Key, T>::keyEnd() const
3555	\since 5.6
3556
3557	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
3558	item after the last key in the hash.
3559
3560	\include qhash.cpp qhash-iterator-invalidation-func-desc
3561
3562	\sa keyBegin()
3563	*/
3564
3565	/*! \fn template <class Key, class T> QMultiHash<Key, T>::key_value_iterator QMultiHash<Key, T>::keyValueBegin()
3566	\since 5.10
3567
3568	Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first entry
3569	in the hash.
3570
3571	\include qhash.cpp qhash-iterator-invalidation-func-desc
3572
3573	\sa keyValueEnd()
3574	*/
3575
3576	/*! \fn template <class Key, class T> QMultiHash<Key, T>::key_value_iterator QMultiHash<Key, T>::keyValueEnd()
3577	\since 5.10
3578
3579	Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
3580	entry after the last entry in the hash.
3581
3582	\include qhash.cpp qhash-iterator-invalidation-func-desc
3583
3584	\sa keyValueBegin()
3585	*/
3586
3587	/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_key_value_iterator QMultiHash<Key, T>::keyValueBegin() const
3588	\since 5.10
3589
3590	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry
3591	in the hash.
3592
3593	\include qhash.cpp qhash-iterator-invalidation-func-desc
3594
3595	\sa keyValueEnd()
3596	*/
3597
3598	/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_key_value_iterator QMultiHash<Key, T>::constKeyValueBegin() const
3599	\since 5.10
3600
3601	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry
3602	in the hash.
3603
3604	\include qhash.cpp qhash-iterator-invalidation-func-desc
3605
3606	\sa keyValueBegin()
3607	*/
3608
3609	/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_key_value_iterator QMultiHash<Key, T>::keyValueEnd() const
3610	\since 5.10
3611
3612	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
3613	entry after the last entry in the hash.
3614
3615	\include qhash.cpp qhash-iterator-invalidation-func-desc
3616
3617	\sa keyValueBegin()
3618	*/
3619
3620	/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_key_value_iterator QMultiHash<Key, T>::constKeyValueEnd() const
3621	\since 5.10
3622
3623	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
3624	entry after the last entry in the hash.
3625
3626	\include qhash.cpp qhash-iterator-invalidation-func-desc
3627
3628	\sa constKeyValueBegin()
3629	*/
3630
3631	/*! \fn template <class Key, class T> auto QMultiHash<Key, T>::asKeyValueRange() &
3632	\fn template <class Key, class T> auto QMultiHash<Key, T>::asKeyValueRange() const &
3633	\fn template <class Key, class T> auto QMultiHash<Key, T>::asKeyValueRange() &&
3634	\fn template <class Key, class T> auto QMultiHash<Key, T>::asKeyValueRange() const &&
3635	\since 6.4
3636
3637	Returns a range object that allows iteration over this hash as
3638	key/value pairs. For instance, this range object can be used in a
3639	range-based for loop, in combination with a structured binding declaration:
3640
3641	\snippet code/src_corelib_tools_qhash.cpp 35
3642
3643	Note that both the key and the value obtained this way are
3644	references to the ones in the hash. Specifically, mutating the value
3645	will modify the hash itself.
3646
3647	\include qhash.cpp qhash-iterator-invalidation-func-desc
3648
3649	\sa QKeyValueIterator
3650	*/
3651
3652	/*! \class QMultiHash::iterator
3653	\inmodule QtCore
3654	\brief The QMultiHash::iterator class provides an STL-style non-const iterator for QMultiHash.
3655
3656	QMultiHash\<Key, T\>::iterator allows you to iterate over a QMultiHash
3657	and to modify the value (but not the key) associated
3658	with a particular key. If you want to iterate over a const QMultiHash,
3659	you should use QMultiHash::const_iterator. It is generally good
3660	practice to use QMultiHash::const_iterator on a non-const QMultiHash as
3661	well, unless you need to change the QMultiHash through the iterator.
3662	Const iterators are slightly faster, and can improve code
3663	readability.
3664
3665	The default QMultiHash::iterator constructor creates an uninitialized
3666	iterator. You must initialize it using a QMultiHash function like
3667	QMultiHash::begin(), QMultiHash::end(), or QMultiHash::find() before you can
3668	start iterating. Here's a typical loop that prints all the (key,
3669	value) pairs stored in a hash:
3670
3671	\snippet code/src_corelib_tools_qhash.cpp 17
3672
3673	Unlike QMap, which orders its items by key, QMultiHash stores its
3674	items in an arbitrary order.
3675
3676	Here's an example that increments every value stored in the QMultiHash
3677	by 2:
3678
3679	\snippet code/src_corelib_tools_qhash.cpp 18
3680
3681	To remove elements from a QMultiHash you can use erase_if(QMultiHash\<Key, T\> &map, Predicate pred):
3682
3683	\snippet code/src_corelib_tools_qhash.cpp 21
3684
3685	Multiple iterators can be used on the same hash. However, be aware
3686	that any modification performed directly on the QHash (inserting and
3687	removing items) can cause the iterators to become invalid.
3688
3689	Inserting items into the hash or calling methods such as QHash::reserve()
3690	or QHash::squeeze() can invalidate all iterators pointing into the hash.
3691	Iterators are guaranteed to stay valid only as long as the QHash doesn't have
3692	to grow/shrink its internal hash table.
3693	Using any iterator after a rehashing operation has occurred will lead to undefined behavior.
3694
3695	If you need to keep iterators over a long period of time, we recommend
3696	that you use QMultiMap rather than QHash.
3697
3698	\warning Iterators on implicitly shared containers do not work
3699	exactly like STL-iterators. You should avoid copying a container
3700	while iterators are active on that container. For more information,
3701	read \l{Implicit sharing iterator problem}.
3702
3703	\sa QMultiHash::const_iterator, QMultiHash::key_iterator, QMultiHash::key_value_iterator
3704	*/
3705
3706	/*! \fn template <class Key, class T> QMultiHash<Key, T>::iterator::iterator()
3707
3708	Constructs an uninitialized iterator.
3709
3710	Functions like key(), value(), and operator++() must not be
3711	called on an uninitialized iterator. Use operator=() to assign a
3712	value to it before using it.
3713
3714	\sa QMultiHash::begin(), QMultiHash::end()
3715	*/
3716
3717	/*! \fn template <class Key, class T> const Key &QMultiHash<Key, T>::iterator::key() const
3718
3719	Returns the current item's key as a const reference.
3720
3721	There is no direct way of changing an item's key through an
3722	iterator, although it can be done by calling QMultiHash::erase()
3723	followed by QMultiHash::insert().
3724
3725	\sa value()
3726	*/
3727
3728	/*! \fn template <class Key, class T> T &QMultiHash<Key, T>::iterator::value() const
3729
3730	Returns a modifiable reference to the current item's value.
3731
3732	You can change the value of an item by using value() on
3733	the left side of an assignment, for example:
3734
3735	\snippet code/src_corelib_tools_qhash.cpp 22
3736
3737	\sa key(), operator*()
3738	*/
3739
3740	/*! \fn template <class Key, class T> T &QMultiHash<Key, T>::iterator::operator*() const
3741
3742	Returns a modifiable reference to the current item's value.
3743
3744	Same as value().
3745
3746	\sa key()
3747	*/
3748
3749	/*! \fn template <class Key, class T> T *QMultiHash<Key, T>::iterator::operator->() const
3750
3751	Returns a pointer to the current item's value.
3752
3753	\sa value()
3754	*/
3755
3756	/*!
3757	\fn template <class Key, class T> bool QMultiHash<Key, T>::iterator::operator==(const iterator &other) const
3758	\fn template <class Key, class T> bool QMultiHash<Key, T>::iterator::operator==(const const_iterator &other) const
3759
3760	Returns \c true if \a other points to the same item as this
3761	iterator; otherwise returns \c false.
3762
3763	\sa operator!=()
3764	*/
3765
3766	/*!
3767	\fn template <class Key, class T> bool QMultiHash<Key, T>::iterator::operator!=(const iterator &other) const
3768	\fn template <class Key, class T> bool QMultiHash<Key, T>::iterator::operator!=(const const_iterator &other) const
3769
3770	Returns \c true if \a other points to a different item than this
3771	iterator; otherwise returns \c false.
3772
3773	\sa operator==()
3774	*/
3775
3776	/*!
3777	\fn template <class Key, class T> QMultiHash<Key, T>::iterator &QMultiHash<Key, T>::iterator::operator++()
3778
3779	The prefix ++ operator (\c{++i}) advances the iterator to the
3780	next item in the hash and returns an iterator to the new current
3781	item.
3782
3783	Calling this function on QMultiHash::end() leads to undefined results.
3784	*/
3785
3786	/*! \fn template <class Key, class T> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::iterator::operator++(int)
3787
3788	\overload
3789
3790	The postfix ++ operator (\c{i++}) advances the iterator to the
3791	next item in the hash and returns an iterator to the previously
3792	current item.
3793	*/
3794
3795	/*! \class QMultiHash::const_iterator
3796	\inmodule QtCore
3797	\brief The QMultiHash::const_iterator class provides an STL-style const iterator for QMultiHash.
3798
3799	QMultiHash\<Key, T\>::const_iterator allows you to iterate over a
3800	QMultiHash. If you want to modify the QMultiHash as you
3801	iterate over it, you must use QMultiHash::iterator instead. It is
3802	generally good practice to use QMultiHash::const_iterator on a
3803	non-const QMultiHash as well, unless you need to change the QMultiHash
3804	through the iterator. Const iterators are slightly faster, and
3805	can improve code readability.
3806
3807	The default QMultiHash::const_iterator constructor creates an
3808	uninitialized iterator. You must initialize it using a QMultiHash
3809	function like QMultiHash::cbegin(), QMultiHash::cend(), or
3810	QMultiHash::constFind() before you can start iterating. Here's a typical
3811	loop that prints all the (key, value) pairs stored in a hash:
3812
3813	\snippet code/src_corelib_tools_qhash.cpp 23
3814
3815	Unlike QMap, which orders its items by key, QMultiHash stores its
3816	items in an arbitrary order. The only guarantee is that items that
3817	share the same key (because they were inserted using
3818	a QMultiHash) will appear consecutively, from the most
3819	recently to the least recently inserted value.
3820
3821	Multiple iterators can be used on the same hash. However, be aware
3822	that any modification performed directly on the QMultiHash (inserting and
3823	removing items) can cause the iterators to become invalid.
3824
3825	Inserting items into the hash or calling methods such as QMultiHash::reserve()
3826	or QMultiHash::squeeze() can invalidate all iterators pointing into the hash.
3827	Iterators are guaranteed to stay valid only as long as the QMultiHash doesn't have
3828	to grow/shrink it's internal hash table.
3829	Using any iterator after a rehashing operation ahs occurred will lead to undefined behavior.
3830
3831	If you need to keep iterators over a long period of time, we recommend
3832	that you use QMultiMap rather than QMultiHash.
3833
3834	\warning Iterators on implicitly shared containers do not work
3835	exactly like STL-iterators. You should avoid copying a container
3836	while iterators are active on that container. For more information,
3837	read \l{Implicit sharing iterator problem}.
3838
3839	\sa QMultiHash::iterator, QMultiHash::key_iterator, QMultiHash::const_key_value_iterator
3840	*/
3841
3842	/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator::const_iterator()
3843
3844	Constructs an uninitialized iterator.
3845
3846	Functions like key(), value(), and operator++() must not be
3847	called on an uninitialized iterator. Use operator=() to assign a
3848	value to it before using it.
3849
3850	\sa QMultiHash::constBegin(), QMultiHash::constEnd()
3851	*/
3852
3853	/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator::const_iterator(const iterator &other)
3854
3855	Constructs a copy of \a other.
3856	*/
3857
3858	/*! \fn template <class Key, class T> const Key &QMultiHash<Key, T>::const_iterator::key() const
3859
3860	Returns the current item's key.
3861
3862	\sa value()
3863	*/
3864
3865	/*! \fn template <class Key, class T> const T &QMultiHash<Key, T>::const_iterator::value() const
3866
3867	Returns the current item's value.
3868
3869	\sa key(), operator*()
3870	*/
3871
3872	/*! \fn template <class Key, class T> const T &QMultiHash<Key, T>::const_iterator::operator*() const
3873
3874	Returns the current item's value.
3875
3876	Same as value().
3877
3878	\sa key()
3879	*/
3880
3881	/*! \fn template <class Key, class T> const T *QMultiHash<Key, T>::const_iterator::operator->() const
3882
3883	Returns a pointer to the current item's value.
3884
3885	\sa value()
3886	*/
3887
3888	/*! \fn template <class Key, class T> bool QMultiHash<Key, T>::const_iterator::operator==(const const_iterator &other) const
3889
3890	Returns \c true if \a other points to the same item as this
3891	iterator; otherwise returns \c false.
3892
3893	\sa operator!=()
3894	*/
3895
3896	/*! \fn template <class Key, class T> bool QMultiHash<Key, T>::const_iterator::operator!=(const const_iterator &other) const
3897
3898	Returns \c true if \a other points to a different item than this
3899	iterator; otherwise returns \c false.
3900
3901	\sa operator==()
3902	*/
3903
3904	/*!
3905	\fn template <class Key, class T> QMultiHash<Key, T>::const_iterator &QMultiHash<Key, T>::const_iterator::operator++()
3906
3907	The prefix ++ operator (\c{++i}) advances the iterator to the
3908	next item in the hash and returns an iterator to the new current
3909	item.
3910
3911	Calling this function on QMultiHash::end() leads to undefined results.
3912	*/
3913
3914	/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::const_iterator::operator++(int)
3915
3916	\overload
3917
3918	The postfix ++ operator (\c{i++}) advances the iterator to the
3919	next item in the hash and returns an iterator to the previously
3920	current item.
3921	*/
3922
3923	/*! \class QMultiHash::key_iterator
3924	\inmodule QtCore
3925	\since 5.6
3926	\brief The QMultiHash::key_iterator class provides an STL-style const iterator for QMultiHash keys.
3927
3928	QMultiHash::key_iterator is essentially the same as QMultiHash::const_iterator
3929	with the difference that operator*() and operator->() return a key
3930	instead of a value.
3931
3932	For most uses QMultiHash::iterator and QMultiHash::const_iterator should be used,
3933	you can easily access the key by calling QMultiHash::iterator::key():
3934
3935	\snippet code/src_corelib_tools_qhash.cpp 27
3936
3937	However, to have interoperability between QMultiHash's keys and STL-style
3938	algorithms we need an iterator that dereferences to a key instead
3939	of a value. With QMultiHash::key_iterator we can apply an algorithm to a
3940	range of keys without having to call QMultiHash::keys(), which is inefficient
3941	as it costs one QMultiHash iteration and memory allocation to create a temporary
3942	QList.
3943
3944	\snippet code/src_corelib_tools_qhash.cpp 28
3945
3946	QMultiHash::key_iterator is const, it's not possible to modify the key.
3947
3948	The default QMultiHash::key_iterator constructor creates an uninitialized
3949	iterator. You must initialize it using a QMultiHash function like
3950	QMultiHash::keyBegin() or QMultiHash::keyEnd().
3951
3952	\warning Iterators on implicitly shared containers do not work
3953	exactly like STL-iterators. You should avoid copying a container
3954	while iterators are active on that container. For more information,
3955	read \l{Implicit sharing iterator problem}.
3956
3957	\sa QMultiHash::const_iterator, QMultiHash::iterator
3958	*/
3959
3960	/*! \fn template <class Key, class T> const T &QMultiHash<Key, T>::key_iterator::operator*() const
3961
3962	Returns the current item's key.
3963	*/
3964
3965	/*! \fn template <class Key, class T> const T *QMultiHash<Key, T>::key_iterator::operator->() const
3966
3967	Returns a pointer to the current item's key.
3968	*/
3969
3970	/*! \fn template <class Key, class T> bool QMultiHash<Key, T>::key_iterator::operator==(key_iterator other) const
3971
3972	Returns \c true if \a other points to the same item as this
3973	iterator; otherwise returns \c false.
3974
3975	\sa operator!=()
3976	*/
3977
3978	/*! \fn template <class Key, class T> bool QMultiHash<Key, T>::key_iterator::operator!=(key_iterator other) const
3979
3980	Returns \c true if \a other points to a different item than this
3981	iterator; otherwise returns \c false.
3982
3983	\sa operator==()
3984	*/
3985
3986	/*!
3987	\fn template <class Key, class T> QMultiHash<Key, T>::key_iterator &QMultiHash<Key, T>::key_iterator::operator++()
3988
3989	The prefix ++ operator (\c{++i}) advances the iterator to the
3990	next item in the hash and returns an iterator to the new current
3991	item.
3992
3993	Calling this function on QMultiHash::keyEnd() leads to undefined results.
3994	*/
3995
3996	/*! \fn template <class Key, class T> QMultiHash<Key, T>::key_iterator QMultiHash<Key, T>::key_iterator::operator++(int)
3997
3998	\overload
3999
4000	The postfix ++ operator (\c{i++}) advances the iterator to the
4001	next item in the hash and returns an iterator to the previous
4002	item.
4003	*/
4004
4005	/*! \fn template <class Key, class T> const_iterator QMultiHash<Key, T>::key_iterator::base() const
4006	Returns the underlying const_iterator this key_iterator is based on.
4007	*/
4008
4009	/*! \typedef QMultiHash::const_key_value_iterator
4010	\inmodule QtCore
4011	\since 5.10
4012	\brief The QMultiHash::const_key_value_iterator typedef provides an STL-style const iterator for QMultiHash.
4013
4014	QMultiHash::const_key_value_iterator is essentially the same as QMultiHash::const_iterator
4015	with the difference that operator*() returns a key/value pair instead of a
4016	value.
4017
4018	\sa QKeyValueIterator
4019	*/
4020
4021	/*! \typedef QMultiHash::key_value_iterator
4022	\inmodule QtCore
4023	\since 5.10
4024	\brief The QMultiHash::key_value_iterator typedef provides an STL-style iterator for QMultiHash.
4025
4026	QMultiHash::key_value_iterator is essentially the same as QMultiHash::iterator
4027	with the difference that operator*() returns a key/value pair instead of a
4028	value.
4029
4030	\sa QKeyValueIterator
4031	*/
4032
4033	/*! \fn template <class Key, class T> QDataStream &operator<<(QDataStream &out, const QMultiHash<Key, T>& hash)
4034	\relates QMultiHash
4035
4036	Writes the hash \a hash to stream \a out.
4037
4038	This function requires the key and value types to implement \c
4039	operator<<().
4040
4041	\sa {Serializing Qt Data Types}
4042	*/
4043
4044	/*! \fn template <class Key, class T> QDataStream &operator>>(QDataStream &in, QMultiHash<Key, T> &hash)
4045	\relates QMultiHash
4046
4047	Reads a hash from stream \a in into \a hash.
4048
4049	This function requires the key and value types to implement \c
4050	operator>>().
4051
4052	\sa {Serializing Qt Data Types}
4053	*/
4054
4055	/*!
4056	\fn template <class Key, class T> size_t qHash(const QHash<Key, T> &key, size_t seed = 0)
4057	\since 5.8
4058	\qhasholdTS{QHash}{Key}{T}
4059	*/
4060
4061	/*!
4062	\fn template <class Key, class T> size_t qHash(const QMultiHash<Key, T> &key, size_t seed = 0)
4063	\since 5.8
4064	\qhasholdTS{QMultiHash}{Key}{T}
4065	*/
4066
4067	/*! \fn template <typename Key, typename T, typename Predicate> qsizetype erase_if(QHash<Key, T> &hash, Predicate pred)
4068	\relates QHash
4069	\since 6.1
4070
4071	Removes all elements for which the predicate \a pred returns true
4072	from the hash \a hash.
4073
4074	The function supports predicates which take either an argument of
4075	type \c{QHash<Key, T>::iterator}, or an argument of type
4076	\c{std::pair<const Key &, T &>}.
4077
4078	Returns the number of elements removed, if any.
4079	*/
4080
4081	/*! \fn template <typename Key, typename T, typename Predicate> qsizetype erase_if(QMultiHash<Key, T> &hash, Predicate pred)
4082	\relates QMultiHash
4083	\since 6.1
4084
4085	Removes all elements for which the predicate \a pred returns true
4086	from the multi hash \a hash.
4087
4088	The function supports predicates which take either an argument of
4089	type \c{QMultiHash<Key, T>::iterator}, or an argument of type
4090	\c{std::pair<const Key &, T &>}.
4091
4092	Returns the number of elements removed, if any.
4093	*/
4094
4095	#ifdef QT_HAS_CONSTEXPR_BITOPS
4096	namespace QHashPrivate {
4097	static_assert(qPopulationCount(v: SpanConstants::NEntries) == 1,
4098	"NEntries must be a power of 2 for bucketForHash() to work.");
4099
4100	// ensure the size of a Span does not depend on the template parameters
4101	using Node1 = Node<int, int>;
4102	static_assert(sizeof(Span<Node1>) == sizeof(Span<Node<char, void *>>));
4103	static_assert(sizeof(Span<Node1>) == sizeof(Span<Node<qsizetype, QHashDummyValue>>));
4104	static_assert(sizeof(Span<Node1>) == sizeof(Span<Node<QString, QVariant>>));
4105	static_assert(sizeof(Span<Node1>) > SpanConstants::NEntries);
4106	static_assert(qNextPowerOfTwo(v: sizeof(Span<Node1>)) == SpanConstants::NEntries * 2);
4107
4108	// ensure allocations are always a power of two, at a minimum NEntries,
4109	// obeying the fomula
4110	// qNextPowerOfTwo(2 * N);
4111	// without overflowing
4112	static constexpr size_t NEntries = SpanConstants::NEntries;
4113	static_assert(GrowthPolicy::bucketsForCapacity(requestedCapacity: 1) == NEntries);
4114	static_assert(GrowthPolicy::bucketsForCapacity(requestedCapacity: NEntries / 2 + 0) == NEntries);
4115	static_assert(GrowthPolicy::bucketsForCapacity(requestedCapacity: NEntries / 2 + 1) == 2 * NEntries);
4116	static_assert(GrowthPolicy::bucketsForCapacity(requestedCapacity: NEntries * 1 - 1) == 2 * NEntries);
4117	static_assert(GrowthPolicy::bucketsForCapacity(requestedCapacity: NEntries * 1 + 0) == 4 * NEntries);
4118	static_assert(GrowthPolicy::bucketsForCapacity(requestedCapacity: NEntries * 1 + 1) == 4 * NEntries);
4119	static_assert(GrowthPolicy::bucketsForCapacity(requestedCapacity: NEntries * 2 - 1) == 4 * NEntries);
4120	static_assert(GrowthPolicy::bucketsForCapacity(requestedCapacity: NEntries * 2 + 0) == 8 * NEntries);
4121	static_assert(GrowthPolicy::bucketsForCapacity(SIZE_MAX / 4) == SIZE_MAX / 2 + 1);
4122	static_assert(GrowthPolicy::bucketsForCapacity(SIZE_MAX / 2) == SIZE_MAX);
4123	static_assert(GrowthPolicy::bucketsForCapacity(SIZE_MAX) == SIZE_MAX);
4124	}
4125	#endif
4126
4127	QT_END_NAMESPACE
4128