New QHash implementation

A brand new QHash implementation using a faster and more memory efficient data
structure than the old QHash.

A new implementation for QHash. Instead of a node based approach as the old
QHash, this implementation now uses a two stage lookup table. The total
amount of buckets in the table are divided into spans of 128 entries.
Inside each span, we use an array of chars to index into a storage area
for the span.

The storage area for each span is a simple array, that gets (re-)allocated
with size increments of 16 items. This gives an average memory overhead of
8*sizeof(struct{ Key; Value; }) + 128*sizeof(char) + 16 for each span.

To give good performance and avoid too many collisions, the array keeps its
load factor between .25 and .5 (and grows and rehashes if the load factor goes
above .5).

This design allows us to keep the memory overhead of the Hash very small, while
at the same time giving very good performance. The calculated overhead for a
QHash<int, int> comes to 1.7-3.3 bytes per entry and to 2.2-4.3 bytes for
a QHash<ptr, ptr>.

The new implementation also completely splits the QHash and QMultiHash classes.

One behavioral change to note is that the new QHash implementation will not
provide stable references to nodes in the hash when the table needs to grow.

Benchmarking using https://github.com/Tessil/hash-table-shootout shows
very nice performance compared to many different hash table implementation.
Numbers shown below are for a hash<int64, int64> with 1 million entries. These
numbers scale nicely (mostly in a linear fashion with some variation due to
varying load factors) to smaller and larger tables. All numbers are in seconds,
measured with gcc on Linux:

Hash table              random     random     random  random reads   full
                        insertion  insertion  full    full   after   iteration
                                   (reserved) deletes reads  deletes
------------------------------------------------------------------------------
std::unordered_map      0,3842     0,1969     0,4511  0,1300 0,1169  0,0708
google::dense_hash_map  0,1091     0,0846     0,0550  0,0452 0,0754  0,0160
google::sparse_hash_map 0,2888     0,1582     0,0948  0,1020 0,1348  0,0112
tsl::sparse_map         0,1487     0,1013     0,0735  0,0448 0,0505  0,0042
old QHash               0,2886     0,1798     0,5065  0,0840 0,0717  0,1387
new QHash               0,0940     0,0714     0,1494  0,0579 0,0449  0,0146

Numbers for hash<std::string, int64>, with the string having 15 characters:

Hash table              random     random     random  random reads
                        insertion  insertion  full    full   after
                                   (reserved) deletes reads  deletes
--------------------------------------------------------------------
std::unordered_map      0,4993     0,2563     0,5515  0,2950 0,2153
google::dense_hash_map  0,2691     0,1870     0,1547  0,1125 0,1622
google::sparse_hash_map 0,6979     0,3304     0,1884  0,1822 0,2122
tsl::sparse_map         0,4066     0,2586     0,1929  0,1146 0,1095
old QHash               0,3236     0,2064     0,5986  0,2115 0,1666
new QHash               0,2119     0,1652     0,2390  0,1378 0,0965

Memory usage numbers (in MB for a table with 1M entries) also look very nice:

Hash table        Key   int64      std::string (15 chars)
                  Value int64      int64
---------------------------------------------------------
std::unordered_map      44.63      75.35
google::dense_hash_map  32.32      80,60
google::sparse_hash_map 18.08      44.21
tsl::sparse_map         20.44      45,93
old QHash               53.95      69,16
new QHash               23.23      51,32

Fixes: QTBUG-80311
Change-Id: I5679734144bc9bca2102acbe725fcc2fa89f0dff
Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>

7 files changed, 1624 insertions, 1378 deletions

diff --git a/src/corelib/tools/qhash.cpp b/src/corelib/tools/qhash.cpp
index ca5b7ffd55..f048aa01de 100644
--- a/src/corelib/tools/qhash.cpp
+++ b/src/corelib/tools/qhash.cpp
@@ -405,328 +405,6 @@ uint qt_hash(QStringView key, uint chained) noexcept
     return h;
 }
 
-/*
-    The prime_deltas array contains the difference between a power
-    of two and the next prime number:
-
-    prime_deltas[i] = nextprime(2^i) - 2^i
-
-    Basically, it's sequence A092131 from OEIS, assuming:
-    - nextprime(1) = 1
-    - nextprime(2) = 2
-    and
-    - left-extending it for the offset 0 (A092131 starts at i=1)
-    - stopping the sequence at i = 28 (the table is big enough...)
-*/
-
-static const uchar prime_deltas[] = {
-    0,  0,  1,  3,  1,  5,  3,  3,  1,  9,  7,  5,  3, 17, 27,  3,
-    1, 29,  3, 21,  7, 17, 15,  9, 43, 35, 15,  0,  0,  0,  0,  0
-};
-
-/*
-    The primeForNumBits() function returns the prime associated to a
-    power of two. For example, primeForNumBits(8) returns 257.
-*/
-
-static inline int primeForNumBits(int numBits)
-{
-    return (1 << numBits) + prime_deltas[numBits];
-}
-
-/*
-    Returns the smallest integer n such that
-    primeForNumBits(n) >= hint.
-*/
-static int countBits(int hint)
-{
-    int numBits = 0;
-    int bits = hint;
-
-    while (bits > 1) {
-        bits >>= 1;
-        numBits++;
-    }
-
-    if (numBits >= (int)sizeof(prime_deltas)) {
-        numBits = sizeof(prime_deltas) - 1;
-    } else if (primeForNumBits(numBits) < hint) {
-        ++numBits;
-    }
-    return numBits;
-}
-
-/*
-    A QHash has initially around pow(2, MinNumBits) buckets. For
-    example, if MinNumBits is 4, it has 17 buckets.
-*/
-const int MinNumBits = 4;
-
-const QHashData QHashData::shared_null = {
-    nullptr, nullptr, Q_REFCOUNT_INITIALIZE_STATIC, 0, 0, MinNumBits, 0, 0, 0, true, false, 0
-};
-
-void *QHashData::allocateNode(int nodeAlign)
-{
-    void *ptr = strictAlignment ? qMallocAligned(nodeSize, nodeAlign) : malloc(nodeSize);
-    Q_CHECK_PTR(ptr);
-    return ptr;
-}
-
-void QHashData::freeNode(void *node)
-{
-    if (strictAlignment)
-        qFreeAligned(node);
-    else
-        free(node);
-}
-
-QHashData *QHashData::detach_helper(void (*node_duplicate)(Node *, void *),
-                                    void (*node_delete)(Node *),
-                                    int nodeSize,
-                                    int nodeAlign)
-{
-    union {
-        QHashData *d;
-        Node *e;
-    };
-    if (this == &shared_null)
-        qt_initialize_qhash_seed(); // may throw
-    d = new QHashData;
-    d->fakeNext = nullptr;
-    d->buckets = nullptr;
-    d->ref.initializeOwned();
-    d->size = size;
-    d->nodeSize = nodeSize;
-    d->userNumBits = userNumBits;
-    d->numBits = numBits;
-    d->numBuckets = numBuckets;
-    d->seed = (this == &shared_null) ? uint(qt_qhash_seed.loadRelaxed()) : seed;
-    d->sharable = true;
-    d->strictAlignment = nodeAlign > 8;
-    d->reserved = 0;
-
-    if (numBuckets) {
-        QT_TRY {
-            d->buckets = new Node *[numBuckets];
-        } QT_CATCH(...) {
-            // restore a consistent state for d
-            d->numBuckets = 0;
-            // roll back
-            d->free_helper(node_delete);
-            QT_RETHROW;
-        }
-
-        Node *this_e = reinterpret_cast<Node *>(this);
-        for (int i = 0; i < numBuckets; ++i) {
-            Node **nextNode = &d->buckets[i];
-            Node *oldNode = buckets[i];
-            while (oldNode != this_e) {
-                QT_TRY {
-                    Node *dup = static_cast<Node *>(allocateNode(nodeAlign));
-
-                    QT_TRY {
-                        node_duplicate(oldNode, dup);
-                    } QT_CATCH(...) {
-                        freeNode( dup );
-                        QT_RETHROW;
-                    }
-
-                    *nextNode = dup;
-                    nextNode = &dup->next;
-                    oldNode = oldNode->next;
-                } QT_CATCH(...) {
-                    // restore a consistent state for d
-                    *nextNode = e;
-                    d->numBuckets = i+1;
-                    // roll back
-                    d->free_helper(node_delete);
-                    QT_RETHROW;
-                }
-            }
-            *nextNode = e;
-        }
-    }
-    return d;
-}
-
-void QHashData::free_helper(void (*node_delete)(Node *))
-{
-    if (node_delete) {
-        Node *this_e = reinterpret_cast<Node *>(this);
-        Node **bucket = reinterpret_cast<Node **>(this->buckets);
-
-        int n = numBuckets;
-        while (n--) {
-            Node *cur = *bucket++;
-            while (cur != this_e) {
-                Node *next = cur->next;
-                node_delete(cur);
-                freeNode(cur);
-                cur = next;
-            }
-        }
-    }
-    delete [] buckets;
-    delete this;
-}
-
-QHashData::Node *QHashData::nextNode(Node *node)
-{
-    union {
-        Node *next;
-        Node *e;
-        QHashData *d;
-    };
-    next = node->next;
-    Q_ASSERT_X(next, "QHash", "Iterating beyond end()");
-    if (next->next)
-        return next;
-
-    int start = (node->h % d->numBuckets) + 1;
-    Node **bucket = d->buckets + start;
-    int n = d->numBuckets - start;
-    while (n--) {
-        if (*bucket != e)
-            return *bucket;
-        ++bucket;
-    }
-    return e;
-}
-
-QHashData::Node *QHashData::previousNode(Node *node)
-{
-    union {
-        Node *e;
-        QHashData *d;
-    };
-
-    e = node;
-    while (e->next)
-        e = e->next;
-
-    int start;
-    if (node == e)
-        start = d->numBuckets - 1;
-    else
-        start = node->h % d->numBuckets;
-
-    Node *sentinel = node;
-    Node **bucket = d->buckets + start;
-    while (start >= 0) {
-        if (*bucket != sentinel) {
-            Node *prev = *bucket;
-            while (prev->next != sentinel)
-                prev = prev->next;
-            return prev;
-        }
-
-        sentinel = e;
-        --bucket;
-        --start;
-    }
-    Q_ASSERT_X(start >= 0, "QHash", "Iterating backward beyond begin()");
-    return e;
-}
-
-/*
-    If hint is negative, -hint gives the approximate number of
-    buckets that should be used for the hash table. If hint is
-    nonnegative, (1 << hint) gives the approximate number
-    of buckets that should be used.
-*/
-void QHashData::rehash(int hint)
-{
-    if (hint < 0) {
-        hint = countBits(-hint);
-        if (hint < MinNumBits)
-            hint = MinNumBits;
-        userNumBits = hint;
-        while (primeForNumBits(hint) < (size >> 1))
-            ++hint;
-    } else if (hint < MinNumBits) {
-        hint = MinNumBits;
-    }
-
-    if (numBits != hint) {
-        Node *e = reinterpret_cast<Node *>(this);
-        Node **oldBuckets = buckets;
-        int oldNumBuckets = numBuckets;
-
-        int nb = primeForNumBits(hint);
-        buckets = new Node *[nb];
-        numBits = hint;
-        numBuckets = nb;
-        for (int i = 0; i < numBuckets; ++i)
-            buckets[i] = e;
-
-        for (int i = 0; i < oldNumBuckets; ++i) {
-            Node *firstNode = oldBuckets[i];
-            while (firstNode != e) {
-                uint h = firstNode->h;
-                Node *lastNode = firstNode;
-                while (lastNode->next != e && lastNode->next->h == h)
-                    lastNode = lastNode->next;
-
-                Node *afterLastNode = lastNode->next;
-                Node **beforeFirstNode = &buckets[h % numBuckets];
-                while (*beforeFirstNode != e)
-                    beforeFirstNode = &(*beforeFirstNode)->next;
-                lastNode->next = *beforeFirstNode;
-                *beforeFirstNode = firstNode;
-                firstNode = afterLastNode;
-            }
-        }
-        delete [] oldBuckets;
-    }
-}
-
-#ifdef QT_QHASH_DEBUG
-
-void QHashData::dump()
-{
-    qDebug("Hash data (ref = %d, size = %d, nodeSize = %d, userNumBits = %d, numBits = %d, numBuckets = %d)",
-            int(ref), size, nodeSize, userNumBits, numBits,
-            numBuckets);
-    qDebug("    %p (fakeNode = %p)", this, fakeNext);
-    for (int i = 0; i < numBuckets; ++i) {
-        Node *n = buckets[i];
-        if (n != reinterpret_cast<Node *>(this)) {
-            QString line = QString::asprintf("%d:", i);
-            while (n != reinterpret_cast<Node *>(this)) {
-                line += QString::asprintf(" -> [%p]", n);
-                if (!n) {
-                    line += " (CORRUPT)";
-                    break;
-                }
-                n = n->next;
-            }
-            qDebug("%ls", qUtf16Printable(line));
-        }
-    }
-}
-
-void QHashData::checkSanity()
-{
-    if (Q_UNLIKELY(fakeNext))
-        qFatal("Fake next isn't 0");
-
-    for (int i = 0; i < numBuckets; ++i) {
-        Node *n = buckets[i];
-        Node *p = n;
-        if (Q_UNLIKELY(!n))
-            qFatal("%d: Bucket entry is 0", i);
-        if (n != reinterpret_cast<Node *>(this)) {
-            while (n != reinterpret_cast<Node *>(this)) {
-                if (Q_UNLIKELY(!n->next))
-                    qFatal("%d: Next of %p is 0, should be %p", i, n, this);
-                n = n->next;
-            }
-        }
-    }
-}
-#endif
-
 /*!
     \fn template <typename T1, typename T2> uint qHash(const QPair<T1, T2> &key, uint seed = 0)
     \since 5.0
diff --git a/src/corelib/tools/qhash.h b/src/corelib/tools/qhash.h
index d03f301306..cdf5577fcb 100644
--- a/src/corelib/tools/qhash.h
+++ b/src/corelib/tools/qhash.h
@@ -1,7 +1,6 @@
 /****************************************************************************
 **
-** Copyright (C) 2016 The Qt Company Ltd.
-** Copyright (C) 2015 Klarälvdalens Datakonsult AB, a KDAB Group company, info@kdab.com, author Marc Mutz <marc.mutz@kdab.com>
+** Copyright (C) 2020 The Qt Company Ltd.
 ** Contact: https://www.qt.io/licensing/
 **
 ** This file is part of the QtCore module of the Qt Toolkit.
@@ -41,218 +40,769 @@
 #ifndef QHASH_H
 #define QHASH_H
 
-#include <QtCore/qchar.h>
 #include <QtCore/qiterator.h>
-#include <QtCore/qlist.h>
+#include <QtCore/qvector.h>
 #include <QtCore/qrefcount.h>
 #include <QtCore/qhashfunctions.h>
 #include <QtCore/qcontainertools_impl.h>
+#include <QtCore/qmath.h>
 
-#include <algorithm>
 #include <initializer_list>
 
-#if defined(Q_CC_MSVC)
-#pragma warning( push )
-#pragma warning( disable : 4311 ) // disable pointer truncation warning
-#pragma warning( disable : 4127 ) // conditional expression is constant
-#endif
-
 QT_BEGIN_NAMESPACE
 
-struct Q_CORE_EXPORT QHashData
+struct QHashDummyValue
 {
-    struct Node {
-        Node *next;
-        uint h;
-    };
+    bool operator==(const QHashDummyValue &) const noexcept { return true; }
+};
 
-    Node *fakeNext;
-    Node **buckets;
-    QtPrivate::RefCount ref;
-    int size;
-    int nodeSize;
-    short userNumBits;
-    short numBits;
-    int numBuckets;
-    uint seed;
-    uint sharable : 1;
-    uint strictAlignment : 1;
-    uint reserved : 30;
-
-    void *allocateNode(int nodeAlign);
-    void freeNode(void *node);
-    QHashData *detach_helper(void (*node_duplicate)(Node *, void *), void (*node_delete)(Node *),
-                             int nodeSize, int nodeAlign);
-    bool willGrow();
-    void hasShrunk();
-    void rehash(int hint);
-    void free_helper(void (*node_delete)(Node *));
-    Node *firstNode();
-#ifdef QT_QHASH_DEBUG
-    void dump();
-    void checkSanity();
-#endif
-    static Node *nextNode(Node *node);
-    static Node *previousNode(Node *node);
+namespace QHashPrivate {
 
-    static const QHashData shared_null;
-};
+// QHash uses a power of two growth policy.
+namespace GrowthPolicy
+{
+inline constexpr size_t maxNumBuckets() noexcept
+{
+    return size_t(1) << (8*sizeof(size_t) - 1);
+}
+inline constexpr size_t bucketsForCapacity(size_t requestedCapacity) noexcept
+{
+    if (requestedCapacity <= 8)
+        return 16;
+    if (requestedCapacity >= maxNumBuckets())
+        return maxNumBuckets();
+    return qNextPowerOfTwo(QIntegerForSize<sizeof(size_t)>::Unsigned(2*requestedCapacity - 1));
+}
+inline constexpr size_t bucketForHash(size_t nBuckets, size_t hash) noexcept
+{
+    return hash & (nBuckets - 1);
+}
+}
 
-inline bool QHashData::willGrow()
+template <typename Key, typename T>
+struct Node
 {
-    if (size >= numBuckets) {
-        rehash(numBits + 1);
-        return true;
-    } else {
-        return false;
+    using KeyType = Key;
+    using ValueType = T;
+
+    Key key;
+    T value;
+    static Node create(Key &&k, T &&t) noexcept(std::is_nothrow_move_assignable_v<Key> && std::is_nothrow_move_assignable_v<T>)
+    {
+        return Node{ std::move(k), std::move(t) };
     }
-}
+    static Node create(const Key &k, const T &t) noexcept(std::is_nothrow_copy_constructible_v<Key> && std::is_nothrow_copy_constructible_v<T>)
+    {
+        return Node{ k, t };
+    }
+    void replace(const T &t) noexcept(std::is_nothrow_assignable_v<T>)
+    {
+        value = t;
+    }
+    void replace(T &&t) noexcept(std::is_nothrow_move_assignable_v<T>)
+    {
+        value = std::move(t);
+    }
+    T &&takeValue() noexcept(std::is_nothrow_move_assignable_v<T>)
+    {
+        return std::move(value);
+    }
+};
 
-inline void QHashData::hasShrunk()
+template <typename T>
+struct MultiNodeChain
 {
-    if (size <= (numBuckets >> 3) && numBits > userNumBits) {
-        QT_TRY {
-            rehash(qMax(int(numBits) - 2, int(userNumBits)));
-        } QT_CATCH(const std::bad_alloc &) {
-            // ignore bad allocs - shrinking shouldn't throw. rehash is exception safe.
+    T value;
+    MultiNodeChain *next = nullptr;
+    ~MultiNodeChain()
+    {
+    }
+    qsizetype free() noexcept(std::is_nothrow_destructible_v<T>)
+    {
+        qsizetype nEntries = 0;
+        MultiNodeChain *e = this;
+        while (e) {
+            MultiNodeChain *n = e->next;
+            ++nEntries;
+            delete e;
+            e = n;
         }
+        return  nEntries;
     }
-}
+    bool contains(const T &val) const noexcept
+    {
+        const MultiNodeChain *e = this;
+        while (e) {
+            if (e->value == val)
+                return true;
+            e = e->next;
+        }
+        return false;
+    }
+};
 
-inline QHashData::Node *QHashData::firstNode()
+template <typename Key, typename T>
+struct MultiNode
 {
-    Node *e = reinterpret_cast<Node *>(this);
-    Node **bucket = buckets;
-    int n = numBuckets;
-    while (n--) {
-        if (*bucket != e)
-            return *bucket;
-        ++bucket;
+    using KeyType = Key;
+    using ValueType = T;
+    using Chain = MultiNodeChain<T>;
+
+    Key key;
+    Chain *value;
+
+    static MultiNode create(Key &&k, T &&t)
+    {
+        Chain *c = new Chain{ std::move(t), nullptr };
+        return MultiNode(std::move(k), c);
+    }
+    static MultiNode create(const Key &k, const T &t)
+    {
+        Chain *c = new Chain{ t, nullptr };
+        return MultiNode(k, c);
     }
-    return e;
-}
 
-struct QHashDummyValue
-{
+    MultiNode(const Key &k, Chain *c)
+        : key(k),
+          value(c)
+    {}
+    MultiNode(Key &&k, Chain *c) noexcept(std::is_nothrow_move_assignable_v<Key>)
+        : key(std::move(k)),
+          value(c)
+    {}
+
+    MultiNode(MultiNode &&other)
+        : key(other.key),
+          value(other.value)
+    {
+        other.value = nullptr;
+    }
+
+    MultiNode(const MultiNode &other)
+        : key(other.key)
+    {
+        Chain *c = other.value;
+        Chain **e = &value;
+        while (c) {
+            Chain *chain = new Chain{ c->value, nullptr };
+            *e = chain;
+            e = &chain->next;
+            c = c->next;
+        }
+    }
+    ~MultiNode()
+    {
+        if (value)
+            value->free();
+    }
+    static qsizetype freeChain(MultiNode *n) noexcept(std::is_nothrow_destructible_v<T>)
+    {
+        qsizetype size = n->value->free();
+        n->value = nullptr;
+        return size;
+    }
+    void replace(const T &t) noexcept(std::is_nothrow_assignable_v<T, T>)
+    {
+        value->value = t;
+    }
+    void replace(T &&t) noexcept(std::is_nothrow_move_assignable_v<T>)
+    {
+        value->value = std::move(t);
+    }
+    void insertMulti(const T &t)
+    {
+        Chain *e = new Chain{ t, nullptr };
+        e->next = value;
+        value = e;
+    }
+
+    // compiler generated move operators are fine
 };
 
-constexpr bool operator==(const QHashDummyValue &, const QHashDummyValue &) noexcept
+template<typename  Node>
+constexpr bool isRelocatable()
 {
-    return true;
+    return QTypeInfo<typename Node::KeyType>::isRelocatable && QTypeInfo<typename Node::ValueType>::isRelocatable;
 }
 
-Q_DECLARE_TYPEINFO(QHashDummyValue, Q_MOVABLE_TYPE | Q_DUMMY_TYPE);
+// Regular hash tables consist of a list of buckets that can store Nodes. But simply allocating one large array of buckets
+// would waste a lot of memory. To avoid this, we split the vector of buckets up into a vector of Spans. Each Span represents
+// NEntries buckets. To quickly find the correct Span that holds a bucket, NEntries must be a power of two.
+//
+// Inside each Span, there is an offset array that represents the actual buckets. offsets contains either an index into the
+// actual storage space for the Nodes (the 'entries' member) or 0xff (UnusedEntry) to flag that the bucket is empty.
+// As we have only 128 entries per Span, the offset array can be represented using an unsigned char. This trick makes the hash
+// table have a very small memory overhead compared to many other implementations.
+template<typename Node>
+struct Span {
+    enum {
+        NEntries = 128,
+        LocalBucketMask = (NEntries - 1),
+        UnusedEntry = 0xff
+    };
+    static_assert ((NEntries & LocalBucketMask) == 0, "EntriesPerSpan must be a power of two.");
+
+    // Entry is a slot available for storing a Node. The Span holds a pointer to
+    // an array of Entries. Upon construction of the array, those entries are
+    // unused, and nextFree() is being used to set up a singly linked list
+    // of free entries.
+    // When a node gets inserted, the first free entry is being picked, removed
+    // from the singly linked list and the Node gets constructed in place.
+    struct Entry {
+        typename std::aligned_storage<sizeof(Node), alignof(Node)>::type storage;
+
+        unsigned char &nextFree() { return *reinterpret_cast<unsigned char *>(&storage); }
+        Node &node() { return *reinterpret_cast<Node *>(&storage); }
+    };
 
-template <class Key, class T>
-struct QHashNode
-{
-    QHashNode *next;
-    const uint h;
-    const Key key;
-    T value;
+    unsigned char offsets[NEntries];
+    Entry *entries = nullptr;
+    unsigned char allocated = 0;
+    unsigned char nextFree = 0;
+    Span() noexcept
+    {
+        memset(offsets, UnusedEntry, sizeof(offsets));
+    }
+    ~Span()
+    {
+        freeData();
+    }
+    void freeData() noexcept(std::is_nothrow_destructible<Node>::value)
+    {
+        if (entries) {
+            if constexpr (!std::is_trivially_destructible<Node>::value) {
+                for (auto o : offsets) {
+                    if (o != UnusedEntry)
+                        entries[o].node().~Node();
+                }
+            }
+            delete [] entries;
+            entries = nullptr;
+        }
+    }
+    void insert(size_t i, Node &&n)
+    {
+        Q_ASSERT(i <= NEntries);
+        Q_ASSERT(offsets[i] == UnusedEntry);
+        if (nextFree == allocated)
+            addStorage();
+        unsigned char entry = nextFree;
+        Q_ASSERT(entry < allocated);
+        nextFree = entries[entry].nextFree();
+        offsets[i] = entry;
+        new (&entries[entry].node()) Node(std::move(n));
+    }
+    void erase(size_t bucket) noexcept(std::is_nothrow_destructible<Node>::value)
+    {
+        Q_ASSERT(bucket <= NEntries);
+        Q_ASSERT(offsets[bucket] != UnusedEntry);
 
-    inline QHashNode(const Key &key0, const T &value0, uint hash, QHashNode *n)
-        : next(n), h(hash), key(key0), value(value0) {}
-    inline bool same_key(uint h0, const Key &key0) const { return h0 == h && key0 == key; }
+        unsigned char entry = offsets[bucket];
+        offsets[bucket] = UnusedEntry;
 
-private:
-    Q_DISABLE_COPY(QHashNode)
+        entries[entry].node().~Node();
+        entries[entry].nextFree() = nextFree;
+        nextFree = entry;
+    }
+    size_t offset(size_t i) const noexcept
+    {
+        return offsets[i];
+    }
+    bool hasNode(size_t i) const noexcept
+    {
+        return (offsets[i] != UnusedEntry);
+    }
+    Node &at(size_t i) noexcept
+    {
+        Q_ASSERT(i <= NEntries);
+        Q_ASSERT(offsets[i] != UnusedEntry);
+
+        return entries[offsets[i]].node();
+    }
+    const Node &at(size_t i) const noexcept
+    {
+        Q_ASSERT(i <= NEntries);
+        Q_ASSERT(offsets[i] != UnusedEntry);
+
+        return entries[offsets[i]].node();
+    }
+    Node &atOffset(size_t o) noexcept
+    {
+        Q_ASSERT(o < allocated);
+
+        return entries[o].node();
+    }
+    const Node &atOffset(size_t o) const noexcept
+    {
+        Q_ASSERT(o < allocated);
+
+        return entries[o].node();
+    }
+    void moveLocal(size_t from, size_t to) noexcept
+    {
+        Q_ASSERT(offsets[from] != UnusedEntry);
+        Q_ASSERT(offsets[to] == UnusedEntry);
+        offsets[to] = offsets[from];
+        offsets[from] = UnusedEntry;
+    }
+    void moveFromSpan(Span &fromSpan, size_t fromIndex, size_t to) noexcept(std::is_nothrow_move_constructible_v<Node>)
+    {
+        Q_ASSERT(to <= NEntries);
+        Q_ASSERT(offsets[to] == UnusedEntry);
+        Q_ASSERT(fromIndex <= NEntries);
+        Q_ASSERT(fromSpan.offsets[fromIndex] != UnusedEntry);
+        if (nextFree == allocated)
+            addStorage();
+        Q_ASSERT(nextFree < allocated);
+        offsets[to] = nextFree;
+        Entry &toEntry = entries[nextFree];
+        nextFree = toEntry.nextFree();
+
+        size_t fromOffset = fromSpan.offsets[fromIndex];
+        fromSpan.offsets[fromIndex] = UnusedEntry;
+        Entry &fromEntry = fromSpan.entries[fromOffset];
+
+        if constexpr (isRelocatable<Node>()) {
+            memcpy(&toEntry, &fromEntry, sizeof(Entry));
+        } else {
+            new (&toEntry.node()) Node(std::move(fromEntry.node()));
+            fromEntry.node().~Node();
+        }
+        fromEntry.nextFree() = fromSpan.nextFree;
+        fromSpan.nextFree = static_cast<unsigned char>(fromOffset);
+    }
+
+    void addStorage()
+    {
+        Q_ASSERT(allocated < NEntries);
+        Q_ASSERT(nextFree == allocated);
+        // the hash table should always be between 25 and 50% full
+        // this implies that we on average have between 32 and 64 entries
+        // in here. The likelihood of having below 16 entries is very small,
+        // so start with that and increment by 16 each time we need to add
+        // some more space
+        const size_t increment = NEntries/8;
+        size_t alloc = allocated + increment;
+        Entry *newEntries = new Entry[alloc];
+        // we only add storage if the previous storage was fully filled, so
+        // simply copy the old data over
+        if constexpr (isRelocatable<Node>()) {
+            memcpy(newEntries, entries, allocated*sizeof(Entry));
+        } else {
+            for (size_t i = 0; i < allocated; ++i) {
+                new (&newEntries[i].node()) Node(std::move(entries[i].node()));
+                entries[i].node().~Node();
+            }
+        }
+        for (size_t i = allocated; i < allocated + increment; ++i) {
+            newEntries[i].nextFree() = uchar(i + 1);
+        }
+        delete [] entries;
+        entries = newEntries;
+        allocated = uchar(alloc);
+    }
 };
 
-// Specialize for QHashDummyValue in order to save some memory
-template <class Key>
-struct QHashNode<Key, QHashDummyValue>
+template <typename Node>
+struct iterator;
+
+template <typename Node>
+struct Data
 {
-    union {
-        QHashNode *next;
-        QHashDummyValue value;
-    };
-    const uint h;
-    const Key key;
+    using Key = typename Node::KeyType;
+    using T = typename Node::ValueType;
+    using Span = QHashPrivate::Span<Node>;
+    using iterator = QHashPrivate::iterator<Node>;
 
-    inline QHashNode(const Key &key0, const QHashDummyValue &, uint hash, QHashNode *n)
-        : next(n), h(hash), key(key0) {}
-    inline bool same_key(uint h0, const Key &key0) const { return h0 == h && key0 == key; }
+    QtPrivate::RefCount ref = {{1}};
+    size_t size = 0;
+    size_t numBuckets = 0;
+    size_t seed = 0;
 
-private:
-    Q_DISABLE_COPY(QHashNode)
+
+    Span *spans = nullptr;
+
+    Data(size_t reserve = 0)
+    {
+        numBuckets = GrowthPolicy::bucketsForCapacity(reserve);
+        size_t nSpans = (numBuckets + Span::LocalBucketMask) / Span::NEntries;
+        spans = new Span[nSpans];
+        seed = qGlobalQHashSeed();
+    }
+    Data(const Data &other)
+        : size(other.size),
+          numBuckets(other.numBuckets),
+          seed(other.seed)
+    {
+        size_t nSpans = (other.numBuckets + Span::LocalBucketMask) / Span::NEntries;
+        spans = new Span[nSpans];
+
+        for (size_t s = 0; s < nSpans; ++s) {
+            const Span &span = other.spans[s];
+            for (size_t index = 0; index < Span::NEntries; ++index) {
+                if (!span.hasNode(index))
+                    continue;
+                const Node &n = span.at(index);
+                iterator it{ this, s*Span::NEntries + index };
+                Q_ASSERT(it.isUnused());
+
+                spans[it.span()].insert(it.index(), std::move(Node(n)));
+            }
+        }
+    }
+    Data(const Data &other, size_t reserved)
+        : size(other.size),
+          seed(other.seed)
+    {
+        numBuckets = GrowthPolicy::bucketsForCapacity(qMax(size, reserved));
+        size_t nSpans = (numBuckets + Span::LocalBucketMask) / Span::NEntries;
+        spans = new Span[nSpans];
+
+        for (size_t s = 0; s < nSpans; ++s) {
+            const Span &span = other.spans[s];
+            for (size_t index = 0; index < Span::NEntries; ++index) {
+                if (!span.hasNode(index))
+                    continue;
+                const Node &n = span.at(index);
+                iterator it = find(n.key);
+                Q_ASSERT(it.isUnused());
+                spans[it.span()].insert(it.index(), std::move(Node(n)));
+            }
+        }
+    }
+
+    static Data *detached(Data *d)
+    {
+        if (!d)
+            return new Data;
+        Data *dd = new Data(*d);
+        if (!d->ref.deref())
+            delete d;
+        return dd;
+    }
+    static Data *detached(Data *d, size_t size)
+    {
+        if (!d)
+            return new Data(size);
+        Data *dd = new Data(*d, size);
+        if (!d->ref.deref())
+            delete d;
+        return dd;
+    }
+
+
+    iterator detachedIterator(iterator other) const noexcept
+    {
+        return iterator{this, other.bucket};
+    }
+
+    iterator begin() const noexcept
+    {
+        iterator it{ this, 0 };
+        if (it.isUnused())
+            ++it;
+        return it;
+    }
+
+    constexpr iterator end() const noexcept
+    {
+        return iterator();
+    }
+
+    void rehash(size_t sizeHint = 0)
+    {
+        if (sizeHint == 0)
+            sizeHint = size;
+        size_t newBucketCount = GrowthPolicy::bucketsForCapacity(sizeHint);
+
+        Span *oldSpans = spans;
+        size_t oldBucketCount = numBuckets;
+        size_t nSpans = (newBucketCount + Span::LocalBucketMask) / Span::NEntries;
+        spans = new Span[nSpans];
+        numBuckets = newBucketCount;
+        size_t oldNSpans = (oldBucketCount + Span::LocalBucketMask) / Span::NEntries;
+
+        for (size_t s = 0; s < oldNSpans; ++s) {
+            Span &span = oldSpans[s];
+            for (size_t index = 0; index < Span::NEntries; ++index) {
+                if (!span.hasNode(index))
+                    continue;
+                Node &n = span.at(index);
+                iterator it = find(n.key);
+                Q_ASSERT(it.isUnused());
+                spans[it.span()].insert(it.index(), std::move(n));
+            }
+            span.freeData();
+        }
+        delete [] oldSpans;
+    }
+
+    size_t nextBucket(size_t bucket) const noexcept
+    {
+        ++bucket;
+        if (bucket == numBuckets)
+            bucket = 0;
+        return bucket;
+    }
+
+    float loadFactor() const noexcept
+    {
+        return float(size)/numBuckets;
+    }
+    bool shouldGrow() const noexcept
+    {
+        return size >= (numBuckets >> 1);
+    }
+
+    iterator find(const Key &key) const noexcept
+    {
+        Q_ASSERT(numBuckets > 0);
+        size_t hash = qHash(key, seed);
+        size_t bucket = GrowthPolicy::bucketForHash(numBuckets, hash);
+        // loop over the buckets until we find the entry we search for
+        // or an empty slot, in which case we know the entry doesn't exist
+        while (true) {
+            // Split the bucket into the indexex of span array, and the local
+            // offset inside the span
+            size_t span = bucket / Span::NEntries;
+            size_t index = bucket & Span::LocalBucketMask;
+            Span &s = spans[span];
+            size_t offset = s.offset(index);
+            if (offset == Span::UnusedEntry) {
+                return iterator{ this, bucket };
+            } else {
+                Node &n = s.atOffset(offset);
+                if (n.key == key)
+                    return iterator{ this, bucket };
+            }
+            bucket = nextBucket(bucket);
+        }
+    }
+
+    Node *findNode(const Key &key) const noexcept
+    {
+        if (!size)
+            return nullptr;
+        iterator it = find(key);
+        if (it.isUnused())
+            return nullptr;
+        return it.node();
+    }
+
+    Node *findAndInsertNode(const Key &key) noexcept
+    {
+        if (shouldGrow())
+            rehash(size + 1);
+        iterator it = find(key);
+        if (it.isUnused()) {
+            spans[it.span()].insert(it.index(), Node::create(key, T()));
+            ++size;
+        }
+        return it.node();
+    }
+
+
+    iterator insert(Node &&n)
+    {
+        if (shouldGrow())
+            rehash(size + 1);
+        iterator it = find(n.key);
+        if (it.isUnused()) {
+            spans[it.span()].insert(it.index(), std::move(n));
+            ++size;
+        } else {
+            it.node()->replace(std::move(n.takeValue()));
+        }
+        return it;
+    }
+
+    iterator insert(const Key &key, const T &value)
+    {
+        if (shouldGrow())
+            rehash(size + 1);
+        auto it = find(key);
+        if (it.isUnused()) {
+            spans[it.span()].insert(it.index(), Node::create(key, value));
+            ++size;
+        } else {
+            it.node()->replace(value);
+        }
+        return it;
+    }
+
+    iterator insertMulti(const Key &key, const T &value)
+    {
+        if (shouldGrow())
+            rehash(size + 1);
+        auto it = find(key);
+        if (it.isUnused()) {
+            spans[it.span()].insert(it.index(), std::move(Node::create(key, value)));
+            ++size;
+        } else {
+            it.node()->insertMulti(value);
+        }
+        return it;
+    }
+
+
+    iterator erase(iterator it) noexcept(std::is_nothrow_destructible<Node>::value)
+    {
+        size_t bucket = it.bucket;
+        size_t span = bucket / Span::NEntries;
+        size_t index = bucket & Span::LocalBucketMask;
+        Q_ASSERT(spans[span].hasNode(index));
+        spans[span].erase(index);
+        --size;
+
+        // re-insert the following entries to avoid holes
+        size_t hole = bucket;
+        size_t next = bucket;
+        while (true) {
+            next = nextBucket(next);
+            size_t nextSpan = next / Span::NEntries;
+            size_t nextIndex = next & Span::LocalBucketMask;
+            if (!spans[nextSpan].hasNode(nextIndex))
+                break;
+            size_t hash = qHash(spans[nextSpan].at(nextIndex).key, seed);
+            size_t newBucket = GrowthPolicy::bucketForHash(numBuckets, hash);
+            while (true) {
+                if (newBucket == next) {
+                    // nothing to do, item is at the right plae
+                    break;
+                } else if (newBucket == hole) {
+                    // move into hole
+                    size_t holeSpan = hole / Span::NEntries;
+                    size_t holeIndex = hole & Span::LocalBucketMask;
+                    if (nextSpan == holeSpan) {
+                        spans[holeSpan].moveLocal(nextIndex, holeIndex);
+                    } else {
+                        // move between spans, more expensive
+                        spans[holeSpan].moveFromSpan(spans[nextSpan], nextIndex, holeIndex);
+                    }
+                    hole = next;
+                    break;
+                }
+                newBucket = nextBucket(newBucket);
+            }
+        }
+
+        // return correct position of the next element
+        if (!spans[span].hasNode(index))
+            ++it;
+        return it;
+    }
+
+    ~Data()
+    {
+        delete [] spans;
+    }
 };
 
+template <typename Node>
+struct iterator {
+    using Span = QHashPrivate::Span<Node>;
 
-#if 0
-// ###
-// The introduction of the QHash random seed breaks this optimization, as it
-// relies on qHash(int i) = i. If the hash value is salted, then the hash
-// table becomes corrupted.
-//
-// A bit more research about whether it makes sense or not to salt integer
-// keys (and in general keys whose hash value is easy to invert)
-// is needed, or about how keep this optimization and the seed (f.i. by
-// specializing QHash for integer values, and re-apply the seed during lookup).
-//
-// Be aware that such changes can easily be binary incompatible, and therefore
-// cannot be made during the Qt 5 lifetime.
-#define Q_HASH_DECLARE_INT_NODES(key_type) \
-    template <class T> \
-    struct QHashDummyNode<key_type, T> { \
-        QHashDummyNode *next; \
-        union { uint h; key_type key; }; \
-\
-        inline QHashDummyNode(key_type /* key0 */) {} \
-    }; \
-\
-    template <class T> \
-    struct QHashNode<key_type, T> { \
-        QHashNode *next; \
-        union { uint h; key_type key; }; \
-        T value; \
-\
-        inline QHashNode(key_type /* key0 */) {} \
-        inline QHashNode(key_type /* key0 */, const T &value0) : value(value0) {} \
-        inline bool same_key(uint h0, key_type) const { return h0 == h; } \
-    }
-
-#if defined(Q_BYTE_ORDER) && Q_BYTE_ORDER == Q_LITTLE_ENDIAN
-Q_HASH_DECLARE_INT_NODES(short);
-Q_HASH_DECLARE_INT_NODES(ushort);
-#endif
-Q_HASH_DECLARE_INT_NODES(int);
-Q_HASH_DECLARE_INT_NODES(uint);
-#undef Q_HASH_DECLARE_INT_NODES
-#endif // #if 0
+    const Data<Node> *d = nullptr;
+    size_t bucket = 0;
 
-template <class Key, class T>
-class QHash
-{
-    typedef QHashNode<Key, T> Node;
+    size_t span() const noexcept { return bucket / Span::NEntries; }
+    size_t index() const noexcept { return bucket & Span::LocalBucketMask; }
+    inline bool isUnused() const noexcept { return !d->spans[span()].hasNode(index()); }
 
-    union {
-        QHashData *d;
-        QHashNode<Key, T> *e;
-    };
+    inline Node *node() const noexcept
+    {
+        Q_ASSERT(!isUnused());
+        return &d->spans[span()].at(index());
+    }
+    bool atEnd() const noexcept { return !d; }
 
-    static inline Node *concrete(QHashData::Node *node) {
-        return reinterpret_cast<Node *>(node);
+    iterator operator++() noexcept
+    {
+        while (true) {
+            ++bucket;
+            if (bucket == d->numBuckets) {
+                d = nullptr;
+                bucket = 0;
+                break;
+            }
+            if (!isUnused())
+                break;
+        }
+        return *this;
     }
+    bool operator==(iterator other) const noexcept
+    { return d == other.d && bucket == other.bucket; }
+    bool operator!=(iterator other) const noexcept
+    { return !(*this == other); }
+};
+
 
-    static inline int alignOfNode() { return qMax<int>(sizeof(void*), alignof(Node)); }
+
+} // namespace QHashPrivate
+
+template <class Key, class T>
+class QHash
+{
+    using Node = QHashPrivate::Node<Key, T>;
+    using Data = QHashPrivate::Data<Node>;
+    friend class QSet<Key>;
+
+    Data *d = nullptr;
 
 public:
-    inline QHash() noexcept : d(const_cast<QHashData *>(&QHashData::shared_null)) { }
+    using key_type = Key;
+    using mapped_type = T;
+    using value_type = T;
+    using size_type = qsizetype;
+    using difference_type = qsizetype;
+    using reference = T &;
+    using const_reference = const T &;
+
+    inline QHash() noexcept = default;
     inline QHash(std::initializer_list<std::pair<Key,T> > list)
-        : d(const_cast<QHashData *>(&QHashData::shared_null))
+        : d(new Data(list.size()))
     {
-        reserve(int(list.size()));
         for (typename std::initializer_list<std::pair<Key,T> >::const_iterator it = list.begin(); it != list.end(); ++it)
             insert(it->first, it->second);
     }
-    QHash(const QHash &other) : d(other.d) { d->ref.ref(); if (!d->sharable) detach(); }
-    ~QHash() { if (!d->ref.deref()) freeData(d); }
+    QHash(const QHash &other) noexcept
+        : d(other.d)
+    {
+        if (d)
+            d->ref.ref();
+    }
+    ~QHash()
+    {
+        if (d && !d->ref.deref())
+            delete d;
+    }
+
+    QHash &operator=(const QHash &other) noexcept(std::is_nothrow_destructible<Node>::value)
+    {
+        if (d != other.d) {
+            Data *o = other.d;
+            if (o)
+                o->ref.ref();
+            if (d && !d->ref.deref())
+                delete d;
+            d = o;
+        }
+        return *this;
+    }
 
-    QHash &operator=(const QHash &other);
-    QHash(QHash &&other) noexcept : d(other.d) { other.d = const_cast<QHashData *>(&QHashData::shared_null); }
-    QHash &operator=(QHash &&other) noexcept
-    { QHash moved(std::move(other)); swap(moved); return *this; }
+    QHash(QHash &&other) noexcept
+        : d(std::exchange(other.d, nullptr))
+    {
+    }
+    QHash &operator=(QHash &&other) noexcept(std::is_nothrow_destructible<Node>::value)
+    {
+        if (d != other.d) {
+            if (d && !d->ref.deref())
+                delete d;
+            d = std::exchange(other.d, nullptr);
+        }
+        return *this;
+    }
 #ifdef Q_QDOC
     template <typename InputIterator>
     QHash(InputIterator f, InputIterator l);
@@ -277,170 +827,220 @@ public:
 #endif
     void swap(QHash &other) noexcept { qSwap(d, other.d); }
 
-    bool operator==(const QHash &other) const;
-    bool operator!=(const QHash &other) const { return !(*this == other); }
+    bool operator==(const QHash &other) const noexcept
+    {
+        if (d == other.d)
+            return true;
+        if (size() != other.size())
+            return false;
 
-    inline int size() const { return d->size; }
+        for (const_iterator it = other.begin(); it != other.end(); ++it) {
+            const_iterator i = find(it.key());
+            if (i == end() || !(i.value() == it.value()))
+                return false;
+        }
+        // all values must be the same as size is the same
+        return true;
+    }
+    bool operator!=(const QHash &other) const noexcept { return !(*this == other); }
 
-    inline bool isEmpty() const { return d->size == 0; }
+    inline qsizetype size() const noexcept { return d ? qsizetype(d->size) : 0; }
+    inline bool isEmpty() const noexcept { return !d || d->size == 0; }
 
-    inline int capacity() const { return d->numBuckets; }
-    void reserve(int size);
-    inline void squeeze() { reserve(1); }
+    inline qsizetype capacity() const noexcept { return d ? qsizetype(d->numBuckets >> 1) : 0; }
+    void reserve(qsizetype size)
+    {
+        if (isDetached())
+            d->rehash(size);
+        else
+            d = Data::detached(d, size_t(size));
+    }
+    inline void squeeze() { reserve(0); }
+
+    inline void detach() { if (!d || d->ref.isShared()) d = Data::detached(d); }
+    inline bool isDetached() const noexcept { return d && !d->ref.isShared(); }
+    bool isSharedWith(const QHash &other) const noexcept { return d == other.d; }
+
+    void clear() noexcept(std::is_nothrow_destructible<Node>::value)
+    {
+        if (d && !d->ref.deref())
+            delete d;
+        d = nullptr;
+    }
 
-    inline void detach() { if (d->ref.isShared()) detach_helper(); }
-    inline bool isDetached() const { return !d->ref.isShared(); }
-    bool isSharedWith(const QHash &other) const { return d == other.d; }
+    bool remove(const Key &key)
+    {
+        if (isEmpty()) // prevents detaching shared null
+            return false;
+        detach();
 
-    void clear();
+        auto it = d->find(key);
+        if (it.isUnused())
+            return false;
+        d->erase(it);
+        return true;
+    }
+    T take(const Key &key)
+    {
+        if (isEmpty()) // prevents detaching shared null
+            return T();
+        detach();
 
-    int remove(const Key &key);
-    T take(const Key &key);
+        auto it = d->find(key);
+        if (it.isUnused())
+            return T();
+        T value = it.node()->takeValue();
+        d->erase(it);
+        return value;
+    }
 
-    bool contains(const Key &key) const;
-    Key key(const T &value) const;
-    Key key(const T &value, const Key &defaultKey) const;
-    T value(const Key &key) const;
-    T value(const Key &key, const T &defaultValue) const;
-    T &operator[](const Key &key);
-    const T operator[](const Key &key) const;
+    bool contains(const Key &key) const noexcept
+    {
+        if (!d)
+            return false;
+        return d->findNode(key) != nullptr;
+    }
+    qsizetype count(const Key &key) const noexcept
+    {
+        return contains(key) ? 1 : 0;
+    }
 
-    QList<Key> keys() const;
-    QList<Key> keys(const T &value) const;
-    QList<T> values() const;
-#if QT_DEPRECATED_SINCE(5, 15)
-    QT_DEPRECATED_VERSION_X_5_15("Use QMultiHash for hashes storing multiple values with the same key.") QList<Key> uniqueKeys() const;
-    QT_DEPRECATED_VERSION_X_5_15("Use QMultiHash for hashes storing multiple values with the same key.") QList<T> values(const Key &key) const;
-#endif
-    int count(const Key &key) const;
+    Key key(const T &value, const Key &defaultKey = Key()) const noexcept
+    {
+        if (d) {
+            const_iterator i = begin();
+            while (i != end()) {
+                if (i.value() == value)
+                    return i.key();
+                ++i;
+            }
+        }
+
+        return defaultKey;
+    }
+    T value(const Key &key, const T &defaultValue = T()) const noexcept
+    {
+        if (d) {
+            Node *n = d->findNode(key);
+            if (n)
+                return n->value;
+        }
+        return defaultValue;
+    }
+    T &operator[](const Key &key)
+    {
+        detach();
+        Node *n = d->findAndInsertNode(key);
+        Q_ASSERT(n);
+        return n->value;
+    }
+
+    const T operator[](const Key &key) const noexcept
+    {
+        return value(key);
+    }
+
+    QVector<Key> keys() const
+    {
+        return QVector<Key>(keyBegin(), keyEnd());
+    }
+    QVector<Key> keys(const T &value) const
+    {
+        QVector<Key> res;
+        const_iterator i = begin();
+        while (i != end()) {
+            if (i.value() == value)
+                res.append(i.key());
+            ++i;
+        }
+        return res;
+    }
+    QVector<T> values() const
+    {
+        return QVector<T>(begin(), end());
+    }
 
     class const_iterator;
 
     class iterator
     {
+        using piter = typename QHashPrivate::iterator<Node>;
         friend class const_iterator;
         friend class QHash<Key, T>;
         friend class QSet<Key>;
-        QHashData::Node *i;
+        piter i;
+        explicit inline iterator(piter it) noexcept : i(it) { }
 
     public:
-#if QT_DEPRECATED_WARNINGS_SINCE < QT_VERSION_CHECK(5, 15, 0)
-        typedef std::bidirectional_iterator_tag iterator_category;
-#else
         typedef std::forward_iterator_tag iterator_category;
-#endif
         typedef qptrdiff difference_type;
         typedef T value_type;
         typedef T *pointer;
         typedef T &reference;
 
-        inline iterator() : i(nullptr) { }
-        explicit inline iterator(void *node) : i(reinterpret_cast<QHashData::Node *>(node)) { }
+        constexpr iterator() noexcept = default;
 
-        inline const Key &key() const { return concrete(i)->key; }
-        inline T &value() const { return concrete(i)->value; }
-        inline T &operator*() const { return concrete(i)->value; }
-        inline T *operator->() const { return &concrete(i)->value; }
-        inline bool operator==(const iterator &o) const { return i == o.i; }
-        inline bool operator!=(const iterator &o) const { return i != o.i; }
+        inline const Key &key() const noexcept { return i.node()->key; }
+        inline T &value() const noexcept { return i.node()->value; }
+        inline T &operator*() const noexcept { return i.node()->value; }
+        inline T *operator->() const noexcept { return &i.node()->value; }
+        inline bool operator==(const iterator &o) const noexcept { return i == o.i; }
+        inline bool operator!=(const iterator &o) const noexcept { return i != o.i; }
 
-        inline iterator &operator++() {
-            i = QHashData::nextNode(i);
-            return *this;
-        }
-        inline iterator operator++(int) {
-            iterator r = *this;
-            i = QHashData::nextNode(i);
-            return r;
-        }
-#if QT_DEPRECATED_SINCE(5, 15)
-        inline QT_DEPRECATED_VERSION_5_15 iterator &operator--()
+        inline iterator &operator++() noexcept
         {
-            i = QHashData::previousNode(i);
+            ++i;
             return *this;
         }
-        inline QT_DEPRECATED_VERSION_5_15 iterator operator--(int)
+        inline iterator operator++(int) noexcept
         {
             iterator r = *this;
-            i = QHashData::previousNode(i);
+            ++i;
             return r;
         }
-        inline QT_DEPRECATED_VERSION_5_15 iterator operator+(int j) const
-        { iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
-        inline QT_DEPRECATED_VERSION_5_15 iterator operator-(int j) const { return operator+(-j); }
-        inline QT_DEPRECATED_VERSION_5_15 iterator &operator+=(int j) { return *this = *this + j; }
-        inline QT_DEPRECATED_VERSION_5_15 iterator &operator-=(int j) { return *this = *this - j; }
-        friend inline QT_DEPRECATED_VERSION_5_15 iterator operator+(int j, iterator k) { return k + j; }
-#endif
 
-        inline bool operator==(const const_iterator &o) const { return i == o.i; }
-        inline bool operator!=(const const_iterator &o) const { return i != o.i; }
+        inline bool operator==(const const_iterator &o) const noexcept { return i == o.i; }
+        inline bool operator!=(const const_iterator &o) const noexcept { return i != o.i; }
     };
     friend class iterator;
 
     class const_iterator
     {
+        using piter = typename QHashPrivate::iterator<Node>;
         friend class iterator;
         friend class QHash<Key, T>;
-        friend class QMultiHash<Key, T>;
         friend class QSet<Key>;
-        QHashData::Node *i;
+        piter i;
+        explicit inline const_iterator(piter it) : i(it) { }
 
     public:
-#if QT_DEPRECATED_WARNINGS_SINCE < QT_VERSION_CHECK(5, 15, 0)
-        typedef std::bidirectional_iterator_tag iterator_category;
-#else
         typedef std::forward_iterator_tag iterator_category;
-#endif
         typedef qptrdiff difference_type;
         typedef T value_type;
         typedef const T *pointer;
         typedef const T &reference;
 
-        Q_DECL_CONSTEXPR inline const_iterator() : i(nullptr) { }
-        explicit inline const_iterator(void *node)
-            : i(reinterpret_cast<QHashData::Node *>(node)) { }
-        inline const_iterator(const iterator &o)
-        { i = o.i; }
-
-        inline const Key &key() const { return concrete(i)->key; }
-        inline const T &value() const { return concrete(i)->value; }
-        inline const T &operator*() const { return concrete(i)->value; }
-        inline const T *operator->() const { return &concrete(i)->value; }
-        Q_DECL_CONSTEXPR inline bool operator==(const const_iterator &o) const { return i == o.i; }
-        Q_DECL_CONSTEXPR inline bool operator!=(const const_iterator &o) const { return i != o.i; }
-
-        inline const_iterator &operator++() {
-            i = QHashData::nextNode(i);
-            return *this;
-        }
-        inline const_iterator operator++(int) {
-            const_iterator r = *this;
-            i = QHashData::nextNode(i);
-            return r;
-        }
-#if QT_DEPRECATED_SINCE(5, 15)
-        inline QT_DEPRECATED_VERSION_5_15 const_iterator &operator--()
+        constexpr const_iterator() noexcept = default;
+        inline const_iterator(const iterator &o) noexcept : i(o.i) { }
+
+        inline const Key &key() const noexcept { return i.node()->key; }
+        inline const T &value() const noexcept { return i.node()->value; }
+        inline const T &operator*() const noexcept { return i.node()->value; }
+        inline const T *operator->() const noexcept { return &i.node()->value; }
+        inline bool operator==(const const_iterator &o) const noexcept { return i == o.i; }
+        inline bool operator!=(const const_iterator &o) const noexcept { return i != o.i; }
+
+        inline const_iterator &operator++() noexcept
         {
-            i = QHashData::previousNode(i);
+            ++i;
             return *this;
         }
-        inline QT_DEPRECATED_VERSION_5_15 const_iterator operator--(int)
+        inline const_iterator operator++(int) noexcept
         {
             const_iterator r = *this;
-            i = QHashData::previousNode(i);
+            ++i;
             return r;
         }
-        inline QT_DEPRECATED_VERSION_5_15 const_iterator operator+(int j) const
-        { const_iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
-        inline QT_DEPRECATED_VERSION_5_15 const_iterator operator-(int j) const { return operator+(-j); }
-        inline QT_DEPRECATED_VERSION_5_15 const_iterator &operator+=(int j) { return *this = *this + j; }
-        inline QT_DEPRECATED_VERSION_5_15 const_iterator &operator-=(int j) { return *this = *this - j; }
-        friend inline QT_DEPRECATED_VERSION_5_15 const_iterator operator+(int j, const_iterator k)
-        {
-            return k + j;
-        }
-#endif
     };
     friend class const_iterator;
 
@@ -450,641 +1050,744 @@ public:
 
     public:
         typedef typename const_iterator::iterator_category iterator_category;
-        typedef typename const_iterator::difference_type difference_type;
+        typedef qptrdiff difference_type;
         typedef Key value_type;
         typedef const Key *pointer;
         typedef const Key &reference;
 
-        key_iterator() = default;
-        explicit key_iterator(const_iterator o) : i(o) { }
+        key_iterator() noexcept = default;
+        explicit key_iterator(const_iterator o) noexcept : i(o) { }
 
-        const Key &operator*() const { return i.key(); }
-        const Key *operator->() const { return &i.key(); }
-        bool operator==(key_iterator o) const { return i == o.i; }
-        bool operator!=(key_iterator o) const { return i != o.i; }
+        const Key &operator*() const noexcept { return i.key(); }
+        const Key *operator->() const noexcept { return &i.key(); }
+        bool operator==(key_iterator o) const noexcept { return i == o.i; }
+        bool operator!=(key_iterator o) const noexcept { return i != o.i; }
 
-        inline key_iterator &operator++() { ++i; return *this; }
-        inline key_iterator operator++(int) { return key_iterator(i++);}
-#if QT_DEPRECATED_SINCE(5, 15)
-        inline QT_DEPRECATED_VERSION_5_15 key_iterator &operator--()
-        {
-            --i;
-            return *this;
-        }
-        inline QT_DEPRECATED_VERSION_5_15 key_iterator operator--(int) { return key_iterator(i--); }
-#endif
-        const_iterator base() const { return i; }
+        inline key_iterator &operator++() noexcept { ++i; return *this; }
+        inline key_iterator operator++(int) noexcept { return key_iterator(i++);}
+        const_iterator base() const noexcept { return i; }
     };
 
     typedef QKeyValueIterator<const Key&, const T&, const_iterator> const_key_value_iterator;
     typedef QKeyValueIterator<const Key&, T&, iterator> key_value_iterator;
 
     // STL style
-    inline iterator begin() { detach(); return iterator(d->firstNode()); }
-    inline const_iterator begin() const { return const_iterator(d->firstNode()); }
-    inline const_iterator cbegin() const { return const_iterator(d->firstNode()); }
-    inline const_iterator constBegin() const { return const_iterator(d->firstNode()); }
-    inline iterator end() { detach(); return iterator(e); }
-    inline const_iterator end() const { return const_iterator(e); }
-    inline const_iterator cend() const { return const_iterator(e); }
-    inline const_iterator constEnd() const { return const_iterator(e); }
-    inline key_iterator keyBegin() const { return key_iterator(begin()); }
-    inline key_iterator keyEnd() const { return key_iterator(end()); }
+    inline iterator begin() { detach(); return iterator(d->begin()); }
+    inline const_iterator begin() const noexcept { return d ? const_iterator(d->begin()): const_iterator(); }
+    inline const_iterator cbegin() const noexcept { return d ? const_iterator(d->begin()): const_iterator(); }
+    inline const_iterator constBegin() const noexcept { return d ? const_iterator(d->begin()): const_iterator(); }
+    inline iterator end() noexcept { return iterator(); }
+    inline const_iterator end() const noexcept { return const_iterator(); }
+    inline const_iterator cend() const noexcept { return const_iterator(); }
+    inline const_iterator constEnd() const noexcept { return const_iterator(); }
+    inline key_iterator keyBegin() const noexcept { return key_iterator(begin()); }
+    inline key_iterator keyEnd() const noexcept { return key_iterator(end()); }
     inline key_value_iterator keyValueBegin() { return key_value_iterator(begin()); }
     inline key_value_iterator keyValueEnd() { return key_value_iterator(end()); }
-    inline const_key_value_iterator keyValueBegin() const { return const_key_value_iterator(begin()); }
-    inline const_key_value_iterator constKeyValueBegin() const { return const_key_value_iterator(begin()); }
-    inline const_key_value_iterator keyValueEnd() const { return const_key_value_iterator(end()); }
-    inline const_key_value_iterator constKeyValueEnd() const { return const_key_value_iterator(end()); }
+    inline const_key_value_iterator keyValueBegin() const noexcept { return const_key_value_iterator(begin()); }
+    inline const_key_value_iterator constKeyValueBegin() const noexcept { return const_key_value_iterator(begin()); }
+    inline const_key_value_iterator keyValueEnd() const noexcept { return const_key_value_iterator(end()); }
+    inline const_key_value_iterator constKeyValueEnd() const noexcept { return const_key_value_iterator(end()); }
 
-    QPair<iterator, iterator> equal_range(const Key &key);
-    QPair<const_iterator, const_iterator> equal_range(const Key &key) const noexcept;
-    iterator erase(iterator it) { return erase(const_iterator(it.i)); }
-    iterator erase(const_iterator it);
+    iterator erase(const_iterator it)
+    {
+        Q_ASSERT(it != constEnd());
+        detach();
+        // ensure a valid iterator across the detach:
+        iterator i = iterator{d->detachedIterator(it.i)};
 
-    // more Qt
-    typedef iterator Iterator;
-    typedef const_iterator ConstIterator;
-    inline int count() const { return d->size; }
-    iterator find(const Key &key);
-    const_iterator find(const Key &key) const;
-    const_iterator constFind(const Key &key) const;
-    iterator insert(const Key &key, const T &value);
-    void insert(const QHash &hash);
-#if QT_DEPRECATED_SINCE(5, 15)
-    QT_DEPRECATED_VERSION_X_5_15("Use QMultiHash for hashes storing multiple values with the same key.") iterator insertMulti(const Key &key, const T &value);
-    QT_DEPRECATED_VERSION_X_5_15("Use QMultiHash for hashes storing multiple values with the same key.") QHash &unite(const QHash &other);
-#endif
+        i.i = d->erase(i.i);
+        return i;
+    }
 
-    // STL compatibility
-    typedef T mapped_type;
-    typedef Key key_type;
-    typedef qptrdiff difference_type;
-    typedef int size_type;
+    QPair<iterator, iterator> equal_range(const Key &key)
+    {
+        auto first = find(key);
+        auto second = first;
+        if (second != iterator())
+            ++second;
+        return qMakePair(first, second);
+    }
 
-    inline bool empty() const { return isEmpty(); }
+    QPair<const_iterator, const_iterator> equal_range(const Key &key) const noexcept
+    {
+        auto first = find(key);
+        auto second = first;
+        if (second != iterator())
+            ++second;
+        return qMakePair(first, second);
+    }
 
-#ifdef QT_QHASH_DEBUG
-    inline void dump() const { d->dump(); }
-    inline void checkSanity() const { d->checkSanity(); }
-#endif
+    typedef iterator Iterator;
+    typedef const_iterator ConstIterator;
+    inline qsizetype count() const noexcept { return d ? qsizetype(d->size) : 0; }
+    iterator find(const Key &key)
+    {
+        if (isEmpty()) // prevents detaching shared null
+            return end();
+        detach();
+        auto it = d->find(key);
+        if (it.isUnused())
+            it = d->end();
+        return iterator(it);
+    }
+    const_iterator find(const Key &key) const noexcept
+    {
+        if (isEmpty())
+            return end();
+        auto it = d->find(key);
+        if (it.isUnused())
+            it = d->end();
+        return const_iterator(it);
+    }
+    const_iterator constFind(const Key &key) const noexcept
+    {
+        return find(key);
+    }
+    iterator insert(const Key &key, const T &value)
+    {
+        detach();
 
-private:
-    void detach_helper();
-    void freeData(QHashData *d);
-    Node **findNode(const Key &key, uint *hp = nullptr) const;
-    Node **findNode(const Key &key, uint h) const;
-    Node *createNode(uint h, const Key &key, const T &value, Node **nextNode);
-    void deleteNode(Node *node);
-    static void deleteNode2(QHashData::Node *node);
-
-    static void duplicateNode(QHashData::Node *originalNode, void *newNode);
-
-    bool isValidIterator(const iterator &it) const noexcept
-    { return isValidNode(it.i); }
-    bool isValidIterator(const const_iterator &it) const noexcept
-    { return isValidNode(it.i); }
-    bool isValidNode(QHashData::Node *node) const noexcept
-    {
-#if defined(QT_DEBUG) && !defined(Q_HASH_NO_ITERATOR_DEBUG)
-        while (node->next)
-            node = node->next;
-        return (static_cast<void *>(node) == d);
-#else
-        Q_UNUSED(node);
-        return true;
-#endif
+        auto i = d->insert(Node{key, value});
+        return iterator(i);
     }
-    friend class QSet<Key>;
-    friend class QMultiHash<Key, T>;
-};
+    void insert(const QHash &hash)
+    {
+        if (d == hash.d || !hash.d)
+            return;
+        if (!d) {
+            *this = hash;
+            return;
+        }
 
+        detach();
 
-template <class Key, class T>
-Q_INLINE_TEMPLATE void QHash<Key, T>::deleteNode(Node *node)
-{
-    deleteNode2(reinterpret_cast<QHashData::Node*>(node));
-    d->freeNode(node);
-}
+        for (auto it = hash.begin(); it != hash.end(); ++it)
+            insert(it.key(), it.value());
+    }
 
-template <class Key, class T>
-Q_INLINE_TEMPLATE void QHash<Key, T>::deleteNode2(QHashData::Node *node)
-{
-#ifdef Q_CC_BOR
-    concrete(node)->~QHashNode<Key, T>();
-#else
-    concrete(node)->~Node();
-#endif
-}
+    float load_factor() const noexcept { return d ? d->loadFactor() : 0; }
+    static float max_load_factor() noexcept { return 0.5; }
+    size_t bucket_count() const noexcept { return d ? d->numBuckets : 0; }
+    static size_t max_bucket_count() noexcept { return QHashPrivate::GrowthPolicy::maxNumBuckets(); }
 
-template <class Key, class T>
-Q_INLINE_TEMPLATE void QHash<Key, T>::duplicateNode(QHashData::Node *node, void *newNode)
-{
-    Node *concreteNode = concrete(node);
-    new (newNode) Node(concreteNode->key, concreteNode->value, concreteNode->h, nullptr);
-}
+    inline bool empty() const noexcept { return isEmpty(); }
+};
 
-template <class Key, class T>
-Q_INLINE_TEMPLATE typename QHash<Key, T>::Node *
-QHash<Key, T>::createNode(uint ah, const Key &akey, const T &avalue, Node **anextNode)
-{
-    Node *node = new (d->allocateNode(alignOfNode())) Node(akey, avalue, ah, *anextNode);
-    *anextNode = node;
-    ++d->size;
-    return node;
-}
 
-template <class Key, class T>
-Q_OUTOFLINE_TEMPLATE void QHash<Key, T>::freeData(QHashData *x)
-{
-    x->free_helper(deleteNode2);
-}
 
 template <class Key, class T>
-Q_INLINE_TEMPLATE void QHash<Key, T>::clear()
+class QMultiHash
 {
-    *this = QHash();
-}
+    using Node = QHashPrivate::MultiNode<Key, T>;
+    using Data = QHashPrivate::Data<Node>;
+    using Chain = QHashPrivate::MultiNodeChain<T>;
 
-template <class Key, class T>
-Q_OUTOFLINE_TEMPLATE void QHash<Key, T>::detach_helper()
-{
-    QHashData *x = d->detach_helper(duplicateNode, deleteNode2, sizeof(Node), alignOfNode());
-    if (!d->ref.deref())
-        freeData(d);
-    d = x;
-}
+    Data  *d = nullptr;
+    qsizetype m_size = 0;
 
-template <class Key, class T>
-Q_INLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::operator=(const QHash &other)
-{
-    if (d != other.d) {
-        QHashData *o = other.d;
-        o->ref.ref();
-        if (!d->ref.deref())
-            freeData(d);
-        d = o;
-        if (!d->sharable)
-            detach_helper();
+public:
+    using key_type = Key;
+    using mapped_type = T;
+    using value_type = T;
+    using size_type = qsizetype;
+    using difference_type = qsizetype;
+    using reference = T &;
+    using const_reference = const T &;
+
+    QMultiHash() noexcept = default;
+    inline QMultiHash(std::initializer_list<std::pair<Key,T> > list)
+        : d(new Data(list.size()))
+    {
+        for (typename std::initializer_list<std::pair<Key,T> >::const_iterator it = list.begin(); it != list.end(); ++it)
+            insert(it->first, it->second);
     }
-    return *this;
-}
-
-template <class Key, class T>
-Q_INLINE_TEMPLATE T QHash<Key, T>::value(const Key &akey) const
-{
-    Node *node;
-    if (d->size == 0 || (node = *findNode(akey)) == e) {
-        return T();
-    } else {
-        return node->value;
+#ifdef Q_QDOC
+    template <typename InputIterator>
+    QMultiHash(InputIterator f, InputIterator l);
+#else
+    template <typename InputIterator, QtPrivate::IfAssociativeIteratorHasKeyAndValue<InputIterator> = true>
+    QMultiHash(InputIterator f, InputIterator l)
+    {
+        QtPrivate::reserveIfForwardIterator(this, f, l);
+        for (; f != l; ++f)
+            insert(f.key(), f.value());
     }
-}
 
-template <class Key, class T>
-Q_INLINE_TEMPLATE T QHash<Key, T>::value(const Key &akey, const T &adefaultValue) const
-{
-    Node *node;
-    if (d->size == 0 || (node = *findNode(akey)) == e) {
-        return adefaultValue;
-    } else {
-        return node->value;
+    template <typename InputIterator, QtPrivate::IfAssociativeIteratorHasFirstAndSecond<InputIterator> = true>
+    QMultiHash(InputIterator f, InputIterator l)
+    {
+        QtPrivate::reserveIfForwardIterator(this, f, l);
+        for (; f != l; ++f)
+            insert(f->first, f->second);
+    }
+#endif
+    QMultiHash(const QMultiHash &other) noexcept
+        : d(other.d), m_size(other.m_size)
+    {
+        if (d)
+            d->ref.ref();
+    }
+    ~QMultiHash()
+    {
+        if (d && !d->ref.deref())
+            delete d;
     }
-}
-
-template <class Key, class T>
-Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::keys() const
-{
-    QList<Key> res;
-    res.reserve(size());
-    const_iterator i = begin();
-    while (i != end()) {
-        res.append(i.key());
-        ++i;
-    }
-    return res;
-}
 
-template <class Key, class T>
-Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::keys(const T &avalue) const
-{
-    QList<Key> res;
-    const_iterator i = begin();
-    while (i != end()) {
-        if (i.value() == avalue)
-            res.append(i.key());
-        ++i;
-    }
-    return res;
-}
+    QMultiHash &operator=(const QMultiHash &other) noexcept(std::is_nothrow_destructible<Node>::value)
+    {
+        if (d != other.d) {
+            Data *o = other.d;
+            if (o)
+                o->ref.ref();
+            if (d && !d->ref.deref())
+                delete d;
+            d = o;
+            m_size = other.m_size;
+        }
+        return *this;
+    }
+    QMultiHash(QMultiHash &&other) noexcept : d(other.d), m_size(other.m_size)
+    {
+        other.d = nullptr;
+        other.m_size = 0;
+    }
+    QMultiHash &operator=(QMultiHash &&other) noexcept(std::is_nothrow_destructible<Node>::value)
+    {
+        QMultiHash moved(std::move(other));
+        swap(moved);
+        return *this;
+    }
 
-template <class Key, class T>
-Q_OUTOFLINE_TEMPLATE Key QHash<Key, T>::key(const T &avalue) const
-{
-    return key(avalue, Key());
-}
+    QMultiHash(const QHash<Key, T> &other)
+        : QMultiHash(other.begin(), other.end())
+    {}
+    void swap(QMultiHash &other) noexcept { qSwap(d, other.d); qSwap(m_size, other.m_size); }
 
-template <class Key, class T>
-Q_OUTOFLINE_TEMPLATE Key QHash<Key, T>::key(const T &avalue, const Key &defaultValue) const
-{
-    const_iterator i = begin();
-    while (i != end()) {
-        if (i.value() == avalue)
-            return i.key();
-        ++i;
+    bool operator==(const QMultiHash &other) const noexcept
+    {
+        if (d == other.d)
+            return true;
+        if (!d || ! other.d)
+            return false;
+        if (m_size != other.m_size || d->size != other.d->size)
+            return false;
+        for (auto it = other.d->begin(); it != other.d->end(); ++it) {
+            auto i = d->find(it.node()->key);
+            if (i == d->end())
+                return false;
+            Chain *e = it.node()->value;
+            while (e) {
+                Chain *oe = i.node()->value;
+                while (oe) {
+                    if (oe->value == e->value)
+                        break;
+                    oe = oe->next;
+                }
+                if (!oe)
+                    return false;
+                e = e->next;
+            }
+        }
+        // all values must be the same as size is the same
+        return true;
     }
+    bool operator!=(const QMultiHash &other) const noexcept { return !(*this == other); }
 
-    return defaultValue;
-}
+    inline qsizetype size() const noexcept { return m_size; }
 
-template <class Key, class T>
-Q_OUTOFLINE_TEMPLATE QList<T> QHash<Key, T>::values() const
-{
-    QList<T> res;
-    res.reserve(size());
-    const_iterator i = begin();
-    while (i != end()) {
-        res.append(i.value());
-        ++i;
-    }
-    return res;
-}
+    inline bool isEmpty() const noexcept { return !m_size; }
 
-template <class Key, class T>
-Q_OUTOFLINE_TEMPLATE int QHash<Key, T>::count(const Key &akey) const
-{
-    int cnt = 0;
-    Node *node = *findNode(akey);
-    if (node != e) {
-        do {
-            ++cnt;
-        } while ((node = node->next) != e && node->key == akey);
-    }
-    return cnt;
-}
+    inline qsizetype capacity() const noexcept { return d ? qsizetype(d->numBuckets >> 1) : 0; }
+    void reserve(qsizetype size)
+    {
+        if (isDetached())
+            d->rehash(size);
+        else
+            d = Data::detached(d, size_t(size));
+    }
+    inline void squeeze() { reserve(0); }
 
-template <class Key, class T>
-Q_INLINE_TEMPLATE const T QHash<Key, T>::operator[](const Key &akey) const
-{
-    return value(akey);
-}
+    inline void detach() { if (!d || d->ref.isShared()) d = Data::detached(d); }
+    inline bool isDetached() const noexcept { return d && !d->ref.isShared(); }
+    bool isSharedWith(const QMultiHash &other) const noexcept { return d == other.d; }
 
-template <class Key, class T>
-Q_INLINE_TEMPLATE T &QHash<Key, T>::operator[](const Key &akey)
-{
-    detach();
+    void clear() noexcept(std::is_nothrow_destructible<Node>::value)
+    {
+        if (d && !d->ref.deref())
+            delete d;
+        d = nullptr;
+        m_size = 0;
+    }
 
-    uint h;
-    Node **node = findNode(akey, &h);
-    if (*node == e) {
-        if (d->willGrow())
-            node = findNode(akey, h);
-        return createNode(h, akey, T(), node)->value;
+    qsizetype remove(const Key &key)
+    {
+        if (isEmpty()) // prevents detaching shared null
+            return 0;
+        detach();
+
+        auto it = d->find(key);
+        if (it.isUnused())
+            return 0;
+        qsizetype n = Node::freeChain(it.node());
+        m_size -= n;
+        Q_ASSERT(m_size >= 0);
+        d->erase(it);
+        return n;
     }
-    return (*node)->value;
-}
+    T take(const Key &key)
+    {
+        if (isEmpty()) // prevents detaching shared null
+            return T();
+        detach();
 
-template <class Key, class T>
-Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::insert(const Key &akey,
-                                                                         const T &avalue)
-{
-    detach();
+        auto it = d->find(key);
+        if (it.isUnused())
+            return T();
+        Q_ASSERT(it.node()->value.size());
+        Chain *e = it.node()->value;
+        Q_ASSERT(e);
+        if (!e->next)
+            d->erase(it);
+        else
+            it.node()->value = e->next;
+        --m_size;
+        Q_ASSERT(m_size >= 0);
+        T t = std::move(e->value);
+        delete e;
+        return t;
+    }
 
-    uint h;
-    Node **node = findNode(akey, &h);
-    if (*node == e) {
-        if (d->willGrow())
-            node = findNode(akey, h);
-        return iterator(createNode(h, akey, avalue, node));
+    bool contains(const Key &key) const noexcept
+    {
+        if (!d)
+            return false;
+        return d->findNode(key) != nullptr;
     }
 
-    if (!std::is_same<T, QHashDummyValue>::value)
-        (*node)->value = avalue;
-    return iterator(*node);
-}
+    Key key(const T &value, const Key &defaultKey = Key()) const noexcept
+    {
+        if (d) {
+            auto i = d->begin();
+            while (i != d->end()) {
+                Chain *e = i.node()->value;
+                if (e->contains(value))
+                    return i.node()->key;
+                ++i;
+            }
+        }
 
-template <class Key, class T>
-Q_INLINE_TEMPLATE void QHash<Key, T>::insert(const QHash &hash)
-{
-    if (d == hash.d)
-        return;
-
-    detach();
-
-    QHashData::Node *i = hash.d->firstNode();
-    QHashData::Node *end = reinterpret_cast<QHashData::Node *>(hash.e);
-    while (i != end) {
-        Node *n = concrete(i);
-        Node **node = findNode(n->key, n->h);
-        if (*node == e) {
-            if (d->willGrow())
-                node = findNode(n->key, n->h);
-            createNode(n->h, n->key, n->value, node);
-        } else {
-            if (!std::is_same<T, QHashDummyValue>::value)
-                (*node)->value = n->value;
+        return defaultKey;
+    }
+    T value(const Key &key, const T &defaultValue = T()) const noexcept
+    {
+        if (d) {
+            Node *n = d->findNode(key);
+            if (n) {
+                Q_ASSERT(n->value);
+                return n->value->value;
+            }
         }
-        i = QHashData::nextNode(i);
+        return defaultValue;
     }
-}
 
-template <class Key, class T>
-Q_OUTOFLINE_TEMPLATE int QHash<Key, T>::remove(const Key &akey)
-{
-    if (isEmpty()) // prevents detaching shared null
-        return 0;
-    detach();
-
-    int oldSize = d->size;
-    Node **node = findNode(akey);
-    if (*node != e) {
-        bool deleteNext = true;
-        do {
-            Node *next = (*node)->next;
-            deleteNext = (next != e && next->key == (*node)->key);
-            deleteNode(*node);
-            *node = next;
-            --d->size;
-        } while (deleteNext);
-        d->hasShrunk();
-    }
-    return oldSize - d->size;
-}
+    T &operator[](const Key &key)
+    {
+        detach();
+        Node *n = d->findAndInsertNode(key);
+        Q_ASSERT(n);
+        return n->value->value;
+    }
 
-template <class Key, class T>
-Q_OUTOFLINE_TEMPLATE T QHash<Key, T>::take(const Key &akey)
-{
-    if (isEmpty()) // prevents detaching shared null
-        return T();
-    detach();
-
-    Node **node = findNode(akey);
-    if (*node != e) {
-        T t = std::move((*node)->value);
-        Node *next = (*node)->next;
-        deleteNode(*node);
-        *node = next;
-        --d->size;
-        d->hasShrunk();
-        return t;
+    const T operator[](const Key &key) const noexcept
+    {
+        return value(key);
     }
-    return T();
-}
 
-template <class Key, class T>
-Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::erase(const_iterator it)
-{
-    Q_ASSERT_X(isValidIterator(it), "QHash::erase", "The specified iterator argument 'it' is invalid");
-
-    if (it == const_iterator(e))
-        return iterator(it.i);
-
-    if (d->ref.isShared()) {
-        // save 'it' across the detach:
-        int bucketNum = (it.i->h % d->numBuckets);
-        const_iterator bucketIterator(*(d->buckets + bucketNum));
-        int stepsFromBucketStartToIte = 0;
-        while (bucketIterator != it) {
-            ++stepsFromBucketStartToIte;
-            ++bucketIterator;
-        }
-        detach();
-        it = const_iterator(*(d->buckets + bucketNum));
-        while (stepsFromBucketStartToIte > 0) {
-            --stepsFromBucketStartToIte;
-            ++it;
+    QVector<Key> uniqueKeys() const
+    {
+        QVector<Key> res;
+        if (d) {
+            auto i = d->begin();
+            while (i != d->end()) {
+                res.append(i.node()->key);
+                ++i;
+            }
         }
+        return res;
     }
 
-    iterator ret(it.i);
-    ++ret;
+    QVector<Key> keys() const
+    {
+        return QVector<Key>(keyBegin(), keyEnd());
+    }
+    QVector<Key> keys(const T &value) const
+    {
+        QVector<Key> res;
+        const_iterator i = begin();
+        while (i != end()) {
+            if (i.value()->contains(value))
+                res.append(i.key());
+            ++i;
+        }
+        return res;
+    }
+    QVector<T> values() const
+    {
+        return QVector<T>(begin(), end());
+    }
+    QVector<T> values(const Key &key) const
+    {
+        QVector<T> values;
+        if (d) {
+            Node *n = d->findNode(key);
+            if (n) {
+                Chain *e = n->value;
+                while (e) {
+                    values.append(e->value);
+                    e = e->next;
+                }
+            }
+        }
+        return values;
+    }
 
-    Node *node = concrete(it.i);
-    Node **node_ptr = reinterpret_cast<Node **>(&d->buckets[node->h % d->numBuckets]);
-    while (*node_ptr != node)
-        node_ptr = &(*node_ptr)->next;
-    *node_ptr = node->next;
-    deleteNode(node);
-    --d->size;
-    return ret;
-}
+    class const_iterator;
 
-template <class Key, class T>
-Q_INLINE_TEMPLATE void QHash<Key, T>::reserve(int asize)
-{
-    detach();
-    d->rehash(-qMax(asize, 1));
-}
+    class iterator
+    {
+        using piter = typename QHashPrivate::iterator<Node>;
+        friend class const_iterator;
+        friend class QMultiHash<Key, T>;
+        piter i;
+        Chain **e = nullptr;
+        explicit inline iterator(piter it, Chain **entry = nullptr) noexcept : i(it), e(entry)
+        {
+            if (!it.atEnd() && !e) {
+                e = &it.node()->value;
+                Q_ASSERT(e && *e);
+            }
+        }
 
-template <class Key, class T>
-Q_INLINE_TEMPLATE typename QHash<Key, T>::const_iterator QHash<Key, T>::find(const Key &akey) const
-{
-    return const_iterator(*findNode(akey));
-}
+    public:
+        typedef std::forward_iterator_tag iterator_category;
+        typedef qptrdiff difference_type;
+        typedef T value_type;
+        typedef T *pointer;
+        typedef T &reference;
 
-template <class Key, class T>
-Q_INLINE_TEMPLATE typename QHash<Key, T>::const_iterator QHash<Key, T>::constFind(const Key &akey) const
-{
-    return const_iterator(*findNode(akey));
-}
+        constexpr iterator() noexcept = default;
+
+        inline const Key &key() const noexcept { return i.node()->key; }
+        inline T &value() const noexcept { return (*e)->value; }
+        inline T &operator*() const noexcept { return (*e)->value; }
+        inline T *operator->() const noexcept { return &(*e)->value; }
+        inline bool operator==(const iterator &o) const noexcept { return e == o.e; }
+        inline bool operator!=(const iterator &o) const noexcept { return e != o.e; }
+
+        inline iterator &operator++() noexcept {
+            Q_ASSERT(e && *e);
+            e = &(*e)->next;
+            Q_ASSERT(e);
+            if (!*e) {
+                ++i;
+                e = i.atEnd() ? nullptr : &i.node()->value;
+            }
+            return *this;
+        }
+        inline iterator operator++(int) noexcept {
+            iterator r = *this;
+            ++(*this);
+            return r;
+        }
 
-template <class Key, class T>
-Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::find(const Key &akey)
-{
-    detach();
-    return iterator(*findNode(akey));
-}
+        inline bool operator==(const const_iterator &o) const noexcept { return e == o.e; }
+        inline bool operator!=(const const_iterator &o) const noexcept { return e != o.e; }
+    };
+    friend class iterator;
 
-template <class Key, class T>
-Q_INLINE_TEMPLATE bool QHash<Key, T>::contains(const Key &akey) const
-{
-    return *findNode(akey) != e;
-}
+    class const_iterator
+    {
+        using piter = typename QHashPrivate::iterator<Node>;
+        friend class iterator;
+        friend class QMultiHash<Key, T>;
+        piter i;
+        Chain **e = nullptr;
+        explicit inline const_iterator(piter it, Chain **entry = nullptr) noexcept : i(it), e(entry)
+        {
+            if (!it.atEnd() && !e) {
+                e = &it.node()->value;
+                Q_ASSERT(e && *e);
+            }
+        }
 
-template <class Key, class T>
-Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::Node **QHash<Key, T>::findNode(const Key &akey, uint h) const
-{
-    Node **node;
+    public:
+        typedef std::forward_iterator_tag iterator_category;
+        typedef qptrdiff difference_type;
+        typedef T value_type;
+        typedef const T *pointer;
+        typedef const T &reference;
 
-    if (d->numBuckets) {
-        node = reinterpret_cast<Node **>(&d->buckets[h % d->numBuckets]);
-        Q_ASSERT(*node == e || (*node)->next);
-        while (*node != e && !(*node)->same_key(h, akey))
-            node = &(*node)->next;
-    } else {
-        node = const_cast<Node **>(reinterpret_cast<const Node * const *>(&e));
-    }
-    return node;
-}
+        constexpr const_iterator() noexcept = default;
+        inline const_iterator(const iterator &o) noexcept : i(o.i), e(o.e) { }
+
+        inline const Key &key() const noexcept { return i.node()->key; }
+        inline T &value() const noexcept { return (*e)->value; }
+        inline T &operator*() const noexcept { return (*e)->value; }
+        inline T *operator->() const noexcept { return &(*e)->value; }
+        inline bool operator==(const const_iterator &o) const noexcept { return e == o.e; }
+        inline bool operator!=(const const_iterator &o) const noexcept { return e != o.e; }
+
+        inline const_iterator &operator++() noexcept {
+            Q_ASSERT(e && *e);
+            e = &(*e)->next;
+            Q_ASSERT(e);
+            if (!*e) {
+                ++i;
+                e = i.atEnd() ? nullptr : &i.node()->value;
+            }
+            return *this;
+        }
+        inline const_iterator operator++(int) noexcept
+        {
+            const_iterator r = *this;
+            ++(*this);
+            return r;
+        }
+    };
+    friend class const_iterator;
 
-template <class Key, class T>
-Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::Node **QHash<Key, T>::findNode(const Key &akey,
-                                                                            uint *ahp) const
-{
-    uint h = 0;
+    class key_iterator
+    {
+        const_iterator i;
 
-    if (d->numBuckets || ahp) {
-        h = qHash(akey, d->seed);
-        if (ahp)
-            *ahp = h;
-    }
-    return findNode(akey, h);
-}
+    public:
+        typedef typename const_iterator::iterator_category iterator_category;
+        typedef qptrdiff difference_type;
+        typedef Key value_type;
+        typedef const Key *pointer;
+        typedef const Key &reference;
 
-template <class Key, class T>
-Q_OUTOFLINE_TEMPLATE bool QHash<Key, T>::operator==(const QHash &other) const
-{
-    if (d == other.d)
-        return true;
-    if (size() != other.size())
-        return false;
+        key_iterator() noexcept = default;
+        explicit key_iterator(const_iterator o) noexcept : i(o) { }
 
-    const_iterator it = begin();
+        const Key &operator*() const noexcept { return i.key(); }
+        const Key *operator->() const noexcept { return &i.key(); }
+        bool operator==(key_iterator o) const noexcept { return i == o.i; }
+        bool operator!=(key_iterator o) const noexcept { return i != o.i; }
 
-    while (it != end()) {
-        // Build two equal ranges for i.key(); one for *this and one for other.
-        // For *this we can avoid a lookup via equal_range, as we know the beginning of the range.
-        auto thisEqualRangeStart = it;
-        const Key &thisEqualRangeKey = it.key();
-        size_type n = 0;
-        do {
-            ++it;
-            ++n;
-        } while (it != end() && it.key() == thisEqualRangeKey);
+        inline key_iterator &operator++() noexcept { ++i; return *this; }
+        inline key_iterator operator++(int) noexcept { return key_iterator(i++);}
+        const_iterator base() const noexcept { return i; }
+    };
 
-        const auto otherEqualRange = other.equal_range(thisEqualRangeKey);
+    typedef QKeyValueIterator<const Key&, const T&, const_iterator> const_key_value_iterator;
+    typedef QKeyValueIterator<const Key&, T&, iterator> key_value_iterator;
 
-        if (n != std::distance(otherEqualRange.first, otherEqualRange.second))
-            return false;
+    // STL style
+    inline iterator begin() { detach(); return iterator(d->begin()); }
+    inline const_iterator begin() const noexcept { return d ? const_iterator(d->begin()): const_iterator(); }
+    inline const_iterator cbegin() const noexcept { return d ? const_iterator(d->begin()): const_iterator(); }
+    inline const_iterator constBegin() const noexcept { return d ? const_iterator(d->begin()): const_iterator(); }
+    inline iterator end() noexcept { return iterator(); }
+    inline const_iterator end() const noexcept { return const_iterator(); }
+    inline const_iterator cend() const noexcept { return const_iterator(); }
+    inline const_iterator constEnd() const noexcept { return const_iterator(); }
+    inline key_iterator keyBegin() const noexcept { return key_iterator(begin()); }
+    inline key_iterator keyEnd() const noexcept { return key_iterator(end()); }
+    inline key_value_iterator keyValueBegin() noexcept { return key_value_iterator(begin()); }
+    inline key_value_iterator keyValueEnd() noexcept { return key_value_iterator(end()); }
+    inline const_key_value_iterator keyValueBegin() const noexcept { return const_key_value_iterator(begin()); }
+    inline const_key_value_iterator constKeyValueBegin() const noexcept { return const_key_value_iterator(begin()); }
+    inline const_key_value_iterator keyValueEnd() const noexcept { return const_key_value_iterator(end()); }
+    inline const_key_value_iterator constKeyValueEnd() const noexcept { return const_key_value_iterator(end()); }
+
+    iterator detach(const_iterator it)
+    {
+        auto i = it.i;
+        Chain **e = it.e;
+        if (d->ref.isShared()) {
+            // need to store iterator position before detaching
+            qsizetype n = 0;
+            Chain *entry = i.node()->value;
+            while (entry != *it.e) {
+                ++n;
+                entry = entry->next;
+            }
+            Q_ASSERT(entry);
+            detach_helper();
 
-        // Keys in the ranges are equal by construction; this checks only the values.
-        if (!qt_is_permutation(thisEqualRangeStart, it, otherEqualRange.first, otherEqualRange.second))
-            return false;
+            i = d->detachedIterator(i);
+            e = &i.node()->value;
+            while (n) {
+                e = &(*e)->next;
+                --n;
+            }
+            Q_ASSERT(e && *e);
+        }
+        return iterator(i, e);
     }
 
-    return true;
-}
-
-template <class Key, class T>
-QPair<typename QHash<Key, T>::iterator, typename QHash<Key, T>::iterator> QHash<Key, T>::equal_range(const Key &akey)
-{
-    detach();
-    auto pair = qAsConst(*this).equal_range(akey);
-    return qMakePair(iterator(pair.first.i), iterator(pair.second.i));
-}
-
-template <class Key, class T>
-QPair<typename QHash<Key, T>::const_iterator, typename QHash<Key, T>::const_iterator> QHash<Key, T>::equal_range(const Key &akey) const noexcept
-{
-    Node *node = *findNode(akey);
-    const_iterator firstIt = const_iterator(node);
-
-    if (node != e) {
-        // equal keys must hash to the same value and so they all
-        // end up in the same bucket. So we can use node->next,
-        // which only works within a bucket, instead of (out-of-line)
-        // QHashData::nextNode()
-        while (node->next != e && node->next->key == akey)
-            node = node->next;
-
-        // 'node' may be the last node in the bucket. To produce the end iterator, we'd
-        // need to enter the next bucket in this case, so we need to use
-        // QHashData::nextNode() here, which, unlike node->next above, can move between
-        // buckets.
-        node = concrete(QHashData::nextNode(reinterpret_cast<QHashData::Node *>(node)));
+    iterator erase(const_iterator it)
+    {
+        Q_ASSERT(d);
+        iterator i = detach(it);
+        Chain *e = *i.e;
+        Chain *next = e->next;
+        *i.e = next;
+        delete e;
+        if (!next) {
+            if (i.e == &i.i.node()->value) {
+                // last remaining entry, erase
+                i = iterator(d->erase(i.i));
+            } else {
+                i = iterator(++it.i);
+            }
+        }
+        --m_size;
+        Q_ASSERT(m_size >= 0);
+        return i;
     }
 
-    return qMakePair(firstIt, const_iterator(node));
-}
-
-template <class Key, class T>
-class QMultiHash : public QHash<Key, T>
-{
-public:
-    QMultiHash() noexcept {}
-    inline QMultiHash(std::initializer_list<std::pair<Key,T> > list)
+    // more Qt
+    typedef iterator Iterator;
+    typedef const_iterator ConstIterator;
+    inline qsizetype count() const noexcept { return size(); }
+    iterator find(const Key &key)
     {
-        this->reserve(int(list.size()));
-        for (typename std::initializer_list<std::pair<Key,T> >::const_iterator it = list.begin(); it != list.end(); ++it)
-            insert(it->first, it->second);
+        if (isEmpty())
+            return end();
+        detach();
+        auto it = d->find(key);
+        if (it.isUnused())
+            it = d->end();
+        return iterator(it);
     }
-#ifdef Q_QDOC
-    template <typename InputIterator>
-    QMultiHash(InputIterator f, InputIterator l);
-#else
-    template <typename InputIterator, QtPrivate::IfAssociativeIteratorHasKeyAndValue<InputIterator> = true>
-    QMultiHash(InputIterator f, InputIterator l)
+    const_iterator find(const Key &key) const noexcept
     {
-        QtPrivate::reserveIfForwardIterator(this, f, l);
-        for (; f != l; ++f)
-            insert(f.key(), f.value());
+        return constFind(key);
     }
-
-    template <typename InputIterator, QtPrivate::IfAssociativeIteratorHasFirstAndSecond<InputIterator> = true>
-    QMultiHash(InputIterator f, InputIterator l)
+    const_iterator constFind(const Key &key) const noexcept
     {
-        QtPrivate::reserveIfForwardIterator(this, f, l);
-        for (; f != l; ++f)
-            insert(f->first, f->second);
+        if (isEmpty())
+            return end();
+        auto it = d->find(key);
+        if (it.isUnused())
+            it = d->end();
+        return const_iterator(it);
+    }
+    iterator insert(const Key &key, const T &value)
+    {
+        detach();
+        auto it = d->insertMulti(key, value);
+        ++m_size;
+        return iterator(it);
     }
-#endif
-    // compiler-generated copy/move ctors/assignment operators are fine!
-    // compiler-generated destructor is fine!
-
-    QMultiHash(const QHash<Key, T> &other) : QHash<Key, T>(other) {}
-    QMultiHash(QHash<Key, T> &&other) noexcept : QHash<Key, T>(std::move(other)) {}
-    void swap(QMultiHash &other) noexcept { QHash<Key, T>::swap(other); } // prevent QMultiHash<->QHash swaps
 
-    inline typename QHash<Key, T>::iterator replace(const Key &key, const T &value)
-    { return QHash<Key, T>::insert(key, value); }
+    float load_factor() const noexcept { return d ? d->loadFactor() : 0; }
+    static float max_load_factor() noexcept { return 0.5; }
+    size_t bucket_count() const noexcept { return d ? d->numBuckets : 0; }
+    static size_t max_bucket_count() noexcept { return QHashPrivate::GrowthPolicy::maxNumBuckets(); }
 
-    typename QHash<Key, T>::iterator insert(const Key &key, const T &value);
+    inline bool empty() const noexcept { return isEmpty(); }
 
-    inline QMultiHash &unite(const QMultiHash &other);
+    inline typename QMultiHash<Key, T>::iterator replace(const Key &key, const T &value)
+    {
+        detach();
+        qsizetype s = d->size;
+        auto it = d->insert(key, value);
+        m_size += d->size - s;
+        return iterator(it);
+    }
 
     inline QMultiHash &operator+=(const QMultiHash &other)
-    { return unite(other); }
+    { this->unite(other); return *this; }
     inline QMultiHash operator+(const QMultiHash &other) const
     { QMultiHash result = *this; result += other; return result; }
 
-    using QHash<Key, T>::contains;
-    using QHash<Key, T>::remove;
-    using QHash<Key, T>::count;
-    using QHash<Key, T>::find;
-    using QHash<Key, T>::constFind;
-    using QHash<Key, T>::values;
-    using QHash<Key, T>::findNode;
-    using QHash<Key, T>::createNode;
-    using QHash<Key, T>::concrete;
-    using QHash<Key, T>::detach;
+    bool contains(const Key &key, const T &value) const noexcept
+    {
+        if (isEmpty())
+            return false;
+        auto n = d->findNode(key);
+        if (n == nullptr)
+            return false;
+        return n->value->contains(value);
+    }
 
-    using typename QHash<Key, T>::Node;
-    using typename QHash<Key, T>::iterator;
-    using typename QHash<Key, T>::const_iterator;
+    qsizetype remove(const Key &key, const T &value)
+    {
+        if (isEmpty()) // prevents detaching shared null
+            return false;
+        detach();
 
-    bool contains(const Key &key, const T &value) const;
+        auto it = d->find(key);
+        if (it.isUnused())
+            return 0;
+        qsizetype n = 0;
+        Chain **e = &it.node()->value;
+        while (*e) {
+            Chain *entry = *e;
+            if (entry->value == value) {
+                *e = entry->next;
+                delete entry;
+                ++n;
+            } else {
+                e = &entry->next;
+            }
+        }
+        if (!it.node()->value)
+            d->erase(it);
+        m_size -= n;
+        Q_ASSERT(m_size >= 0);
+        return n;
+    }
 
-    int remove(const Key &key, const T &value);
+    qsizetype count(const Key &key) const noexcept
+    {
+        auto it = d->find(key);
+        if (it.isUnused())
+            return 0;
+        qsizetype n = 0;
+        Chain *e = it.node()->value;
+        while (e) {
+            ++n;
+            e = e->next;
+        }
 
-    int count(const Key &key, const T &value) const;
+        return n;
+    }
 
-    QList<Key> uniqueKeys() const;
+    qsizetype count(const Key &key, const T &value) const noexcept
+    {
+        auto it = d->find(key);
+        if (it.isUnused())
+            return 0;
+        qsizetype n = 0;
+        Chain *e = it.node()->value;
+        while (e) {
+            if (e->value == value)
+                ++n;
+            e = e->next;
+        }
 
-    QList<T> values(const Key &akey) const;
+        return n;
+    }
 
-    typename QHash<Key, T>::iterator find(const Key &key, const T &value) {
-        typename QHash<Key, T>::iterator i(find(key));
-        typename QHash<Key, T>::iterator end(this->end());
-        while (i != end && i.key() == key) {
-            if (i.value() == value)
-                return i;
-            ++i;
-        }
-        return end;
+    iterator find(const Key &key, const T &value)
+    {
+        detach();
+        auto it = constFind(key, value);
+        return iterator(it.i, it.e);
     }
-    typename QHash<Key, T>::const_iterator find(const Key &key, const T &value) const {
-        typename QHash<Key, T>::const_iterator i(constFind(key));
-        typename QHash<Key, T>::const_iterator end(QHash<Key, T>::constEnd());
+    const_iterator find(const Key &key, const T &value) const noexcept
+    {
+        return constFind(key, value);
+    }
+    const_iterator constFind(const Key &key, const T &value) const noexcept
+    {
+        const_iterator i(constFind(key));
+        const_iterator end(constEnd());
         while (i != end && i.key() == key) {
             if (i.value() == value)
                 return i;
@@ -1092,229 +1795,108 @@ public:
         }
         return end;
     }
-    typename QHash<Key, T>::const_iterator constFind(const Key &key, const T &value) const
-        { return find(key, value); }
-private:
-    T &operator[](const Key &key);
-    const T operator[](const Key &key) const;
-};
-
-template <class Key, class T>
-Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QMultiHash<Key, T>::insert(const Key &akey, const T &avalue)
-{
-    detach();
-    this->d->willGrow();
-
-    uint h;
-    Node **nextNode = findNode(akey, &h);
-    return iterator(createNode(h, akey, avalue, nextNode));
-}
 
-template <class Key, class T>
-Q_INLINE_TEMPLATE QMultiHash<Key, T> &QMultiHash<Key, T>::unite(const QMultiHash &other)
-{
-    if (this->d == &QHashData::shared_null) {
-        *this = other;
-    } else {
-#if QT_DEPRECATED_SINCE(5, 15)
-        QMultiHash copy(other);
-        const_iterator it = copy.constEnd();
-        while (it != copy.constBegin()) {
-            it.i = QHashData::previousNode(it.i);
-            insert(it.key(), it.value());
-        }
-#else
-        const QMultiHash copy(other);
-        const_iterator it = copy.cbegin();
-        const const_iterator end = copy.cend();
-        while (it != end) {
-            const auto rangeStart = it++;
-            while (it != end && rangeStart.key() == it.key())
-                ++it;
-            const qint64 last = std::distance(rangeStart, it) - 1;
-            for (qint64 i = last; i >= 0; --i) {
-                auto next = std::next(rangeStart, i);
-                insert(next.key(), next.value());
-            }
+    QMultiHash &unite(const QMultiHash &other)
+    {
+        if (isEmpty()) {
+            *this = other;
+        } else if (other.isEmpty()) {
+            ;
+        } else {
+            QMultiHash copy(other);
+            detach();
+            for (auto cit = copy.cbegin(); cit != copy.cend(); ++cit)
+                insert(cit.key(), *cit);
         }
-#endif
+        return *this;
     }
-    return *this;
-}
-
-
-template <class Key, class T>
-Q_INLINE_TEMPLATE bool QMultiHash<Key, T>::contains(const Key &key, const T &value) const
-{
-    return constFind(key, value) != QHash<Key, T>::constEnd();
-}
 
-template <class Key, class T>
-Q_INLINE_TEMPLATE int QMultiHash<Key, T>::remove(const Key &key, const T &value)
-{
-    int n = 0;
-    typename QHash<Key, T>::iterator i(find(key));
-    typename QHash<Key, T>::iterator end(QHash<Key, T>::end());
-    while (i != end && i.key() == key) {
-        if (i.value() == value) {
-            i = this->erase(i);
-            ++n;
-        } else {
-            ++i;
-        }
+    QPair<iterator, iterator> equal_range(const Key &key)
+    {
+        detach();
+        auto pair = qAsConst(*this).equal_range(key);
+        return qMakePair(iterator(pair.first.i), iterator(pair.second.i));
     }
-    return n;
-}
 
-template <class Key, class T>
-Q_INLINE_TEMPLATE int QMultiHash<Key, T>::count(const Key &key, const T &value) const
-{
-    int n = 0;
-    typename QHash<Key, T>::const_iterator i(constFind(key));
-    typename QHash<Key, T>::const_iterator end(QHash<Key, T>::constEnd());
-    while (i != end && i.key() == key) {
-        if (i.value() == value)
-            ++n;
-        ++i;
+    QPair<const_iterator, const_iterator> equal_range(const Key &key) const noexcept
+    {
+        auto it = d->find(key);
+        if (it.isUnused())
+            return qMakePair(end(), end());
+        auto end = it;
+        ++end;
+        return qMakePair(const_iterator(it), const_iterator(end));
     }
-    return n;
-}
 
-template <class Key, class T>
-Q_OUTOFLINE_TEMPLATE QList<Key> QMultiHash<Key, T>::uniqueKeys() const
-{
-    QList<Key> res;
-    res.reserve(QHash<Key, T>::size()); // May be too much, but assume short lifetime
-    typename QHash<Key, T>::const_iterator i = QHash<Key, T>::begin();
-    if (i != QHash<Key, T>::end()) {
-        for (;;) {
-            const Key &aKey = i.key();
-            res.append(aKey);
-            do {
-                if (++i == QHash<Key, T>::end())
-                    goto break_out_of_outer_loop;
-            } while (aKey == i.key());
+private:
+    void detach_helper()
+    {
+        if (!d) {
+            d = new Data;
+            return;
         }
+        Data *dd = new Data(*d);
+        if (!d->ref.deref())
+            delete d;
+        d = dd;
     }
-break_out_of_outer_loop:
-    return res;
-}
-
-#if QT_DEPRECATED_SINCE(5, 15)
-
-template <class Key, class T>
-Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::insertMulti(const Key &key, const T &value) {
-    return static_cast<QMultiHash<Key, T> *>(this)->insert(key, value);
-}
-
-template <class Key, class T>
-Q_OUTOFLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::unite(const QHash &other) {
-    return static_cast<QMultiHash<Key, T> *>(this)->unite(other);
-}
-
-template <class Key, class T>
-Q_OUTOFLINE_TEMPLATE QList<T> QHash<Key, T>::values(const Key &akey) const
-{
-    return static_cast<const QMultiHash<Key, T> *>(this)->values(akey);
-}
-
-template <class Key, class T>
-Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::uniqueKeys() const
-{
-    return static_cast<const QMultiHash<Key, T> *>(this)->uniqueKeys();
-}
-#endif
-
-template <class Key, class T>
-Q_OUTOFLINE_TEMPLATE QList<T> QMultiHash<Key, T>::values(const Key &akey) const
-{
-    QList<T> res;
-    Node *node = *findNode(akey);
-    if (node != this->e) {
-        do {
-            res.append(node->value);
-        } while ((node = node->next) != this->e && node->key == akey);
-    }
-    return res;
-}
+};
 
 #if !defined(QT_NO_JAVA_STYLE_ITERATORS)
-template <class Key, class T>
+template<class Key, class T>
 class QHashIterator
 {
     typedef typename QHash<Key, T>::const_iterator const_iterator;
     typedef const_iterator Item;
     QHash<Key, T> c;
     const_iterator i, n;
-    inline bool item_exists() const { return n != c.constEnd(); }
+    inline bool item_exists() const noexcept { return n != c.constEnd(); }
 
 public:
-    inline QHashIterator(const QHash<Key, T> &container)
+    inline QHashIterator(const QHash<Key, T> &container) noexcept
         : c(container), i(c.constBegin()), n(c.constEnd())
-    {
-    }
-    inline QHashIterator &operator=(const QHash<Key, T> &container)
+    { }
+    inline QHashIterator &operator=(const QHash<Key, T> &container) noexcept
     {
         c = container;
         i = c.constBegin();
         n = c.constEnd();
         return *this;
     }
-    inline void toFront()
+    inline void toFront() noexcept
     {
         i = c.constBegin();
         n = c.constEnd();
     }
-    inline void toBack()
+    inline void toBack() noexcept
     {
         i = c.constEnd();
         n = c.constEnd();
     }
-    inline bool hasNext() const { return i != c.constEnd(); }
-    inline Item next()
+    inline bool hasNext() const noexcept { return i != c.constEnd(); }
+    inline Item next() noexcept
     {
         n = i++;
         return n;
     }
-    inline Item peekNext() const { return i; }
-    inline const T &value() const
+    inline Item peekNext() const noexcept { return i; }
+    inline const T &value() const noexcept
     {
         Q_ASSERT(item_exists());
         return *n;
     }
-    inline const Key &key() const
+    inline const Key &key() const noexcept
     {
         Q_ASSERT(item_exists());
         return n.key();
     }
-    inline bool findNext(const T &t)
+    inline bool findNext(const T &t) noexcept
     {
         while ((n = i) != c.constEnd())
             if (*i++ == t)
                 return true;
         return false;
     }
-#if QT_DEPRECATED_SINCE(5, 15)
-    inline QT_DEPRECATED_VERSION_5_15 bool hasPrevious() const { return i != c.constBegin(); }
-    inline QT_DEPRECATED_VERSION_5_15 Item previous()
-    {
-        n = --i;
-        return n;
-    }
-    inline QT_DEPRECATED_VERSION_5_15 Item peekPrevious() const
-    {
-        const_iterator p = i;
-        return --p;
-    }
-    inline bool QT_DEPRECATED_VERSION_5_15 findPrevious(const T &t)
-    {
-        while (i != c.constBegin())
-            if (*(n = --i) == t)
-                return true;
-        n = c.constEnd();
-        return false;
-    }
-#endif
 };
 
 template<class Key, class T>
@@ -1325,10 +1907,11 @@ class QMutableHashIterator
     typedef iterator Item;
     QHash<Key, T> *c;
     iterator i, n;
-    inline bool item_exists() const { return const_iterator(n) != c->constEnd(); }
+    inline bool item_exists() const noexcept { return const_iterator(n) != c->constEnd(); }
 
 public:
-    inline QMutableHashIterator(QHash<Key, T> &container) : c(&container)
+    inline QMutableHashIterator(QHash<Key, T> &container)
+        : c(&container)
     {
         i = c->begin();
         n = c->end();
@@ -1345,18 +1928,18 @@ public:
         i = c->begin();
         n = c->end();
     }
-    inline void toBack()
+    inline void toBack() noexcept
     {
         i = c->end();
         n = c->end();
     }
-    inline bool hasNext() const { return const_iterator(i) != c->constEnd(); }
-    inline Item next()
+    inline bool hasNext() const noexcept { return const_iterator(i) != c->constEnd(); }
+    inline Item next() noexcept
     {
         n = i++;
         return n;
     }
-    inline Item peekNext() const { return i; }
+    inline Item peekNext() const noexcept { return i; }
     inline void remove()
     {
         if (const_iterator(n) != c->constEnd()) {
@@ -1369,49 +1952,28 @@ public:
         if (const_iterator(n) != c->constEnd())
             *n = t;
     }
-    inline T &value()
+    inline T &value() noexcept
     {
         Q_ASSERT(item_exists());
         return *n;
     }
-    inline const T &value() const
+    inline const T &value() const noexcept
     {
         Q_ASSERT(item_exists());
         return *n;
     }
-    inline const Key &key() const
+    inline const Key &key() const noexcept
     {
         Q_ASSERT(item_exists());
         return n.key();
     }
-    inline bool findNext(const T &t)
+    inline bool findNext(const T &t) noexcept
     {
         while (const_iterator(n = i) != c->constEnd())
             if (*i++ == t)
                 return true;
         return false;
     }
-#if QT_DEPRECATED_SINCE(5, 15)
-    inline QT_DEPRECATED_VERSION_5_15 bool hasPrevious() const { return const_iterator(i) != c->constBegin(); }
-    inline QT_DEPRECATED_VERSION_5_15 Item previous()
-    {
-        n = --i;
-        return n;
-    }
-    inline QT_DEPRECATED_VERSION_5_15 Item peekPrevious() const
-    {
-        iterator p = i;
-        return --p;
-    }
-    inline QT_DEPRECATED_VERSION_5_15 bool findPrevious(const T &t)
-    {
-        while (const_iterator(i) != c->constBegin())
-            if (*(n = --i) == t)
-                return true;
-        n = c->end();
-        return false;
-    }
-#endif
 };
 #endif // !QT_NO_JAVA_STYLE_ITERATORS
 
@@ -1438,8 +2000,4 @@ inline uint qHash(const QMultiHash<Key, T> &key, uint seed = 0)
 
 QT_END_NAMESPACE
 
-#if defined(Q_CC_MSVC)
-#pragma warning( pop )
-#endif
-
 #endif // QHASH_H
diff --git a/src/corelib/tools/qset.h b/src/corelib/tools/qset.h
index ef363ed52d..5b7aa8fa28 100644
--- a/src/corelib/tools/qset.h
+++ b/src/corelib/tools/qset.h
@@ -281,24 +281,14 @@ Q_INLINE_TEMPLATE bool QSet<T>::intersects(const QSet<T> &other) const
     const bool otherIsBigger = other.size() > size();
     const QSet &smallestSet = otherIsBigger ? *this : other;
     const QSet &biggestSet = otherIsBigger ? other : *this;
-    const bool equalSeeds = q_hash.d->seed == other.q_hash.d->seed;
     typename QSet::const_iterator i = smallestSet.cbegin();
     typename QSet::const_iterator e = smallestSet.cend();
 
-    if (Q_LIKELY(equalSeeds)) {
-        // If seeds are equal we take the fast path so no hash is recalculated.
-        while (i != e) {
-            if (*biggestSet.q_hash.findNode(*i, i.i.i->h) != biggestSet.q_hash.e)
-                return true;
-            ++i;
-        }
-    } else {
-        while (i != e) {
-            if (biggestSet.contains(*i))
-                return true;
-            ++i;
-        }
-     }
+    while (i != e) {
+        if (biggestSet.contains(*i))
+            return true;
+        ++i;
+    }
 
     return false;
 }
diff --git a/src/corelib/tools/qsharedpointer.cpp b/src/corelib/tools/qsharedpointer.cpp
index 0576fb2bd0..499546da4b 100644
--- a/src/corelib/tools/qsharedpointer.cpp
+++ b/src/corelib/tools/qsharedpointer.cpp
@@ -1630,7 +1630,7 @@ void QtSharedPointer::internalSafetyCheckCleanCheck()
         qFatal("Internal consistency error: the number of pointers is not equal!");
 
     if (Q_UNLIKELY(!kp->dPointers.isEmpty()))
-        qFatal("Pointer cleaning failed: %d entries remaining", kp->dPointers.size());
+        qFatal("Pointer cleaning failed: %d entries remaining", int(kp->dPointers.size()));
 #  endif
 }
 
diff --git a/tests/auto/corelib/tools/collections/tst_collections.cpp b/tests/auto/corelib/tools/collections/tst_collections.cpp
index 6fcf726c21..456c3e6cf9 100644
--- a/tests/auto/corelib/tools/collections/tst_collections.cpp
+++ b/tests/auto/corelib/tools/collections/tst_collections.cpp
@@ -1286,19 +1286,13 @@ void tst_Collections::hash()
             QHash<int, int> hash;
             for (int i = 0; i < 1000; ++i)
                 hash.insert(i, i);
-            QVERIFY(hash.capacity() == 1031);
-            hash.squeeze();
-            QVERIFY(hash.capacity() == 521);
-
-            hash.insert(12345, 12345);
-            QVERIFY(hash.capacity() == 1031);
+            QVERIFY(hash.capacity() > 1000);
 
             for (int j = 0; j < 900; ++j)
                 hash.remove(j);
-            QVERIFY(hash.capacity() == 257);
+            QVERIFY(hash.capacity() > 1000);
             hash.squeeze();
-            QVERIFY(hash.capacity() == 67);
-            hash.reserve(0);
+            QVERIFY(hash.capacity() < 200);
         }
     }
 
@@ -1331,13 +1325,21 @@ void tst_Collections::hash()
 
         hash1.unite(hash2);
         QCOMPARE(hash1.size(), 5);
-        QCOMPARE(hash1.values(),
-                (QList<QString>() << "Gamma" << "Gamma" << "Beta" << "Gamma" << "Alpha"));
+        auto values = hash1.values();
+        qSort(values);
+        QList<QString> expected;
+        expected << "Gamma" << "Gamma" << "Beta" << "Gamma" << "Alpha";
+        qSort(expected);
+        QCOMPARE(values, expected);
 
         hash2 = hash1;
         hash2.unite(hash2);
         QCOMPARE(hash2.size(), 10);
-        QCOMPARE(hash2.values(), hash1.values() + hash1.values());
+        values = hash2.values();
+        qSort(values);
+        expected += expected;
+        qSort(expected);
+        QCOMPARE(values, expected);
     }
 }
 
diff --git a/tests/auto/corelib/tools/qhash/tst_qhash.cpp b/tests/auto/corelib/tools/qhash/tst_qhash.cpp
index 2a18f8d3e6..b987adaa3f 100644
--- a/tests/auto/corelib/tools/qhash/tst_qhash.cpp
+++ b/tests/auto/corelib/tools/qhash/tst_qhash.cpp
@@ -62,7 +62,6 @@ private slots:
     void keyIterator();
     void keyValueIterator();
     void keys_values_uniqueKeys(); // slightly modified from tst_QMap
-    void noNeedlessRehashes();
 
     void const_shared_null();
     void twoArguments_qHash();
@@ -70,6 +69,8 @@ private slots:
     void eraseValidIteratorOnSharedHash();
     void equal_range();
     void insert_hash();
+
+    void badHashFunction();
 };
 
 struct IdentityTracker {
@@ -1325,20 +1326,6 @@ void tst_QHash::keys_values_uniqueKeys()
     QVERIFY(sorted(hash.values()) == sorted(QList<int>() << 2 << 1 << 4 << -2));
 }
 
-void tst_QHash::noNeedlessRehashes()
-{
-    QHash<int, int> hash;
-    for (int i = 0; i < 512; ++i) {
-        int j = (i * 345) % 512;
-        hash.insert(j, j);
-        int oldCapacity = hash.capacity();
-        hash[j] = j + 1;
-        QCOMPARE(oldCapacity, hash.capacity());
-        hash.insert(j, j + 1);
-        QCOMPARE(oldCapacity, hash.capacity());
-    }
-}
-
 void tst_QHash::const_shared_null()
 {
     QHash<int, QString> hash2;
@@ -1663,5 +1650,33 @@ void tst_QHash::insert_hash()
     }
 }
 
+struct BadKey {
+    int k;
+    BadKey(int i) : k(i) {}
+    bool operator==(const BadKey &other) const
+    {
+        return k == other.k;
+    }
+};
+
+size_t qHash(BadKey, size_t seed)
+{
+    return seed;
+}
+
+void tst_QHash::badHashFunction()
+{
+    QHash<BadKey, int> hash;
+    for (int i = 0; i < 10000; ++i)
+        hash.insert(i, i);
+
+    for (int i = 0; i < 10000; ++i)
+        QCOMPARE(hash.value(i), i);
+
+    for (int i = 10000; i < 20000; ++i)
+        QVERIFY(!hash.contains(i));
+
+}
+
 QTEST_APPLESS_MAIN(tst_QHash)
 #include "tst_qhash.moc"
diff --git a/tests/auto/corelib/tools/qset/tst_qset.cpp b/tests/auto/corelib/tools/qset/tst_qset.cpp
index 0ca8be7fa3..21ceee87c0 100644
--- a/tests/auto/corelib/tools/qset/tst_qset.cpp
+++ b/tests/auto/corelib/tools/qset/tst_qset.cpp
@@ -247,21 +247,24 @@ void tst_QSet::squeeze()
     set.squeeze();
     QVERIFY(set.capacity() < 100);
 
-    for (int i = 0; i < 500; ++i)
+    for (int i = 0; i < 512; ++i)
         set.insert(i);
-    QVERIFY(set.capacity() >= 500 && set.capacity() < 10000);
+    QVERIFY(set.capacity() == 512);
 
     set.reserve(50000);
     QVERIFY(set.capacity() >= 50000);
 
     set.squeeze();
-    QVERIFY(set.capacity() < 500);
+    QVERIFY(set.capacity() == 512);
 
     set.remove(499);
-    QVERIFY(set.capacity() < 500);
+    QVERIFY(set.capacity() == 512);
 
     set.insert(499);
-    QVERIFY(set.capacity() >= 500);
+    QVERIFY(set.capacity() == 512);
+
+    set.insert(1000);
+    QVERIFY(set.capacity() == 1024);
 
     for (int i = 0; i < 500; ++i)
         set.remove(i);
@@ -495,13 +498,13 @@ void tst_QSet::end()
 
         QVERIFY(i == j);
         QVERIFY(k == ell);
-        QVERIFY(i != k);
-        QVERIFY(j != ell);
 
         QVERIFY(set1.constBegin() != set1.constEnd());
         QVERIFY(set2.constBegin() == set2.constEnd());
+        QVERIFY(set1.constBegin() != set2.constBegin());
     }
 
+
     set2 = set1;
 
     {