intermediate changes

ref:cde9a383711a11544ce7e107a78147fb96cc4029

46 files changed, 3559 insertions, 0 deletions

diff --git a/library/cpp/containers/flat_hash/benchmark/flat_hash_benchmark.cpp b/library/cpp/containers/flat_hash/benchmark/flat_hash_benchmark.cpp
new file mode 100644
index 0000000000..040cff3fff
--- /dev/null
+++ b/library/cpp/containers/flat_hash/benchmark/flat_hash_benchmark.cpp
@@ -0,0 +1,180 @@
+#include <library/cpp/containers/flat_hash/flat_hash.h>
+
+#include <library/cpp/containers/dense_hash/dense_hash.h>
+#include <library/cpp/testing/benchmark/bench.h>
+
+#include <util/random/random.h>
+#include <util/generic/xrange.h>
+#include <util/generic/hash.h>
+
+namespace {
+
+template <class Map, size_t elemCount, class... Args>
+void RunLookupPositiveScalarKeysBench(::NBench::NCpu::TParams& iface, Args&&... args) {
+    using key_type = i32;
+    static_assert(std::is_same_v<typename Map::key_type, key_type>);
+    Map hm(std::forward<Args>(args)...);
+
+    TVector<i32> keys(elemCount);
+    for (auto& k : keys) {
+        k = RandomNumber<ui32>(std::numeric_limits<i32>::max());
+        hm.emplace(k, 0);
+    }
+
+    for (const auto i : xrange(iface.Iterations())) {
+        Y_UNUSED(i);
+        for (const auto& k : keys) {
+            Y_DO_NOT_OPTIMIZE_AWAY(hm[k]);
+        }
+    }
+}
+
+constexpr size_t TEST1_ELEM_COUNT = 10;
+constexpr size_t TEST2_ELEM_COUNT = 1000;
+constexpr size_t TEST3_ELEM_COUNT = 1000000;
+
+}
+
+/* *********************************** TEST1 ***********************************
+ * Insert TEST1_ELEM_COUNT positive integers and than make lookup.
+ * No init size provided for tables.
+ * key_type - i32
+ */
+
+Y_CPU_BENCHMARK(Test1_fh_TFlatHashMap_LinearProbing, iface) {
+    RunLookupPositiveScalarKeysBench<NFH::TFlatHashMap<i32, int>, TEST1_ELEM_COUNT>(iface);
+}
+
+/*
+Y_CPU_BENCHMARK(Test1_fh_TFlatHashMap_QuadraticProbing, iface) {
+    RunLookupPositiveScalarKeysBench<NFH::TFlatHashMap<i32, int, THash<i32>,
+                                   std::equal_to<i32>, NFlatHash::TQuadraticProbing>, TEST1_ELEM_COUNT>(iface);
+}
+*/
+
+Y_CPU_BENCHMARK(Test1_fh_TFlatHashMap_DenseProbing, iface) {
+    RunLookupPositiveScalarKeysBench<NFH::TFlatHashMap<i32, int, THash<i32>,
+                                   std::equal_to<i32>, NFlatHash::TDenseProbing>, TEST1_ELEM_COUNT>(iface);
+}
+
+
+Y_CPU_BENCHMARK(Test1_fh_TDenseHashMapStaticMarker_LinearProbing, iface) {
+    RunLookupPositiveScalarKeysBench<NFH::TDenseHashMapStaticMarker<i32, int, -1, THash<i32>,
+                                   std::equal_to<i32>, NFlatHash::TLinearProbing>, TEST1_ELEM_COUNT>(iface);
+}
+
+/*
+Y_CPU_BENCHMARK(Test1_fh_TDenseHashMapStaticMarker_QuadraticProbing, iface) {
+    RunLookupPositiveScalarKeysBench<NFH::TDenseHashMapStaticMarker<i32, int, -1, THash<i32>,
+                                   std::equal_to<i32>, NFlatHash::TQuadraticProbing>, TEST1_ELEM_COUNT>(iface);
+}
+*/
+
+Y_CPU_BENCHMARK(Test1_fh_TDenseHashMapStaticMarker_DenseProbing, iface) {
+    RunLookupPositiveScalarKeysBench<NFH::TDenseHashMapStaticMarker<i32, int, -1>, TEST1_ELEM_COUNT>(iface);
+}
+
+
+Y_CPU_BENCHMARK(Test1_foreign_TDenseHash, iface) {
+    RunLookupPositiveScalarKeysBench<TDenseHash<i32, int>, TEST1_ELEM_COUNT>(iface, (i32)-1);
+}
+
+Y_CPU_BENCHMARK(Test1_foreign_THashMap, iface) {
+    RunLookupPositiveScalarKeysBench<THashMap<i32, int>, TEST1_ELEM_COUNT>(iface);
+}
+
+/* *********************************** TEST2 ***********************************
+ * Insert TEST2_ELEM_COUNT positive integers and than make lookup.
+ * No init size provided for tables.
+ * key_type - i32
+ */
+
+Y_CPU_BENCHMARK(Test2_fh_TFlatHashMap_LinearProbing, iface) {
+    RunLookupPositiveScalarKeysBench<NFH::TFlatHashMap<i32, int>, TEST2_ELEM_COUNT>(iface);
+}
+
+/*
+Y_CPU_BENCHMARK(Test2_fh_TFlatHashMap_QuadraticProbing, iface) {
+    RunLookupPositiveScalarKeysBench<NFH::TFlatHashMap<i32, int, THash<i32>,
+                                   std::equal_to<i32>, NFlatHash::TQuadraticProbing>, TEST2_ELEM_COUNT>(iface);
+}
+*/
+
+Y_CPU_BENCHMARK(Test2_fh_TFlatHashMap_DenseProbing, iface) {
+    RunLookupPositiveScalarKeysBench<NFH::TFlatHashMap<i32, int, THash<i32>,
+                                   std::equal_to<i32>, NFlatHash::TDenseProbing>, TEST2_ELEM_COUNT>(iface);
+}
+
+
+Y_CPU_BENCHMARK(Test2_fh_TDenseHashMapStaticMarker_LinearProbing, iface) {
+    RunLookupPositiveScalarKeysBench<NFH::TDenseHashMapStaticMarker<i32, int, -1, THash<i32>,
+                                   std::equal_to<i32>, NFlatHash::TLinearProbing>, TEST2_ELEM_COUNT>(iface);
+}
+
+/*
+Y_CPU_BENCHMARK(Test2_fh_TDenseHashMapStaticMarker_QuadraticProbing, iface) {
+    RunLookupPositiveScalarKeysBench<NFH::TDenseHashMapStaticMarker<i32, int, -1, THash<i32>,
+                                   std::equal_to<i32>, NFlatHash::TQuadraticProbing>, TEST2_ELEM_COUNT>(iface);
+}
+*/
+
+Y_CPU_BENCHMARK(Test2_fh_TDenseHashMapStaticMarker_DenseProbing, iface) {
+    RunLookupPositiveScalarKeysBench<NFH::TDenseHashMapStaticMarker<i32, int, -1>, TEST2_ELEM_COUNT>(iface);
+}
+
+
+Y_CPU_BENCHMARK(Test2_foreign_TDenseHash, iface) {
+    RunLookupPositiveScalarKeysBench<TDenseHash<i32, int>, TEST2_ELEM_COUNT>(iface, (i32)-1);
+}
+
+Y_CPU_BENCHMARK(Test2_foreign_THashMap, iface) {
+    RunLookupPositiveScalarKeysBench<THashMap<i32, int>, TEST2_ELEM_COUNT>(iface);
+}
+
+/* *********************************** TEST3 ***********************************
+ * Insert TEST2_ELEM_COUNT positive integers and than make lookup.
+ * No init size provided for tables.
+ * key_type - i32
+ */
+
+Y_CPU_BENCHMARK(Test3_fh_TFlatHashMap_LinearProbing, iface) {
+    RunLookupPositiveScalarKeysBench<NFH::TFlatHashMap<i32, int>, TEST3_ELEM_COUNT>(iface);
+}
+
+/*
+Y_CPU_BENCHMARK(Test3_fh_TFlatHashMap_QuadraticProbing, iface) {
+    RunLookupPositiveScalarKeysBench<NFH::TFlatHashMap<i32, int, THash<i32>,
+                                   std::equal_to<i32>, NFlatHash::TQuadraticProbing>, TEST3_ELEM_COUNT>(iface);
+}
+*/
+
+Y_CPU_BENCHMARK(Test3_fh_TFlatHashMap_DenseProbing, iface) {
+    RunLookupPositiveScalarKeysBench<NFH::TFlatHashMap<i32, int, THash<i32>,
+                                   std::equal_to<i32>, NFlatHash::TDenseProbing>, TEST3_ELEM_COUNT>(iface);
+}
+
+
+Y_CPU_BENCHMARK(Test3_fh_TDenseHashMapStaticMarker_LinearProbing, iface) {
+    RunLookupPositiveScalarKeysBench<NFH::TDenseHashMapStaticMarker<i32, int, -1, THash<i32>,
+                                   std::equal_to<i32>, NFlatHash::TLinearProbing>, TEST3_ELEM_COUNT>(iface);
+}
+
+/*
+Y_CPU_BENCHMARK(Test3_fh_TDenseHashMapStaticMarker_QuadraticProbing, iface) {
+    RunLookupPositiveScalarKeysBench<NFH::TDenseHashMapStaticMarker<i32, int, -1, THash<i32>,
+                                   std::equal_to<i32>, NFlatHash::TQuadraticProbing>, TEST3_ELEM_COUNT>(iface);
+}
+*/
+
+Y_CPU_BENCHMARK(Test3_fh_TDenseHashMapStaticMarker_DenseProbing, iface) {
+    RunLookupPositiveScalarKeysBench<NFH::TDenseHashMapStaticMarker<i32, int, -1>, TEST3_ELEM_COUNT>(iface);
+}
+
+
+Y_CPU_BENCHMARK(Test3_foreign_TDenseHash, iface) {
+    RunLookupPositiveScalarKeysBench<TDenseHash<i32, int>, TEST3_ELEM_COUNT>(iface, (i32)-1);
+}
+
+Y_CPU_BENCHMARK(Test3_foreign_THashMap, iface) {
+    RunLookupPositiveScalarKeysBench<THashMap<i32, int>, TEST3_ELEM_COUNT>(iface);
+}
diff --git a/library/cpp/containers/flat_hash/benchmark/ya.make b/library/cpp/containers/flat_hash/benchmark/ya.make
new file mode 100644
index 0000000000..6f9aedf50d
--- /dev/null
+++ b/library/cpp/containers/flat_hash/benchmark/ya.make
@@ -0,0 +1,13 @@
+Y_BENCHMARK()
+
+OWNER(tender-bum)
+
+SRCS(
+    flat_hash_benchmark.cpp
+)
+
+PEERDIR(
+    library/cpp/containers/flat_hash
+)
+
+END()
diff --git a/library/cpp/containers/flat_hash/flat_hash.cpp b/library/cpp/containers/flat_hash/flat_hash.cpp
new file mode 100644
index 0000000000..2a16398bd4
--- /dev/null
+++ b/library/cpp/containers/flat_hash/flat_hash.cpp
@@ -0,0 +1 @@
+#include "flat_hash.h"
diff --git a/library/cpp/containers/flat_hash/flat_hash.h b/library/cpp/containers/flat_hash/flat_hash.h
new file mode 100644
index 0000000000..582b8ae8f5
--- /dev/null
+++ b/library/cpp/containers/flat_hash/flat_hash.h
@@ -0,0 +1,120 @@
+#pragma once
+
+#include <library/cpp/containers/flat_hash/lib/map.h>
+#include <library/cpp/containers/flat_hash/lib/containers.h>
+#include <library/cpp/containers/flat_hash/lib/probings.h>
+#include <library/cpp/containers/flat_hash/lib/set.h>
+#include <library/cpp/containers/flat_hash/lib/size_fitters.h>
+#include <library/cpp/containers/flat_hash/lib/expanders.h>
+
+#include <util/str_stl.h>
+
+namespace NPrivate {
+
+template <class Key, class T, class Hash, class KeyEqual, class Probing, class Alloc>
+using TFlatHashMapImpl = NFlatHash::TMap<Key, T, Hash, KeyEqual,
+                                         NFlatHash::TFlatContainer<std::pair<const Key, T>, Alloc>,
+                                         Probing, NFlatHash::TAndSizeFitter,
+                                         NFlatHash::TSimpleExpander>;
+
+template <class Key, class T, auto emptyMarker, class Hash, class KeyEqual, class Probing, class Alloc>
+using TDenseHashMapImpl =
+    NFlatHash::TMap<Key, T, Hash, KeyEqual,
+                    NFlatHash::TDenseContainer<std::pair<const Key, T>,
+                                               NFlatHash::NMap::TStaticValueMarker<emptyMarker, T>,
+                                               Alloc>,
+                    Probing, NFlatHash::TAndSizeFitter, NFlatHash::TSimpleExpander>;
+
+
+template <class T, class Hash, class KeyEqual, class Probing, class Alloc>
+using TFlatHashSetImpl = NFlatHash::TSet<T, Hash, KeyEqual,
+                                         NFlatHash::TFlatContainer<T, Alloc>,
+                                         Probing, NFlatHash::TAndSizeFitter,
+                                         NFlatHash::TSimpleExpander>;
+
+template <class T, auto emptyMarker, class Hash, class KeyEqual, class Probing, class Alloc>
+using TDenseHashSetImpl =
+    NFlatHash::TSet<T, Hash, KeyEqual,
+                    NFlatHash::TDenseContainer<T, NFlatHash::NSet::TStaticValueMarker<emptyMarker>, Alloc>,
+                    Probing, NFlatHash::TAndSizeFitter, NFlatHash::TSimpleExpander>;
+
+}  // namespace NPrivate
+
+namespace NFH {
+
+/* flat_map: Fast and highly customizable hash map.
+ *
+ * Most features would be available soon.
+ * Until that time we strongly insist on using only class aliases listed below.
+ */
+
+/* Simpliest open addressing hash map.
+ * Uses additional array to denote status of every bucket.
+ * Default probing is linear.
+ * Currently available probings:
+ * * TLinearProbing
+ * * TQuadraticProbing
+ * * TDenseProbing
+ */
+template <class Key,
+          class T,
+          class Hash = THash<Key>,
+          class KeyEqual = std::equal_to<>,
+          class Probing = NFlatHash::TLinearProbing,
+          class Alloc = std::allocator<std::pair<const Key, T>>>
+using TFlatHashMap = NPrivate::TFlatHashMapImpl<Key, T, Hash, KeyEqual, Probing, Alloc>;
+
+/* Open addressing table with user specified marker for empty buckets.
+ * Currently available probings:
+ * * TLinearProbing
+ * * TQuadraticProbing
+ * * TDenseProbing
+ */
+template <class Key,
+          class T,
+          auto emptyMarker,
+          class Hash = THash<Key>,
+          class KeyEqual = std::equal_to<>,
+          class Probing = NFlatHash::TDenseProbing,
+          class Alloc = std::allocator<std::pair<const Key, T>>>
+using TDenseHashMapStaticMarker = NPrivate::TDenseHashMapImpl<Key, T, emptyMarker,
+                                                              Hash, KeyEqual, Probing, Alloc>;
+
+
+/* flat_set: Fast and highly customizable hash set.
+ *
+ * Most features would be available soon.
+ * Until that time we strongly insist on using only class aliases listed below.
+ */
+
+/* Simpliest open addressing hash map.
+ * Uses additional array to denote status of every bucket.
+ * Default probing is linear.
+ * Currently available probings:
+ * * TLinearProbing
+ * * TQuadraticProbing
+ * * TDenseProbing
+ */
+template <class T,
+          class Hash = THash<T>,
+          class KeyEqual = std::equal_to<>,
+          class Probing = NFlatHash::TLinearProbing,
+          class Alloc = std::allocator<T>>
+using TFlatHashSet = NPrivate::TFlatHashSetImpl<T, Hash, KeyEqual, Probing, Alloc>;
+
+/* Open addressing table with user specified marker for empty buckets.
+ * Currently available probings:
+ * * TLinearProbing
+ * * TQuadraticProbing
+ * * TDenseProbing
+ */
+template <class T,
+          auto emptyMarker,
+          class Hash = THash<T>,
+          class KeyEqual = std::equal_to<>,
+          class Probing = NFlatHash::TDenseProbing,
+          class Alloc = std::allocator<T>>
+using TDenseHashSetStaticMarker = NPrivate::TDenseHashSetImpl<T, emptyMarker,
+                                                              Hash, KeyEqual, Probing, Alloc>;
+
+}  // namespace NFH
diff --git a/library/cpp/containers/flat_hash/lib/concepts/concepts.cpp b/library/cpp/containers/flat_hash/lib/concepts/concepts.cpp
new file mode 100644
index 0000000000..63eed9acdd
--- /dev/null
+++ b/library/cpp/containers/flat_hash/lib/concepts/concepts.cpp
@@ -0,0 +1,4 @@
+#include "container.h"
+#include "iterator.h"
+#include "size_fitter.h"
+#include "value_marker.h"
diff --git a/library/cpp/containers/flat_hash/lib/concepts/container.h b/library/cpp/containers/flat_hash/lib/concepts/container.h
new file mode 100644
index 0000000000..eac1803b59
--- /dev/null
+++ b/library/cpp/containers/flat_hash/lib/concepts/container.h
@@ -0,0 +1,66 @@
+#pragma once
+
+#include <type_traits>
+
+/* Concepts:
+ * Container
+ * RemovalContainer
+ */
+namespace NFlatHash::NConcepts {
+
+#define DCV(type) std::declval<type>()
+#define DCT(object) decltype(object)
+
+template <class T, class = void>
+struct Container : std::false_type {};
+
+template <class T>
+struct Container<T, std::void_t<
+    typename T::value_type,
+    typename T::size_type,
+    typename T::difference_type,
+    DCT(DCV(T).Node(DCV(typename T::size_type))),
+    DCT(DCV(const T).Node(DCV(typename T::size_type))),
+    DCT(DCV(const T).Size()),
+    DCT(DCV(const T).Taken()),
+    DCT(DCV(const T).Empty()),
+    DCT(DCV(const T).IsEmpty(DCV(typename T::size_type))),
+    DCT(DCV(const T).IsTaken(DCV(typename T::size_type))),
+    DCT(DCV(T).Swap(DCV(T&))),
+    DCT(DCV(const T).Clone(DCV(typename T::size_type)))>>
+    : std::conjunction<std::is_same<DCT(DCV(T).Node(DCV(typename T::size_type))),
+                                    typename T::value_type&>,
+                       std::is_same<DCT(DCV(const T).Node(DCV(typename T::size_type))),
+                                    const typename T::value_type&>,
+                       std::is_same<DCT(DCV(const T).Size()), typename T::size_type>,
+                       std::is_same<DCT(DCV(const T).Taken()), typename T::size_type>,
+                       std::is_same<DCT(DCV(const T).Empty()), typename T::size_type>,
+                       std::is_same<DCT(DCV(const T).IsEmpty(DCV(typename T::size_type))), bool>,
+                       std::is_same<DCT(DCV(const T).IsTaken(DCV(typename T::size_type))), bool>,
+                       std::is_same<DCT(DCV(const T).Clone(DCV(typename T::size_type))), T>,
+                       std::is_copy_constructible<T>,
+                       std::is_move_constructible<T>,
+                       std::is_copy_assignable<T>,
+                       std::is_move_assignable<T>> {};
+
+template <class T>
+constexpr bool ContainerV = Container<T>::value;
+
+template <class T, class = void>
+struct RemovalContainer : std::false_type {};
+
+template <class T>
+struct RemovalContainer<T, std::void_t<
+    DCT(DCV(T).DeleteNode(DCV(typename T::size_type))),
+    DCT(DCV(const T).IsDeleted(DCV(typename T::size_type)))>>
+    : std::conjunction<Container<T>,
+                       std::is_same<DCT(DCV(const T).IsDeleted(DCV(typename T::size_type))),
+                                    bool>> {};
+
+template <class T>
+constexpr bool RemovalContainerV = RemovalContainer<T>::value;
+
+#undef DCV
+#undef DCT
+
+}  // namespace NFlatHash::NConcepts
diff --git a/library/cpp/containers/flat_hash/lib/concepts/iterator.h b/library/cpp/containers/flat_hash/lib/concepts/iterator.h
new file mode 100644
index 0000000000..b9c1c24c82
--- /dev/null
+++ b/library/cpp/containers/flat_hash/lib/concepts/iterator.h
@@ -0,0 +1,20 @@
+#pragma once
+
+#include <iterator>
+
+/* Concepts:
+ * Iterator
+ */
+namespace NFlatHash::NConcepts {
+
+template <class T, class = void>
+struct Iterator : std::false_type {};
+
+template <class T>
+struct Iterator<T, std::void_t<typename std::iterator_traits<T>::iterator_category>>
+    : std::true_type {};
+
+template <class T>
+constexpr bool IteratorV = Iterator<T>::value;
+
+}  // namespace NFlatHash::NConcepts
diff --git a/library/cpp/containers/flat_hash/lib/concepts/size_fitter.h b/library/cpp/containers/flat_hash/lib/concepts/size_fitter.h
new file mode 100644
index 0000000000..83d1d31304
--- /dev/null
+++ b/library/cpp/containers/flat_hash/lib/concepts/size_fitter.h
@@ -0,0 +1,34 @@
+#pragma once
+
+#include <type_traits>
+
+/* Concepts:
+ * SizeFitter
+ */
+namespace NFlatHash::NConcepts {
+
+#define DCV(type) std::declval<type>()
+#define DCT(object) decltype(object)
+
+template <class T, class = void>
+struct SizeFitter : std::false_type {};
+
+template <class T>
+struct SizeFitter<T, std::void_t<
+    DCT(DCV(const T).EvalIndex(DCV(size_t), DCV(size_t))),
+    DCT(DCV(const T).EvalSize(DCV(size_t))),
+    DCT(DCV(T).Update(DCV(size_t)))>>
+    : std::conjunction<std::is_same<DCT(DCV(const T).EvalIndex(DCV(size_t), DCV(size_t))), size_t>,
+                       std::is_same<DCT(DCV(const T).EvalSize(DCV(size_t))), size_t>,
+                       std::is_copy_constructible<T>,
+                       std::is_move_constructible<T>,
+                       std::is_copy_assignable<T>,
+                       std::is_move_assignable<T>> {};
+
+template <class T>
+constexpr bool SizeFitterV = SizeFitter<T>::value;
+
+#undef DCV
+#undef DCT
+
+}  // namespace NFlatHash::NConcepts
diff --git a/library/cpp/containers/flat_hash/lib/concepts/value_marker.h b/library/cpp/containers/flat_hash/lib/concepts/value_marker.h
new file mode 100644
index 0000000000..9d1e9b210a
--- /dev/null
+++ b/library/cpp/containers/flat_hash/lib/concepts/value_marker.h
@@ -0,0 +1,34 @@
+#pragma once
+
+#include <type_traits>
+
+/* Concepts:
+ * ValueMarker
+ */
+namespace NFlatHash::NConcepts {
+
+#define DCV(type) std::declval<type>()
+#define DCT(object) decltype(object)
+
+template <class T, class = void>
+struct ValueMarker : std::false_type {};
+
+template <class T>
+struct ValueMarker<T, std::void_t<
+    typename T::value_type,
+    DCT(DCV(const T).Create()),
+    DCT(DCV(const T).Equals(DCV(const typename T::value_type&)))>>
+    : std::conjunction<std::is_constructible<typename T::value_type, DCT(DCV(const T).Create())>,
+                       std::is_same<DCT(DCV(const T).Equals(DCV(const typename T::value_type&))), bool>,
+                       std::is_copy_constructible<T>,
+                       std::is_move_constructible<T>,
+                       std::is_copy_assignable<T>,
+                       std::is_move_assignable<T>> {};
+
+template <class T>
+constexpr bool ValueMarkerV = ValueMarker<T>::value;
+
+#undef DCV
+#undef DCT
+
+}  // namespace NFlatHash::NConcepts
diff --git a/library/cpp/containers/flat_hash/lib/concepts/ya.make b/library/cpp/containers/flat_hash/lib/concepts/ya.make
new file mode 100644
index 0000000000..f82fc1d51c
--- /dev/null
+++ b/library/cpp/containers/flat_hash/lib/concepts/ya.make
@@ -0,0 +1,9 @@
+LIBRARY()
+
+OWNER(tender-bum)
+
+SRCS(
+    concepts.cpp
+)
+
+END()
diff --git a/library/cpp/containers/flat_hash/lib/containers.cpp b/library/cpp/containers/flat_hash/lib/containers.cpp
new file mode 100644
index 0000000000..0853c23fc1
--- /dev/null
+++ b/library/cpp/containers/flat_hash/lib/containers.cpp
@@ -0,0 +1 @@
+#include "containers.h"
diff --git a/library/cpp/containers/flat_hash/lib/containers.h b/library/cpp/containers/flat_hash/lib/containers.h
new file mode 100644
index 0000000000..82008f2f9c
--- /dev/null
+++ b/library/cpp/containers/flat_hash/lib/containers.h
@@ -0,0 +1,314 @@
+#pragma once
+
+#include "concepts/container.h"
+#include "value_markers.h"
+
+#include <util/system/yassert.h>
+
+#include <util/generic/vector.h>
+#include <util/generic/typetraits.h>
+#include <util/generic/utility.h>
+
+#include <optional>
+
+namespace NFlatHash {
+
+/* FLAT CONTAINER */
+
+template <class T, class Alloc = std::allocator<T>>
+class TFlatContainer {
+public:
+    using value_type = T;
+    using size_type = size_t;
+    using difference_type = ptrdiff_t;
+    using allocator_type = Alloc;
+    using pointer = typename std::allocator_traits<allocator_type>::pointer;
+    using const_pointer = typename std::allocator_traits<allocator_type>::const_pointer;
+
+private:
+    class TCage {
+        enum ENodeStatus {
+            NS_EMPTY,
+            NS_TAKEN,
+            NS_DELETED
+        };
+
+    public:
+        TCage() noexcept = default;
+
+        TCage(const TCage&) = default;
+        TCage(TCage&&) = default;
+
+        TCage& operator=(const TCage& rhs) {
+            switch (rhs.Status_) {
+            case NS_TAKEN:
+                if constexpr (std::is_copy_assignable_v<value_type>) {
+                    Value_ = rhs.Value_;
+                } else {
+                    Value_.emplace(rhs.Value());
+                }
+                break;
+            case NS_EMPTY:
+            case NS_DELETED:
+                if (Value_.has_value()) {
+                    Value_.reset();
+                }
+                break;
+            default:
+                Y_VERIFY(false, "Not implemented");
+            }
+            Status_ = rhs.Status_;
+            return *this;
+        }
+        // We never call it since all the TCage's are stored in vector
+        TCage& operator=(TCage&& rhs) = delete;
+
+        template <class... Args>
+        void Emplace(Args&&... args) {
+            Y_ASSERT(Status_ == NS_EMPTY);
+            Value_.emplace(std::forward<Args>(args)...);
+            Status_ = NS_TAKEN;
+        }
+
+        void Reset() noexcept {
+            Y_ASSERT(Status_ == NS_TAKEN);
+            Value_.reset();
+            Status_ = NS_DELETED;
+        }
+
+        value_type& Value() {
+            Y_ASSERT(Status_ == NS_TAKEN);
+            return *Value_;
+        }
+
+        const value_type& Value() const {
+            Y_ASSERT(Status_ == NS_TAKEN);
+            return *Value_;
+        }
+
+        bool IsEmpty() const noexcept { return Status_ == NS_EMPTY; }
+        bool IsTaken() const noexcept { return Status_ == NS_TAKEN; }
+        bool IsDeleted() const noexcept { return Status_ == NS_DELETED; }
+
+        ENodeStatus Status() const noexcept { return Status_; }
+
+    private:
+        std::optional<value_type> Value_;
+        ENodeStatus Status_ = NS_EMPTY;
+    };
+
+public:
+    explicit TFlatContainer(size_type initSize, const allocator_type& alloc = {})
+        : Buckets_(initSize, alloc)
+        , Taken_(0)
+        , Empty_(initSize) {}
+
+    TFlatContainer(const TFlatContainer&) = default;
+    TFlatContainer(TFlatContainer&& rhs)
+        : Buckets_(std::move(rhs.Buckets_))
+        , Taken_(rhs.Taken_)
+        , Empty_(rhs.Empty_)
+    {
+        rhs.Taken_ = 0;
+        rhs.Empty_ = 0;
+    }
+
+    TFlatContainer& operator=(const TFlatContainer&) = default;
+    TFlatContainer& operator=(TFlatContainer&&) = default;
+
+    value_type& Node(size_type idx) { return Buckets_[idx].Value(); }
+    const value_type& Node(size_type idx) const { return Buckets_[idx].Value(); }
+
+    size_type Size() const noexcept { return Buckets_.size(); }
+    size_type Taken() const noexcept { return Taken_; }
+    size_type Empty() const noexcept { return Empty_; }
+
+    template <class... Args>
+    void InitNode(size_type idx, Args&&... args) {
+        Buckets_[idx].Emplace(std::forward<Args>(args)...);
+        ++Taken_;
+        --Empty_;
+    }
+
+    void DeleteNode(size_type idx) noexcept {
+        Buckets_[idx].Reset();
+        --Taken_;
+    }
+
+    bool IsEmpty(size_type idx) const { return Buckets_[idx].IsEmpty(); }
+    bool IsTaken(size_type idx) const { return Buckets_[idx].IsTaken(); }
+    bool IsDeleted(size_type idx) const { return Buckets_[idx].IsDeleted(); }
+
+    void Swap(TFlatContainer& rhs) noexcept {
+        DoSwap(Buckets_, rhs.Buckets_);
+        DoSwap(Taken_, rhs.Taken_);
+        DoSwap(Empty_, rhs.Empty_);
+    }
+
+    TFlatContainer Clone(size_type newSize) const { return TFlatContainer(newSize, Buckets_.get_allocator()); }
+
+private:
+    TVector<TCage, allocator_type> Buckets_;
+    size_type Taken_;
+    size_type Empty_;
+};
+
+static_assert(NConcepts::ContainerV<TFlatContainer<int>>);
+static_assert(NConcepts::RemovalContainerV<TFlatContainer<int>>);
+
+/* DENSE CONTAINER */
+
+template <class T, class EmptyMarker = NSet::TEqValueMarker<T>, class Alloc = std::allocator<T>>
+class TDenseContainer {
+    static_assert(NConcepts::ValueMarkerV<EmptyMarker>);
+
+public:
+    using value_type = T;
+    using size_type = size_t;
+    using difference_type = ptrdiff_t;
+    using allocator_type = Alloc;
+    using pointer = typename std::allocator_traits<allocator_type>::pointer;
+    using const_pointer = typename std::allocator_traits<allocator_type>::const_pointer;
+
+public:
+    TDenseContainer(size_type initSize,  EmptyMarker emptyMarker = {}, const allocator_type& alloc = {})
+        : Buckets_(initSize, emptyMarker.Create(), alloc)
+        , Taken_(0)
+        , EmptyMarker_(std::move(emptyMarker)) {}
+
+    TDenseContainer(const TDenseContainer&) = default;
+    TDenseContainer(TDenseContainer&&) = default;
+
+    TDenseContainer& operator=(const TDenseContainer& rhs) {
+        Taken_ = rhs.Taken_;
+        EmptyMarker_ = rhs.EmptyMarker_;
+        if constexpr (std::is_copy_assignable_v<value_type>) {
+            Buckets_ = rhs.Buckets_;
+        } else {
+            auto tmp = rhs.Buckets_;
+            Buckets_.swap(tmp);
+        }
+        return *this;
+    }
+    TDenseContainer& operator=(TDenseContainer&&) = default;
+
+    value_type& Node(size_type idx) { return Buckets_[idx]; }
+    const value_type& Node(size_type idx) const { return Buckets_[idx]; }
+
+    size_type Size() const noexcept { return Buckets_.size(); }
+    size_type Taken() const noexcept { return Taken_; }
+    size_type Empty() const noexcept { return Size() - Taken(); }
+
+    template <class... Args>
+    void InitNode(size_type idx, Args&&... args) {
+        Node(idx).~value_type();
+        new (&Buckets_[idx]) value_type(std::forward<Args>(args)...);
+        ++Taken_;
+    }
+
+    bool IsEmpty(size_type idx) const { return EmptyMarker_.Equals(Buckets_[idx]); }
+    bool IsTaken(size_type idx) const { return !IsEmpty(idx); }
+
+    void Swap(TDenseContainer& rhs)
+    noexcept(noexcept(DoSwap(std::declval<EmptyMarker&>(), std::declval<EmptyMarker&>())))
+    {
+        DoSwap(Buckets_, rhs.Buckets_);
+        DoSwap(EmptyMarker_, rhs.EmptyMarker_);
+        DoSwap(Taken_, rhs.Taken_);
+    }
+
+    TDenseContainer Clone(size_type newSize) const { return { newSize, EmptyMarker_, GetAllocator() }; }
+
+protected:
+    allocator_type GetAllocator() const {
+        return Buckets_.get_allocator();
+    }
+
+protected:
+    TVector<value_type, allocator_type> Buckets_;
+    size_type Taken_;
+    EmptyMarker EmptyMarker_;
+};
+
+static_assert(NConcepts::ContainerV<TDenseContainer<int>>);
+static_assert(!NConcepts::RemovalContainerV<TDenseContainer<int>>);
+
+template <class T, class DeletedMarker = NSet::TEqValueMarker<T>,
+          class EmptyMarker = NSet::TEqValueMarker<T>, class Alloc = std::allocator<T>>
+class TRemovalDenseContainer : private TDenseContainer<T, EmptyMarker, Alloc> {
+private:
+    static_assert(NConcepts::ValueMarkerV<DeletedMarker>);
+
+    using TBase = TDenseContainer<T, EmptyMarker>;
+
+public:
+    using typename TBase::value_type;
+    using typename TBase::size_type;
+    using typename TBase::difference_type;
+    using typename TBase::allocator_type;
+    using typename TBase::pointer;
+    using typename TBase::const_pointer;
+
+public:
+    TRemovalDenseContainer(
+        size_type initSize,
+        DeletedMarker deletedMarker = {},
+        EmptyMarker emptyMarker = {},
+        const allocator_type& alloc = {})
+        : TBase(initSize, std::move(emptyMarker), alloc)
+        , DeletedMarker_(std::move(deletedMarker))
+        , Empty_(initSize) {}
+
+    TRemovalDenseContainer(const TRemovalDenseContainer&) = default;
+    TRemovalDenseContainer(TRemovalDenseContainer&&) = default;
+
+    TRemovalDenseContainer& operator=(const TRemovalDenseContainer&) = default;
+    TRemovalDenseContainer& operator=(TRemovalDenseContainer&&) = default;
+
+    using TBase::Node;
+    using TBase::Size;
+    using TBase::Taken;
+    using TBase::InitNode;
+    using TBase::IsEmpty;
+
+    size_type Empty() const noexcept { return Empty_; }
+
+    template <class... Args>
+    void InitNode(size_type idx, Args&&... args) {
+        TBase::InitNode(idx, std::forward<Args>(args)...);
+        --Empty_;
+    }
+
+    void DeleteNode(size_type idx) {
+        if constexpr (!std::is_trivially_destructible_v<value_type>) {
+            TBase::Node(idx).~value_type();
+        }
+        new (&TBase::Node(idx)) value_type(DeletedMarker_.Create());
+        --TBase::Taken_;
+    }
+
+    bool IsTaken(size_type idx) const { return !IsDeleted(idx) && TBase::IsTaken(idx); }
+    bool IsDeleted(size_type idx) const { return DeletedMarker_.Equals(Node(idx)); }
+
+    void Swap(TRemovalDenseContainer& rhs)
+    noexcept(noexcept(std::declval<TBase>().Swap(std::declval<TBase&>())) &&
+             noexcept(DoSwap(std::declval<DeletedMarker&>(), std::declval<DeletedMarker&>())))
+    {
+        TBase::Swap(rhs);
+        DoSwap(DeletedMarker_, rhs.DeletedMarker_);
+        DoSwap(Empty_, rhs.Empty_);
+    }
+
+    TRemovalDenseContainer Clone(size_type newSize) const {
+        return { newSize, DeletedMarker_, TBase::EmptyMarker_, TBase::GetAllocator() };
+    }
+
+private:
+    DeletedMarker DeletedMarker_;
+    size_type Empty_;
+};
+
+static_assert(NConcepts::ContainerV<TRemovalDenseContainer<int>>);
+static_assert(NConcepts::RemovalContainerV<TRemovalDenseContainer<int>>);
+
+}  // namespace NFlatHash
diff --git a/library/cpp/containers/flat_hash/lib/expanders.cpp b/library/cpp/containers/flat_hash/lib/expanders.cpp
new file mode 100644
index 0000000000..6bed3c72f3
--- /dev/null
+++ b/library/cpp/containers/flat_hash/lib/expanders.cpp
@@ -0,0 +1 @@
+#include "expanders.h"
diff --git a/library/cpp/containers/flat_hash/lib/expanders.h b/library/cpp/containers/flat_hash/lib/expanders.h
new file mode 100644
index 0000000000..25b10e6bf1
--- /dev/null
+++ b/library/cpp/containers/flat_hash/lib/expanders.h
@@ -0,0 +1,25 @@
+#pragma once
+
+#include <utility>
+
+namespace NFlatHash {
+
+struct TSimpleExpander {
+    static constexpr bool NeedGrow(size_t size, size_t buckets) noexcept {
+        return size >= buckets / 2;
+    }
+
+    static constexpr bool WillNeedGrow(size_t size, size_t buckets) noexcept {
+        return NeedGrow(size + 1, buckets);
+    }
+
+    static constexpr size_t EvalNewSize(size_t buckets) noexcept {
+        return buckets * 2;
+    }
+
+    static constexpr size_t SuitableSize(size_t size) noexcept {
+        return size * 2 + 1;
+    }
+};
+
+}  // namespace NFlatHash
diff --git a/library/cpp/containers/flat_hash/lib/fuzz/dense_map_fuzz/fuzz.cpp b/library/cpp/containers/flat_hash/lib/fuzz/dense_map_fuzz/fuzz.cpp
new file mode 100644
index 0000000000..9b4cb4c983
--- /dev/null
+++ b/library/cpp/containers/flat_hash/lib/fuzz/dense_map_fuzz/fuzz.cpp
@@ -0,0 +1,60 @@
+#include <library/cpp/containers/flat_hash/lib/map.h>
+#include <library/cpp/containers/flat_hash/lib/containers.h>
+#include <library/cpp/containers/flat_hash/lib/probings.h>
+#include <library/cpp/containers/flat_hash/lib/size_fitters.h>
+#include <library/cpp/containers/flat_hash/lib/expanders.h>
+
+#include <library/cpp/containers/flat_hash/lib/fuzz/fuzz_common/fuzz_common.h>
+
+#include <util/generic/hash.h>
+#include <util/generic/xrange.h>
+#include <util/generic/bt_exception.h>
+
+using namespace NFlatHash;
+
+namespace {
+
+template <class Key, class T>
+using TDenseModMap = NFlatHash::TMap<Key,
+                                     T,
+                                     THash<Key>,
+                                     std::equal_to<Key>,
+                                     TRemovalDenseContainer<std::pair<const Key, T>,
+                                                            NMap::TEqValueMarker<Key, T>,
+                                                            NMap::TEqValueMarker<Key, T>>,
+                                     TDenseProbing,
+                                     TAndSizeFitter,
+                                     TSimpleExpander>;
+
+NFuzz::EActionType EvalType(ui8 data) {
+    return static_cast<NFuzz::EActionType>((data >> 5) & 0b111);
+}
+
+ui8 EvalKey(ui8 data) {
+    return data & 0b11111;
+}
+
+ui8 EvalValue() {
+    return RandomNumber<ui8>();
+}
+
+}  // namespace
+
+#include <util/datetime/base.h>
+
+extern "C" int LLVMFuzzerTestOneInput(const ui8* const wireData, const size_t wireSize) {
+    THashMap<ui8, ui8> etalon;
+    // We assume, that markers can't be produced by EvalKey function.
+    TDenseModMap<ui8, ui8> testee(8,
+                                  (1 << 5), // Deleted marker
+                                  (1 << 6)); // Empty marker
+
+    for (auto i : xrange(wireSize)) {
+        auto data = wireData[i];
+
+        NFuzz::MakeAction(etalon, testee, EvalKey(data), EvalValue(), EvalType(data));
+        NFuzz::CheckInvariants(etalon, testee);
+    }
+
+    return 0;
+}
diff --git a/library/cpp/containers/flat_hash/lib/fuzz/dense_map_fuzz/ya.make b/library/cpp/containers/flat_hash/lib/fuzz/dense_map_fuzz/ya.make
new file mode 100644
index 0000000000..3a5d3d6d8c
--- /dev/null
+++ b/library/cpp/containers/flat_hash/lib/fuzz/dense_map_fuzz/ya.make
@@ -0,0 +1,19 @@
+FUZZ()
+
+OWNER(
+    tender-bum
+)
+
+SRCS(
+    fuzz.cpp
+)
+
+PEERDIR(
+    library/cpp/containers/flat_hash/lib/fuzz/fuzz_common
+)
+
+SIZE(LARGE)
+
+TAG(ya:fat)
+
+END()
diff --git a/library/cpp/containers/flat_hash/lib/fuzz/flat_map_fuzz/fuzz.cpp b/library/cpp/containers/flat_hash/lib/fuzz/flat_map_fuzz/fuzz.cpp
new file mode 100644
index 0000000000..7fb73af0e9
--- /dev/null
+++ b/library/cpp/containers/flat_hash/lib/fuzz/flat_map_fuzz/fuzz.cpp
@@ -0,0 +1,53 @@
+#include <library/cpp/containers/flat_hash/lib/map.h>
+#include <library/cpp/containers/flat_hash/lib/containers.h>
+#include <library/cpp/containers/flat_hash/lib/probings.h>
+#include <library/cpp/containers/flat_hash/lib/size_fitters.h>
+#include <library/cpp/containers/flat_hash/lib/expanders.h>
+
+#include <library/cpp/containers/flat_hash/lib/fuzz/fuzz_common/fuzz_common.h>
+
+#include <util/generic/hash.h>
+#include <util/generic/xrange.h>
+#include <util/generic/bt_exception.h>
+
+using namespace NFlatHash;
+
+namespace {
+
+template <class Key, class T>
+using TFlatLinearModMap = NFlatHash::TMap<Key,
+                                          T,
+                                          THash<Key>,
+                                          std::equal_to<Key>,
+                                          TFlatContainer<std::pair<const Key, T>>,
+                                          TLinearProbing,
+                                          TAndSizeFitter,
+                                          TSimpleExpander>;
+
+NFuzz::EActionType EvalType(ui8 data) {
+    return static_cast<NFuzz::EActionType>((data >> 5) & 0b111);
+}
+
+ui8 EvalKey(ui8 data) {
+    return data & 0b11111;
+}
+
+ui8 EvalValue() {
+    return RandomNumber<ui8>();
+}
+
+}  // namespace
+
+extern "C" int LLVMFuzzerTestOneInput(const ui8* const wireData, const size_t wireSize) {
+    THashMap<ui8, ui8> etalon;
+    TFlatLinearModMap<ui8, ui8> testee;
+
+    for (auto i : xrange(wireSize)) {
+        auto data = wireData[i];
+
+        NFuzz::MakeAction(etalon, testee, EvalKey(data), EvalValue(), EvalType(data));
+        NFuzz::CheckInvariants(etalon, testee);
+    }
+
+    return 0;
+}
diff --git a/library/cpp/containers/flat_hash/lib/fuzz/flat_map_fuzz/ya.make b/library/cpp/containers/flat_hash/lib/fuzz/flat_map_fuzz/ya.make
new file mode 100644
index 0000000000..3a5d3d6d8c
--- /dev/null
+++ b/library/cpp/containers/flat_hash/lib/fuzz/flat_map_fuzz/ya.make
@@ -0,0 +1,19 @@
+FUZZ()
+
+OWNER(
+    tender-bum
+)
+
+SRCS(
+    fuzz.cpp
+)
+
+PEERDIR(
+    library/cpp/containers/flat_hash/lib/fuzz/fuzz_common
+)
+
+SIZE(LARGE)
+
+TAG(ya:fat)
+
+END()
diff --git a/library/cpp/containers/flat_hash/lib/fuzz/fuzz_common/fuzz_common.cpp b/library/cpp/containers/flat_hash/lib/fuzz/fuzz_common/fuzz_common.cpp
new file mode 100644
index 0000000000..efc2973d18
--- /dev/null
+++ b/library/cpp/containers/flat_hash/lib/fuzz/fuzz_common/fuzz_common.cpp
@@ -0,0 +1 @@
+#include "fuzz_common.h"
diff --git a/library/cpp/containers/flat_hash/lib/fuzz/fuzz_common/fuzz_common.h b/library/cpp/containers/flat_hash/lib/fuzz/fuzz_common/fuzz_common.h
new file mode 100644
index 0000000000..71a123d9cf
--- /dev/null
+++ b/library/cpp/containers/flat_hash/lib/fuzz/fuzz_common/fuzz_common.h
@@ -0,0 +1,223 @@
+#pragma once
+
+#include <util/generic/bt_exception.h>
+#include <util/generic/vector.h>
+#include <util/generic/xrange.h>
+
+#include <util/random/random.h>
+
+namespace NFlatHash::NFuzz {
+
+#define FUZZ_ASSERT(cond) \
+    Y_ENSURE_EX(cond, TWithBackTrace<yexception>() << Y_STRINGIZE(cond) << " assertion failed ")
+
+#define FUZZ_ASSERT_THROW(cond, exc) \
+    try { \
+        cond; \
+        FUZZ_ASSERT(false); \
+    } catch (const exc&) { \
+    } catch (...) { \
+        FUZZ_ASSERT(false); \
+    }
+
+enum EActionType {
+    AT_INSERT,
+    AT_CLEAR,
+    AT_REHASH,
+    AT_ATOP,
+    AT_AT,
+    AT_ITERATORS,
+    AT_ERASE,
+    AT_FIND
+};
+
+template <class EtalonMap, class TesteeMap, class Key, class Value>
+void MakeAction(EtalonMap& etalon, TesteeMap& testee, Key&& key, Value&& value, EActionType type) {
+    switch (type) {
+    case AT_INSERT: {
+        auto itEt = etalon.insert({ key, value });
+        if (itEt.second) {
+            FUZZ_ASSERT(!testee.contains(key));
+            auto size = testee.size();
+            auto bucket_count = testee.bucket_count();
+
+            auto itTs = testee.insert(std::make_pair(key, value));
+            FUZZ_ASSERT(itTs.second);
+            FUZZ_ASSERT(itTs.first->first == key);
+            FUZZ_ASSERT(itTs.first->second == value);
+            FUZZ_ASSERT(size + 1 == testee.size());
+            FUZZ_ASSERT(bucket_count <= testee.bucket_count());
+        } else {
+            FUZZ_ASSERT(testee.contains(key));
+            auto size = testee.size();
+            auto bucket_count = testee.bucket_count();
+
+            auto itTs = testee.insert(std::make_pair(key, value));
+            FUZZ_ASSERT(!itTs.second);
+            FUZZ_ASSERT(itTs.first->first == key);
+            FUZZ_ASSERT(itTs.first->second == itEt.first->second);
+            FUZZ_ASSERT(size == testee.size());
+            FUZZ_ASSERT(bucket_count == testee.bucket_count());
+        }
+        break;
+    }
+    case AT_CLEAR: {
+        auto bucket_count = testee.bucket_count();
+        testee.clear();
+        for (const auto& v : etalon) {
+            FUZZ_ASSERT(!testee.contains(v.first));
+        }
+        FUZZ_ASSERT(testee.empty());
+        FUZZ_ASSERT(testee.size() == 0);
+        FUZZ_ASSERT(testee.bucket_count() == bucket_count);
+        FUZZ_ASSERT(testee.load_factor() < std::numeric_limits<float>::epsilon());
+
+        etalon.clear();
+        break;
+    }
+    case AT_REHASH: {
+        testee.rehash(key);
+        FUZZ_ASSERT(testee.bucket_count() >= key);
+        break;
+    }
+    case AT_ATOP: {
+        if (etalon.contains(key)) {
+            FUZZ_ASSERT(testee.contains(key));
+            auto size = testee.size();
+            auto bucket_count = testee.bucket_count();
+
+            FUZZ_ASSERT(testee[key] == etalon[key]);
+
+            FUZZ_ASSERT(size == testee.size());
+            FUZZ_ASSERT(bucket_count == testee.bucket_count());
+        } else {
+            FUZZ_ASSERT(!testee.contains(key));
+            auto size = testee.size();
+            auto bucket_count = testee.bucket_count();
+
+            FUZZ_ASSERT(testee[key] == etalon[key]);
+
+            FUZZ_ASSERT(size + 1 == testee.size());
+            FUZZ_ASSERT(bucket_count <= testee.bucket_count());
+        }
+        auto size = testee.size();
+        auto bucket_count = testee.bucket_count();
+
+        etalon[key] = value;
+        testee[key] = value;
+        FUZZ_ASSERT(testee[key] == etalon[key]);
+        FUZZ_ASSERT(testee[key] == value);
+
+        FUZZ_ASSERT(size == testee.size());
+        FUZZ_ASSERT(bucket_count == testee.bucket_count());
+        break;
+    }
+    case AT_AT: {
+        auto size = testee.size();
+        auto bucket_count = testee.bucket_count();
+        if (etalon.contains(key)) {
+            FUZZ_ASSERT(testee.contains(key));
+
+            FUZZ_ASSERT(testee.at(key) == etalon.at(key));
+            testee.at(key) = value;
+            etalon.at(key) = value;
+            FUZZ_ASSERT(testee.at(key) == etalon.at(key));
+        } else {
+            FUZZ_ASSERT(!testee.contains(key));
+            FUZZ_ASSERT_THROW(testee.at(key) = value, std::out_of_range);
+            FUZZ_ASSERT(!testee.contains(key));
+        }
+        FUZZ_ASSERT(size == testee.size());
+        FUZZ_ASSERT(bucket_count == testee.bucket_count());
+        break;
+    }
+    case AT_ITERATORS: {
+        auto itBeginTs = testee.begin();
+        auto itEndTs = testee.end();
+        FUZZ_ASSERT((size_t)std::distance(itBeginTs, itEndTs) == testee.size());
+        FUZZ_ASSERT(std::distance(itBeginTs, itEndTs) ==
+                    std::distance(etalon.begin(), etalon.end()));
+        FUZZ_ASSERT(std::distance(testee.cbegin(), testee.cend()) ==
+                    std::distance(etalon.cbegin(), etalon.cend()));
+        break;
+    }
+    case AT_ERASE: {
+        if (etalon.contains(key)) {
+            FUZZ_ASSERT(testee.contains(key));
+            auto size = testee.size();
+            auto bucket_count = testee.bucket_count();
+
+            auto itTs = testee.find(key);
+            FUZZ_ASSERT(itTs->first == key);
+            FUZZ_ASSERT(itTs->second == etalon.at(key));
+
+            testee.erase(itTs);
+            FUZZ_ASSERT(size - 1 == testee.size());
+            FUZZ_ASSERT(bucket_count == testee.bucket_count());
+            etalon.erase(key);
+        } else {
+            FUZZ_ASSERT(!testee.contains(key));
+        }
+        break;
+    }
+    case AT_FIND: {
+        auto itEt = etalon.find(key);
+        if (itEt != etalon.end()) {
+            FUZZ_ASSERT(testee.contains(key));
+
+            auto itTs = testee.find(key);
+            FUZZ_ASSERT(itTs != testee.end());
+            FUZZ_ASSERT(itTs->first == key);
+            FUZZ_ASSERT(itTs->second == itEt->second);
+
+            itTs->second = value;
+            itEt->second = value;
+        } else {
+            FUZZ_ASSERT(!testee.contains(key));
+
+            auto itTs = testee.find(key);
+            FUZZ_ASSERT(itTs == testee.end());
+        }
+        break;
+    }
+    };
+}
+
+template <class EtalonMap, class TesteeMap>
+void CheckInvariants(const EtalonMap& etalon, const TesteeMap& testee) {
+    using value_type = std::pair<typename TesteeMap::key_type,
+          typename TesteeMap::mapped_type>;
+    using size_type = typename TesteeMap::size_type;
+
+    TVector<value_type> etalonVals{ etalon.begin(), etalon.end() };
+    std::sort(etalonVals.begin(), etalonVals.end());
+    TVector<value_type> testeeVals{ testee.begin(), testee.end() };
+    std::sort(testeeVals.begin(), testeeVals.end());
+
+    FUZZ_ASSERT(testeeVals == etalonVals);
+
+    FUZZ_ASSERT(testee.size() == etalon.size());
+    FUZZ_ASSERT(testee.empty() == etalon.empty());
+    FUZZ_ASSERT(testee.load_factor() < 0.5f + std::numeric_limits<float>::epsilon());
+    FUZZ_ASSERT(testee.bucket_count() > testee.size());
+
+    size_type buckets = 0;
+    for (auto b : xrange(testee.bucket_count())) {
+        buckets += testee.bucket_size(b);
+    }
+    FUZZ_ASSERT(buckets == testee.size());
+
+    for (const auto& v : etalon) {
+        auto key = v.first;
+        auto value = v.second;
+
+        FUZZ_ASSERT(testee.contains(key));
+        FUZZ_ASSERT(testee.count(key) == 1);
+
+        auto it = testee.find(key);
+        FUZZ_ASSERT(it->first == key);
+        FUZZ_ASSERT(it->second == value);
+    }
+}
+
+}  // namespace NFlatHash::NFuzz
diff --git a/library/cpp/containers/flat_hash/lib/fuzz/fuzz_common/ya.make b/library/cpp/containers/flat_hash/lib/fuzz/fuzz_common/ya.make
new file mode 100644
index 0000000000..ecb590e116
--- /dev/null
+++ b/library/cpp/containers/flat_hash/lib/fuzz/fuzz_common/ya.make
@@ -0,0 +1,11 @@
+LIBRARY()
+
+OWNER(tender-bum)
+
+SRCS(fuzz_common.cpp)
+
+PEERDIR(
+    library/cpp/containers/flat_hash/lib
+)
+
+END()
diff --git a/library/cpp/containers/flat_hash/lib/fuzz/ya.make b/library/cpp/containers/flat_hash/lib/fuzz/ya.make
new file mode 100644
index 0000000000..dbf2183be5
--- /dev/null
+++ b/library/cpp/containers/flat_hash/lib/fuzz/ya.make
@@ -0,0 +1,7 @@
+OWNER(tender-bum)
+
+RECURSE(
+    flat_map_fuzz
+    dense_map_fuzz
+    fuzz_common
+)
diff --git a/library/cpp/containers/flat_hash/lib/iterator.cpp b/library/cpp/containers/flat_hash/lib/iterator.cpp
new file mode 100644
index 0000000000..7c5c206cc3
--- /dev/null
+++ b/library/cpp/containers/flat_hash/lib/iterator.cpp
@@ -0,0 +1 @@
+#include "iterator.h"
diff --git a/library/cpp/containers/flat_hash/lib/iterator.h b/library/cpp/containers/flat_hash/lib/iterator.h
new file mode 100644
index 0000000000..f6b1e74355
--- /dev/null
+++ b/library/cpp/containers/flat_hash/lib/iterator.h
@@ -0,0 +1,99 @@
+#pragma once
+
+#include "concepts/container.h"
+
+#include <util/system/yassert.h>
+
+#include <iterator>
+
+namespace NFlatHash {
+
+template <class Container, class T>
+class TIterator {
+private:
+    static_assert(NConcepts::ContainerV<std::decay_t<Container>>);
+
+public:
+    using iterator_category = std::forward_iterator_tag;
+    using value_type = T;
+    using difference_type = ptrdiff_t;
+    using pointer = typename std::add_pointer<T>::type;
+    using reference = typename std::add_lvalue_reference<T>::type;
+
+private:
+    using size_type = typename Container::size_type;
+
+public:
+    TIterator(Container* cont)
+        : Cont_(cont)
+        , Idx_(0)
+    {
+        if (!cont->IsTaken(Idx_)) {
+            Next();
+        }
+    }
+
+    TIterator(Container* cont, size_type idx)
+        : Cont_(cont)
+        , Idx_(idx) {}
+
+    template <class C, class U, class = std::enable_if_t<std::is_convertible<C*, Container*>::value &&
+                                                         std::is_convertible<U, T>::value>>
+    TIterator(const TIterator<C, U>& rhs)
+        : Cont_(rhs.Cont_)
+        , Idx_(rhs.Idx_) {}
+
+    TIterator(const TIterator&) = default;
+
+    TIterator& operator=(const TIterator&) = default;
+
+    TIterator& operator++() {
+        Next();
+        return *this;
+    }
+    TIterator operator++(int) {
+        auto idx = Idx_;
+        Next();
+        return { Cont_, idx };
+    }
+
+    reference operator*() {
+        return Cont_->Node(Idx_);
+    }
+
+    pointer operator->() {
+        return &Cont_->Node(Idx_);
+    }
+
+    const pointer operator->() const {
+        return &Cont_->Node(Idx_);
+    }
+
+    bool operator==(const TIterator& rhs) const noexcept {
+        Y_ASSERT(Cont_ == rhs.Cont_);
+        return Idx_ == rhs.Idx_;
+    }
+
+    bool operator!=(const TIterator& rhs) const noexcept {
+        return !operator==(rhs);
+    }
+
+private:
+    void Next() {
+        // Container provider ensures that it's not empty.
+        do {
+            ++Idx_;
+        } while (Idx_ != Cont_->Size() && !Cont_->IsTaken(Idx_));
+    }
+
+private:
+    template <class C, class U>
+    friend class TIterator;
+
+    Container* Cont_ = nullptr;
+
+protected:
+    size_type Idx_ = 0;
+};
+
+}  // namespace NFlatHash
diff --git a/library/cpp/containers/flat_hash/lib/map.cpp b/library/cpp/containers/flat_hash/lib/map.cpp
new file mode 100644
index 0000000000..b323fbb46d
--- /dev/null
+++ b/library/cpp/containers/flat_hash/lib/map.cpp
@@ -0,0 +1 @@
+#include "map.h"
diff --git a/library/cpp/containers/flat_hash/lib/map.h b/library/cpp/containers/flat_hash/lib/map.h
new file mode 100644
index 0000000000..f77c318a61
--- /dev/null
+++ b/library/cpp/containers/flat_hash/lib/map.h
@@ -0,0 +1,233 @@
+#pragma once
+
+#include "table.h"
+#include "concepts/iterator.h"
+
+#include <util/generic/algorithm.h>
+#include <util/generic/mapfindptr.h>
+
+namespace NFlatHash {
+
+namespace NPrivate {
+
+struct TMapKeyGetter {
+    template <class T>
+    static constexpr auto& Apply(T& t) noexcept { return t.first; };
+
+    template <class T>
+    static constexpr const auto& Apply(const T& t) noexcept { return t.first; };
+};
+
+}  // namespace NPrivate
+
+template <class Key,
+          class T,
+          class Hash,
+          class KeyEqual,
+          class Container,
+          class Probing,
+          class SizeFitter,
+          class Expander>
+class TMap : private TTable<Hash,
+                            KeyEqual,
+                            Container,
+                            NPrivate::TMapKeyGetter,
+                            Probing,
+                            SizeFitter,
+                            Expander>,
+             public TMapOps<TMap<Key,
+                                 T,
+                                 Hash,
+                                 KeyEqual,
+                                 Container,
+                                 Probing,
+                                 SizeFitter,
+                                 Expander>>
+{
+private:
+    using TBase = TTable<Hash,
+                         KeyEqual,
+                         Container,
+                         NPrivate::TMapKeyGetter,
+                         Probing,
+                         SizeFitter,
+                         Expander>;
+
+    static_assert(std::is_same<std::pair<const Key, T>, typename Container::value_type>::value);
+
+public:
+    using key_type = Key;
+    using mapped_type = T;
+    using typename TBase::value_type;
+    using typename TBase::size_type;
+    using typename TBase::difference_type;
+    using typename TBase::hasher;
+    using typename TBase::key_equal;
+    using typename TBase::reference;
+    using typename TBase::const_reference;
+    using typename TBase::iterator;
+    using typename TBase::const_iterator;
+    using typename TBase::allocator_type;
+    using typename TBase::pointer;
+    using typename TBase::const_pointer;
+
+private:
+    static constexpr size_type INIT_SIZE = 8;
+
+public:
+    TMap() : TBase(INIT_SIZE) {}
+
+    template <class... Rest>
+    TMap(size_type initSize, Rest&&... rest) : TBase(initSize, std::forward<Rest>(rest)...) {}
+
+    template <class I, class... Rest>
+    TMap(I first, I last,
+         std::enable_if_t<NConcepts::IteratorV<I>, size_type> initSize = INIT_SIZE,
+         Rest&&... rest)
+        : TBase(initSize, std::forward<Rest>(rest)...)
+    {
+        insert(first, last);
+    }
+
+    template <class... Rest>
+    TMap(std::initializer_list<value_type> il, size_type initSize = INIT_SIZE, Rest&&... rest)
+        : TBase(initSize, std::forward<Rest>(rest)...)
+    {
+        insert(il.begin(), il.end());
+    }
+
+    TMap(std::initializer_list<value_type> il, size_type initSize = INIT_SIZE)
+        : TBase(initSize)
+    {
+        insert(il.begin(), il.end());
+    }
+
+    TMap(const TMap&) = default;
+    TMap(TMap&&) = default;
+
+    TMap& operator=(const TMap&) = default;
+    TMap& operator=(TMap&&) = default;
+
+    // Iterators
+    using TBase::begin;
+    using TBase::cbegin;
+    using TBase::end;
+    using TBase::cend;
+
+    // Capacity
+    using TBase::empty;
+    using TBase::size;
+
+    // Modifiers
+    using TBase::clear;
+    using TBase::insert;
+    using TBase::emplace;
+    using TBase::emplace_hint;
+    using TBase::erase;
+    using TBase::swap;
+
+    template <class V>
+    std::pair<iterator, bool> insert_or_assign(const key_type& k, V&& v) {
+        return InsertOrAssignImpl(k, std::forward<V>(v));
+    }
+    template <class V>
+    std::pair<iterator, bool> insert_or_assign(key_type&& k, V&& v) {
+        return InsertOrAssignImpl(std::move(k), std::forward<V>(v));
+    }
+
+    template <class V>
+    iterator insert_or_assign(const_iterator, const key_type& k, V&& v) { // TODO(tender-bum)
+        return insert_or_assign(k, std::forward<V>(v)).first;
+    }
+    template <class V>
+    iterator insert_or_assign(const_iterator, key_type&& k, V&& v) { // TODO(tender-bum)
+        return insert_or_assign(std::move(k), std::forward<V>(v)).first;
+    }
+
+    template <class... Args>
+    std::pair<iterator, bool> try_emplace(const key_type& key, Args&&... args) {
+        return TryEmplaceImpl(key, std::forward<Args>(args)...);
+    }
+    template <class... Args>
+    std::pair<iterator, bool> try_emplace(key_type&& key, Args&&... args) {
+        return TryEmplaceImpl(std::move(key), std::forward<Args>(args)...);
+    }
+
+    template <class... Args>
+    iterator try_emplace(const_iterator, const key_type& key, Args&&... args) { // TODO(tender-bum)
+        return try_emplace(key, std::forward<Args>(args)...).first;
+    }
+    template <class... Args>
+    iterator try_emplace(const_iterator, key_type&& key, Args&&... args) { // TODO(tender-bum)
+        return try_emplace(std::move(key), std::forward<Args>(args)...).first;
+    }
+
+    // Lookup
+    using TBase::count;
+    using TBase::find;
+    using TBase::contains;
+
+    template <class K>
+    mapped_type& at(const K& key) {
+        auto it = find(key);
+        if (it == end()) {
+            throw std::out_of_range{ "no such key in map" };
+        }
+        return it->second;
+    }
+
+    template <class K>
+    const mapped_type& at(const K& key) const { return const_cast<TMap*>(this)->at(key); }
+
+    template <class K>
+    Y_FORCE_INLINE mapped_type& operator[](K&& key) {
+        return TBase::TryCreate(key, [&](size_type idx) {
+            TBase::Buckets_.InitNode(idx, std::forward<K>(key), mapped_type{});
+        }).first->second;
+    }
+
+    // Bucket interface
+    using TBase::bucket_count;
+    using TBase::bucket_size;
+
+    // Hash policy
+    using TBase::load_factor;
+    using TBase::rehash;
+    using TBase::reserve;
+
+    // Observers
+    using TBase::hash_function;
+    using TBase::key_eq;
+
+    friend bool operator==(const TMap& lhs, const TMap& rhs) {
+        return lhs.size() == rhs.size() && AllOf(lhs, [&rhs](const auto& v) {
+            auto it = rhs.find(v.first);
+            return it != rhs.end() && *it == v;
+        });
+    }
+
+    friend bool operator!=(const TMap& lhs, const TMap& rhs) { return !(lhs == rhs); }
+
+private:
+    template <class K, class... Args>
+    std::pair<iterator, bool> TryEmplaceImpl(K&& key, Args&&... args) {
+        return TBase::TryCreate(key, [&](size_type idx) {
+            TBase::Buckets_.InitNode(
+                idx,
+                std::piecewise_construct,
+                std::forward_as_tuple(std::forward<K>(key)),
+                std::forward_as_tuple(std::forward<Args>(args)...));
+        });
+    }
+
+    template <class K, class V>
+    std::pair<iterator, bool> InsertOrAssignImpl(K&& key, V&& v) {
+        auto p = try_emplace(std::forward<K>(key), std::forward<V>(v));
+        if (!p.second) {
+            p.first->second = std::forward<V>(v);
+        }
+        return p;
+    }
+};
+
+}  // namespace NFlatHash
diff --git a/library/cpp/containers/flat_hash/lib/probings.cpp b/library/cpp/containers/flat_hash/lib/probings.cpp
new file mode 100644
index 0000000000..f10c6af113
--- /dev/null
+++ b/library/cpp/containers/flat_hash/lib/probings.cpp
@@ -0,0 +1 @@
+#include "probings.h"
diff --git a/library/cpp/containers/flat_hash/lib/probings.h b/library/cpp/containers/flat_hash/lib/probings.h
new file mode 100644
index 0000000000..886be59cff
--- /dev/null
+++ b/library/cpp/containers/flat_hash/lib/probings.h
@@ -0,0 +1,45 @@
+#pragma once
+
+#include <type_traits>
+
+namespace NFlatHash {
+
+class TLinearProbing {
+public:
+    template <class SizeFitter, class F>
+    static auto FindBucket(SizeFitter sf, size_t idx, size_t sz, F f) {
+        idx = sf.EvalIndex(idx, sz);
+        while (!f(idx)) {
+            idx = sf.EvalIndex(++idx, sz);
+        }
+        return idx;
+    }
+};
+
+class TQuadraticProbing {
+public:
+    template <class SizeFitter, class F>
+    static auto FindBucket(SizeFitter sf, size_t idx, size_t sz, F f) {
+        idx = sf.EvalIndex(idx, sz);
+        size_t k = 0;
+        while (!f(idx)) {
+            idx = sf.EvalIndex(idx + 2 * ++k - 1, sz);
+        }
+        return idx;
+    }
+};
+
+class TDenseProbing {
+public:
+    template <class SizeFitter, class F>
+    static auto FindBucket(SizeFitter sf, size_t idx, size_t sz, F f) {
+        idx = sf.EvalIndex(idx, sz);
+        size_t k = 0;
+        while (!f(idx)) {
+            idx = sf.EvalIndex(idx + ++k, sz);
+        }
+        return idx;
+    }
+};
+
+}  // NFlatHash
diff --git a/library/cpp/containers/flat_hash/lib/set.cpp b/library/cpp/containers/flat_hash/lib/set.cpp
new file mode 100644
index 0000000000..aa2f9c58e1
--- /dev/null
+++ b/library/cpp/containers/flat_hash/lib/set.cpp
@@ -0,0 +1 @@
+#include "set.h"
diff --git a/library/cpp/containers/flat_hash/lib/set.h b/library/cpp/containers/flat_hash/lib/set.h
new file mode 100644
index 0000000000..5266293c6c
--- /dev/null
+++ b/library/cpp/containers/flat_hash/lib/set.h
@@ -0,0 +1,147 @@
+#pragma once
+
+#include "table.h"
+#include "concepts/iterator.h"
+
+#include <util/generic/algorithm.h>
+
+namespace NFlatHash {
+
+namespace NPrivate {
+
+struct TSimpleKeyGetter {
+    template <class T>
+    static constexpr auto& Apply(T& t) noexcept { return t; };
+
+    template <class T>
+    static constexpr const auto& Apply(const T& t) noexcept { return t; };
+};
+
+}  // namespace NPrivate
+
+template <class Key,
+          class Hash,
+          class KeyEqual,
+          class Container,
+          class Probing,
+          class SizeFitter,
+          class Expander>
+class TSet : private TTable<Hash,
+                            KeyEqual,
+                            Container,
+                            NPrivate::TSimpleKeyGetter,
+                            Probing,
+                            SizeFitter,
+                            Expander,
+                            std::add_const>
+{
+private:
+    using TBase = TTable<Hash,
+                         KeyEqual,
+                         Container,
+                         NPrivate::TSimpleKeyGetter,
+                         Probing,
+                         SizeFitter,
+                         Expander,
+                         std::add_const>;
+
+    static_assert(std::is_same_v<Key, typename Container::value_type>);
+
+public:
+    using key_type = Key;
+    using typename TBase::value_type;
+    using typename TBase::size_type;
+    using typename TBase::difference_type;
+    using typename TBase::hasher;
+    using typename TBase::key_equal;
+    using typename TBase::reference;
+    using typename TBase::const_reference;
+    using typename TBase::iterator;
+    using typename TBase::const_iterator;
+    using typename TBase::allocator_type;
+    using typename TBase::pointer;
+    using typename TBase::const_pointer;
+
+private:
+    static constexpr size_type INIT_SIZE = 8;
+
+public:
+    TSet() : TBase(INIT_SIZE) {}
+
+    template <class... Rest>
+    TSet(size_type initSize, Rest&&... rest) : TBase(initSize, std::forward<Rest>(rest)...) {}
+
+    template <class I, class... Rest>
+    TSet(I first, I last,
+         std::enable_if_t<NConcepts::IteratorV<I>, size_type> initSize = INIT_SIZE,
+         Rest&&... rest)
+        : TBase(initSize, std::forward<Rest>(rest)...)
+    {
+        insert(first, last);
+    }
+
+    template <class... Rest>
+    TSet(std::initializer_list<value_type> il, size_type initSize = INIT_SIZE, Rest&&... rest)
+        : TBase(initSize, std::forward<Rest>(rest)...)
+    {
+        insert(il.begin(), il.end());
+    }
+
+    TSet(std::initializer_list<value_type> il, size_type initSize = INIT_SIZE)
+        : TBase(initSize)
+    {
+        insert(il.begin(), il.end());
+    }
+
+    TSet(const TSet&) = default;
+    TSet(TSet&&) = default;
+
+    TSet& operator=(const TSet&) = default;
+    TSet& operator=(TSet&&) = default;
+
+    // Iterators
+    using TBase::begin;
+    using TBase::cbegin;
+    using TBase::end;
+    using TBase::cend;
+
+    // Capacity
+    using TBase::empty;
+    using TBase::size;
+
+    // Modifiers
+    using TBase::clear;
+    using TBase::insert;
+    using TBase::emplace;
+    using TBase::emplace_hint;
+    using TBase::erase;
+    using TBase::swap;
+
+    // Lookup
+    using TBase::count;
+    using TBase::find;
+    using TBase::contains;
+
+    // Bucket interface
+    using TBase::bucket_count;
+    using TBase::bucket_size;
+
+    // Hash policy
+    using TBase::load_factor;
+    using TBase::rehash;
+    using TBase::reserve;
+
+    // Observers
+    using TBase::hash_function;
+    using TBase::key_eq;
+
+    friend bool operator==(const TSet& lhs, const TSet& rhs) {
+        return lhs.size() == rhs.size() && AllOf(lhs, [&rhs](const auto& v) {
+            return rhs.contains(v);
+        });
+    }
+
+    friend bool operator!=(const TSet& lhs, const TSet& rhs) { return !(lhs == rhs); }
+};
+
+}  // namespace NFlatHash
diff --git a/library/cpp/containers/flat_hash/lib/size_fitters.cpp b/library/cpp/containers/flat_hash/lib/size_fitters.cpp
new file mode 100644
index 0000000000..f1431c27e3
--- /dev/null
+++ b/library/cpp/containers/flat_hash/lib/size_fitters.cpp
@@ -0,0 +1 @@
+#include "size_fitters.h"
diff --git a/library/cpp/containers/flat_hash/lib/size_fitters.h b/library/cpp/containers/flat_hash/lib/size_fitters.h
new file mode 100644
index 0000000000..86bd617342
--- /dev/null
+++ b/library/cpp/containers/flat_hash/lib/size_fitters.h
@@ -0,0 +1,47 @@
+#pragma once
+
+#include "concepts/size_fitter.h"
+
+#include <util/system/yassert.h>
+#include <util/generic/bitops.h>
+
+namespace NFlatHash {
+
+class TAndSizeFitter {
+public:
+    size_t EvalIndex(size_t hs, size_t sz) const noexcept {
+        Y_ASSERT(Mask_ == sz - 1);
+        return (hs & Mask_);
+    }
+
+    size_t EvalSize(size_t sz) const noexcept {
+        return FastClp2(sz);
+    }
+
+    void Update(size_t sz) noexcept {
+        Y_ASSERT((sz & (sz - 1)) == 0);
+        Mask_ = sz - 1;
+    }
+
+private:
+    size_t Mask_ = 0;
+};
+
+static_assert(NConcepts::SizeFitterV<TAndSizeFitter>);
+
+class TModSizeFitter {
+public:
+    constexpr size_t EvalIndex(size_t hs, size_t sz) const noexcept {
+        return hs % sz;
+    }
+
+    constexpr size_t EvalSize(size_t sz) const noexcept {
+        return sz;
+    }
+
+    constexpr void Update(size_t) noexcept {}
+};
+
+static_assert(NConcepts::SizeFitterV<TModSizeFitter>);
+
+}  // NFlatHash
diff --git a/library/cpp/containers/flat_hash/lib/table.cpp b/library/cpp/containers/flat_hash/lib/table.cpp
new file mode 100644
index 0000000000..e89d72ad94
--- /dev/null
+++ b/library/cpp/containers/flat_hash/lib/table.cpp
@@ -0,0 +1 @@
+#include "table.h"
diff --git a/library/cpp/containers/flat_hash/lib/table.h b/library/cpp/containers/flat_hash/lib/table.h
new file mode 100644
index 0000000000..b84a052be7
--- /dev/null
+++ b/library/cpp/containers/flat_hash/lib/table.h
@@ -0,0 +1,314 @@
+#pragma once
+
+#include "iterator.h"
+#include "concepts/container.h"
+#include "concepts/size_fitter.h"
+
+#include <util/generic/utility.h>
+
+#include <functional>
+
+namespace NFlatHash {
+
+namespace NPrivate {
+
+template <class T>
+struct TTypeIdentity { using type = T; };
+
+}  // namespace NPrivate
+
+template <
+    class Hash,
+    class KeyEqual,
+    class Container,
+    class KeyGetter,
+    class Probing,
+    class SizeFitter,
+    class Expander,
+    // Used in the TSet to make iterator behave as const_iterator
+    template <class> class IteratorModifier = NPrivate::TTypeIdentity>
+class TTable {
+private:
+    static_assert(NConcepts::ContainerV<Container>);
+    static_assert(NConcepts::SizeFitterV<SizeFitter>);
+
+    template <class C, class V>
+    class TIteratorImpl : public TIterator<C, V> {
+    private:
+        using TBase = TIterator<C, V>;
+        friend class TTable;
+
+        using TBase::TBase;
+
+    public:
+        TIteratorImpl() : TBase(nullptr, 0) {}
+    };
+
+public:
+    using value_type = typename Container::value_type;
+    using size_type = typename Container::size_type;
+    using difference_type = typename Container::difference_type;
+    using hasher = Hash;
+    using key_equal = KeyEqual;
+
+    using reference = value_type&;
+    using const_reference = const value_type&;
+
+    using iterator = TIteratorImpl<typename IteratorModifier<Container>::type,
+                                   typename IteratorModifier<value_type>::type>;
+    using const_iterator = TIteratorImpl<const Container, const value_type>;
+    using allocator_type = typename Container::allocator_type;
+    using pointer = typename Container::pointer;
+    using const_pointer = typename Container::const_pointer;
+
+private:
+    TTable(Container buckets)
+        : Buckets_(std::move(buckets))
+    {
+        SizeFitter_.Update(bucket_count());
+    }
+
+    static constexpr size_type INIT_SIZE = 8;
+
+public:
+    template <class... Rest>
+    TTable(size_type initSize, Rest&&... rest)
+        : Buckets_(initSize == 0 ? INIT_SIZE : SizeFitter_.EvalSize(initSize),
+                   std::forward<Rest>(rest)...)
+    {
+        SizeFitter_.Update(bucket_count());
+    }
+
+    TTable(const TTable&) = default;
+    TTable(TTable&& rhs)
+        : SizeFitter_(std::move(rhs.SizeFitter_))
+        , Buckets_(std::move(rhs.Buckets_))
+        , Hasher_(std::move(rhs.Hasher_))
+        , KeyEqual_(std::move(rhs.KeyEqual_))
+    {
+        TTable tmp{ Buckets_.Clone(INIT_SIZE) };
+        tmp.swap(rhs);
+    }
+
+    TTable& operator=(const TTable&) = default;
+    TTable& operator=(TTable&& rhs) {
+        TTable tmp(std::move(rhs));
+        swap(tmp);
+        return *this;
+    }
+
+    // Iterators
+    iterator begin() { return &Buckets_; }
+    const_iterator begin() const { return const_cast<TTable*>(this)->begin(); }
+    const_iterator cbegin() const { return begin(); }
+
+    iterator end() { return { &Buckets_, bucket_count() }; }
+    const_iterator end() const { return const_cast<TTable*>(this)->end(); }
+    const_iterator cend() const { return end(); }
+
+    // Capacity
+    bool empty() const noexcept { return size() == 0; }
+    size_type size() const noexcept { return Buckets_.Taken(); }
+
+    // Modifiers
+    void clear() {
+        Container tmp(Buckets_.Clone(bucket_count()));
+        Buckets_.Swap(tmp);
+    }
+
+    std::pair<iterator, bool> insert(const value_type& value) { return InsertImpl(value); }
+    std::pair<iterator, bool> insert(value_type&& value) { return InsertImpl(std::move(value)); }
+
+    template <class T>
+    std::enable_if_t<!std::is_same_v<std::decay_t<T>, value_type>,
+    std::pair<iterator, bool>> insert(T&& value) {
+        return insert(value_type(std::forward<T>(value)));
+    }
+
+    iterator insert(const_iterator, const value_type& value) { // TODO(tender-bum)
+        return insert(value).first;
+    }
+    iterator insert(const_iterator, value_type&& value) { // TODO(tender-bum)
+        return insert(std::move(value)).first;
+    }
+
+    template <class T>
+    iterator insert(const_iterator, T&& value) { // TODO(tender-bum)
+        return insert(value_type(std::forward<T>(value))).first;
+    }
+
+    template <class InputIt>
+    void insert(InputIt first, InputIt last) {
+        while (first != last) {
+            insert(*first++);
+        }
+    }
+
+    void insert(std::initializer_list<value_type> il) {
+        insert(il.begin(), il.end());
+    }
+
+    template <class... Args>
+    std::pair<iterator, bool> emplace(Args&&... args) {
+        return insert(value_type(std::forward<Args>(args)...));
+    }
+
+    template <class... Args>
+    iterator emplace_hint(const_iterator, Args&&... args) { // TODO(tender-bum)
+        return emplace(std::forward<Args>(args)...).first;
+    }
+
+    void erase(const_iterator pos) {
+        static_assert(NConcepts::RemovalContainerV<Container>,
+                      "That kind of table doesn't allow erasing. Use another table instead.");
+        if constexpr (NConcepts::RemovalContainerV<Container>) {
+            Buckets_.DeleteNode(pos.Idx_);
+        }
+    }
+
+    void erase(const_iterator f, const_iterator l) {
+        while (f != l) {
+            auto nxt = f;
+            ++nxt;
+            erase(f);
+            f = nxt;
+        }
+    }
+
+    template <class K>
+    std::enable_if_t<!std::is_convertible_v<K, iterator> && !std::is_convertible_v<K, const_iterator>,
+    size_type> erase(const K& key) {
+        auto it = find(key);
+        if (it != end()) {
+            erase(it);
+            return 1;
+        }
+        return 0;
+    }
+
+    void swap(TTable& rhs)
+    noexcept(noexcept(std::declval<Container>().Swap(std::declval<Container&>())))
+    {
+        DoSwap(SizeFitter_, rhs.SizeFitter_);
+        Buckets_.Swap(rhs.Buckets_);
+        DoSwap(Hasher_, rhs.Hasher_);
+        DoSwap(KeyEqual_, rhs.KeyEqual_);
+    }
+
+    // Lookup
+    template <class K>
+    size_type count(const K& key) const { return contains(key); }
+
+    template <class K>
+    iterator find(const K& key) {
+        size_type hs = hash_function()(key);
+        auto idx = FindProperBucket(hs, key);
+        if (Buckets_.IsTaken(idx)) {
+            return { &Buckets_, idx };
+        }
+        return end();
+    }
+
+    template <class K>
+    const_iterator find(const K& key) const { return const_cast<TTable*>(this)->find(key); }
+
+    template <class K>
+    bool contains(const K& key) const {
+        size_type hs = hash_function()(key);
+        return Buckets_.IsTaken(FindProperBucket(hs, key));
+    }
+
+    // Bucket interface
+    size_type bucket_count() const noexcept { return Buckets_.Size(); }
+    size_type bucket_size(size_type idx) const { return Buckets_.IsTaken(idx); }
+
+    // Hash policy
+    float load_factor() const noexcept {
+        return (float)(bucket_count() - Buckets_.Empty()) / bucket_count();
+    }
+
+    void rehash(size_type sz) {
+        if (sz != 0) {
+            auto newBuckets = SizeFitter_.EvalSize(sz);
+            size_type occupied = bucket_count() - Buckets_.Empty();
+            if (Expander::NeedGrow(occupied, newBuckets)) {
+                newBuckets = Max(newBuckets, SizeFitter_.EvalSize(Expander::SuitableSize(size())));
+            }
+            RehashImpl(newBuckets);
+        } else {
+            RehashImpl(SizeFitter_.EvalSize(Expander::SuitableSize(size())));
+        }
+    }
+
+    void reserve(size_type sz) { rehash(sz); } // TODO(tender-bum)
+
+    // Observers
+    constexpr auto hash_function() const noexcept { return Hasher_; }
+    constexpr auto key_eq() const noexcept { return KeyEqual_; }
+
+public:
+    template <class T>
+    std::pair<iterator, bool> InsertImpl(T&& value) {
+        return TryCreate(KeyGetter::Apply(value), [&](size_type idx) {
+            Buckets_.InitNode(idx, std::forward<T>(value));
+        });
+    }
+
+    template <class T, class F>
+    Y_FORCE_INLINE std::pair<iterator, bool> TryCreate(const T& key, F nodeInit) {
+        size_type hs = hash_function()(key);
+        size_type idx = FindProperBucket(hs, key);
+        if (!Buckets_.IsTaken(idx)) {
+            if (Expander::WillNeedGrow(bucket_count() - Buckets_.Empty(), bucket_count())) {
+                RehashImpl();
+                idx = FindProperBucket(hs, key);
+            }
+            nodeInit(idx);
+            return { iterator{ &Buckets_, idx }, true };
+        }
+        return { iterator{ &Buckets_, idx }, false };
+    }
+
+    template <class K>
+    size_type FindProperBucket(size_type hs, const K& key) const {
+        return Probing::FindBucket(SizeFitter_, hs, bucket_count(), [&](size_type idx) {
+            if constexpr (NConcepts::RemovalContainerV<Container>) {
+                return Buckets_.IsEmpty(idx) ||
+                       Buckets_.IsTaken(idx) && key_eq()(KeyGetter::Apply(Buckets_.Node(idx)), key);
+            } else {
+                return Buckets_.IsEmpty(idx) || key_eq()(KeyGetter::Apply(Buckets_.Node(idx)), key);
+            }
+        });
+    }
+
+    void RehashImpl() {
+        if constexpr (NConcepts::RemovalContainerV<Container>) {
+            size_type occupied = bucket_count() - Buckets_.Empty();
+            if (size() < occupied / 2) {
+                rehash(bucket_count()); // Just clearing all deleted elements
+            } else {
+                RehashImpl(SizeFitter_.EvalSize(Expander::EvalNewSize(bucket_count())));
+            }
+        } else {
+            RehashImpl(SizeFitter_.EvalSize(Expander::EvalNewSize(bucket_count())));
+        }
+    }
+
+    void RehashImpl(size_type newSize) {
+        TTable tmp = Buckets_.Clone(newSize);
+        for (auto& value : *this) {
+            size_type hs = hash_function()(KeyGetter::Apply(value));
+            tmp.Buckets_.InitNode(
+                tmp.FindProperBucket(hs, KeyGetter::Apply(value)), std::move_if_noexcept(value));
+        }
+        swap(tmp);
+    }
+
+public:
+    SizeFitter SizeFitter_;
+    Container Buckets_;
+    hasher Hasher_;
+    key_equal KeyEqual_;
+};
+
+}  // namespace NFlatHash
diff --git a/library/cpp/containers/flat_hash/lib/ut/containers_ut.cpp b/library/cpp/containers/flat_hash/lib/ut/containers_ut.cpp
new file mode 100644
index 0000000000..b17b30fa80
--- /dev/null
+++ b/library/cpp/containers/flat_hash/lib/ut/containers_ut.cpp
@@ -0,0 +1,410 @@
+#include <library/cpp/containers/flat_hash/lib/containers.h>
+
+#include <library/cpp/testing/unittest/registar.h>
+
+#include <util/generic/algorithm.h>
+#include <util/random/random.h>
+#include <util/random/shuffle.h>
+
+using namespace NFlatHash;
+
+namespace {
+    constexpr size_t INIT_SIZE = 128;
+
+    struct TDummy {
+        static size_t Count;
+
+        TDummy() { ++Count; }
+        TDummy(const TDummy&) { ++Count; }
+        ~TDummy() { --Count; }
+    };
+    size_t TDummy::Count = 0;
+
+    struct TAlmostDummy {
+        static size_t Count;
+
+        TAlmostDummy(int j = 0) : Junk(j) { ++Count; }
+        TAlmostDummy(const TAlmostDummy& d) : Junk(d.Junk) { ++Count; }
+        ~TAlmostDummy() { --Count; }
+
+        bool operator==(const TAlmostDummy& r) const { return Junk == r.Junk; };
+        bool operator!=(const TAlmostDummy& r) const { return !operator==(r); };
+
+        int Junk;
+    };
+    size_t TAlmostDummy::Count = 0;
+
+    struct TNotSimple {
+        enum class EType {
+            Value,
+            Empty,
+            Deleted
+        } Type_ = EType::Value;
+
+        TString Junk = "something"; // to prevent triviality propagation
+        int Value = 0;
+
+        static int CtorCalls;
+        static int DtorCalls;
+        static int CopyCtorCalls;
+        static int MoveCtorCalls;
+
+        TNotSimple() {
+            ++CtorCalls;
+        }
+        explicit TNotSimple(int value)
+            : Value(value)
+        {
+            ++CtorCalls;
+        }
+
+        TNotSimple(const TNotSimple& rhs) {
+            ++CopyCtorCalls;
+            Value = rhs.Value;
+            Type_ = rhs.Type_;
+        }
+        TNotSimple(TNotSimple&& rhs) {
+            ++MoveCtorCalls;
+            Value = rhs.Value;
+            Type_ = rhs.Type_;
+        }
+
+        ~TNotSimple() {
+            ++DtorCalls;
+        }
+
+        TNotSimple& operator=(const TNotSimple& rhs) {
+            ++CopyCtorCalls;
+            Value = rhs.Value;
+            Type_ = rhs.Type_;
+            return *this;
+        }
+        TNotSimple& operator=(TNotSimple&& rhs) {
+            ++MoveCtorCalls;
+            Value = rhs.Value;
+            Type_ = rhs.Type_;
+            return *this;
+        }
+
+        static TNotSimple Empty() {
+            TNotSimple ret;
+            ret.Type_ = EType::Empty;
+            return ret;
+        }
+
+        static TNotSimple Deleted() {
+            TNotSimple ret;
+            ret.Type_ = EType::Deleted;
+            return ret;
+        }
+
+        bool operator==(const TNotSimple& rhs) const noexcept {
+            return Value == rhs.Value;
+        }
+
+        static void ResetStats() {
+            CtorCalls = 0;
+            DtorCalls = 0;
+            CopyCtorCalls = 0;
+            MoveCtorCalls = 0;
+        }
+    };
+
+    int TNotSimple::CtorCalls = 0;
+    int TNotSimple::DtorCalls = 0;
+    int TNotSimple::CopyCtorCalls = 0;
+    int TNotSimple::MoveCtorCalls = 0;
+
+    struct TNotSimpleEmptyMarker {
+        using value_type = TNotSimple;
+
+        value_type Create() const {
+            return TNotSimple::Empty();
+        }
+
+        bool Equals(const value_type& rhs) const {
+            return rhs.Type_ == TNotSimple::EType::Empty;
+        }
+    };
+
+    struct TNotSimpleDeletedMarker {
+        using value_type = TNotSimple;
+
+        value_type Create() const {
+            return TNotSimple::Deleted();
+        }
+
+        bool Equals(const value_type& rhs) const {
+            return rhs.Type_ == TNotSimple::EType::Deleted;
+        }
+    };
+
+    template <class Container>
+    void CheckContainersEqual(const Container& a, const Container& b) {
+        UNIT_ASSERT_EQUAL(a.Size(), b.Size());
+        UNIT_ASSERT_EQUAL(a.Taken(), b.Empty());
+        for (typename Container::size_type i = 0; i < a.Size(); ++i) {
+            if (a.IsTaken(i)) {
+                UNIT_ASSERT(b.IsTaken(i));
+                UNIT_ASSERT_EQUAL(a.Node(i), b.Node(i));
+            }
+        }
+    }
+
+    template <class Container, class... Args>
+    void SmokingTest(typename Container::size_type size, Args&&... args) {
+        using size_type = typename Container::size_type;
+        using value_type = typename Container::value_type;
+
+        Container cont(size, std::forward<Args>(args)...);
+        UNIT_ASSERT_EQUAL(cont.Size(), size);
+        UNIT_ASSERT_EQUAL(cont.Taken(), 0);
+
+        for (size_type i = 0; i < cont.Size(); ++i) {
+            UNIT_ASSERT(cont.IsEmpty(i));
+            UNIT_ASSERT(!cont.IsTaken(i));
+        }
+
+        // Filling the container till half
+        TVector<size_type> toInsert(cont.Size());
+        Iota(toInsert.begin(), toInsert.end(), 0);
+        Shuffle(toInsert.begin(), toInsert.end());
+        toInsert.resize(toInsert.size() / 2);
+        for (auto i : toInsert) {
+            UNIT_ASSERT(cont.IsEmpty(i));
+            UNIT_ASSERT(!cont.IsTaken(i));
+            value_type value(RandomNumber<size_type>(cont.Size()));
+            cont.InitNode(i, value);
+            UNIT_ASSERT(!cont.IsEmpty(i));
+            UNIT_ASSERT(cont.IsTaken(i));
+            UNIT_ASSERT_EQUAL(cont.Node(i), value);
+        }
+        UNIT_ASSERT_EQUAL(cont.Taken(), toInsert.size());
+
+        // Copy construction test
+        auto cont2 = cont;
+        CheckContainersEqual(cont, cont2);
+
+        // Copy assignment test
+        cont2 = cont2.Clone(0);
+        UNIT_ASSERT_EQUAL(cont2.Size(), 0);
+        UNIT_ASSERT_EQUAL(cont2.Taken(), 0);
+
+        // Copy assignment test
+        cont2 = cont;
+        CheckContainersEqual(cont, cont2);
+
+        // Move construction test
+        auto cont3 = std::move(cont2);
+        UNIT_ASSERT_EQUAL(cont2.Size(), 0);
+        CheckContainersEqual(cont, cont3);
+
+        // Move assignment test
+        cont2 = std::move(cont3);
+        UNIT_ASSERT_EQUAL(cont3.Size(), 0);
+        CheckContainersEqual(cont, cont2);
+    }
+}
+
+Y_UNIT_TEST_SUITE(TFlatContainerTest) {
+    Y_UNIT_TEST(SmokingTest) {
+        SmokingTest<TFlatContainer<int>>(INIT_SIZE);
+    }
+
+    Y_UNIT_TEST(SmokingTestNotSimpleType) {
+        TNotSimple::ResetStats();
+        SmokingTest<TFlatContainer<TNotSimple>>(INIT_SIZE);
+
+        UNIT_ASSERT_EQUAL(TNotSimple::CtorCalls + TNotSimple::CopyCtorCalls + TNotSimple::MoveCtorCalls,
+                          TNotSimple::DtorCalls);
+        UNIT_ASSERT_EQUAL(TNotSimple::CtorCalls, INIT_SIZE / 2 /* created while filling */);
+        UNIT_ASSERT_EQUAL(TNotSimple::DtorCalls, INIT_SIZE / 2 /* removed filling temporary */
+                                                 + INIT_SIZE / 2 /* removed while cloning */
+                                                 + INIT_SIZE /* 3 containers dtors */);
+        UNIT_ASSERT_EQUAL(TNotSimple::CopyCtorCalls, INIT_SIZE / 2 /* 3 created while filling */
+                                                     + INIT_SIZE / 2 /* created while copy constructing */
+                                                     + INIT_SIZE / 2/* created while copy assigning */);
+        UNIT_ASSERT_EQUAL(TNotSimple::MoveCtorCalls, 0);
+    }
+
+    Y_UNIT_TEST(DummyHalfSizeTest) {
+        using TContainer = TFlatContainer<TDummy>;
+        using size_type = typename TContainer::size_type;
+
+        {
+            TContainer cont(INIT_SIZE);
+            UNIT_ASSERT_EQUAL(TDummy::Count, 0);
+
+            TVector<size_type> toInsert(cont.Size());
+            Iota(toInsert.begin(), toInsert.end(), 0);
+            Shuffle(toInsert.begin(), toInsert.end());
+            toInsert.resize(toInsert.size() / 2);
+            for (auto i : toInsert) {
+                UNIT_ASSERT(cont.IsEmpty(i));
+                UNIT_ASSERT(!cont.IsTaken(i));
+                cont.InitNode(i);
+                UNIT_ASSERT_EQUAL(TDummy::Count, cont.Taken());
+                UNIT_ASSERT(!cont.IsEmpty(i));
+                UNIT_ASSERT(cont.IsTaken(i));
+            }
+            UNIT_ASSERT_EQUAL(cont.Taken(), cont.Size() / 2);
+            UNIT_ASSERT_EQUAL(TDummy::Count, cont.Taken());
+        }
+        UNIT_ASSERT_EQUAL(TDummy::Count, 0);
+    }
+
+    Y_UNIT_TEST(DeleteTest) {
+        using TContainer = TFlatContainer<TDummy>;
+        using size_type = typename TContainer::size_type;
+
+        TContainer cont(INIT_SIZE);
+        auto idx = RandomNumber<size_type>(INIT_SIZE);
+        UNIT_ASSERT(!cont.IsTaken(idx));
+        UNIT_ASSERT(!cont.IsDeleted(idx));
+        UNIT_ASSERT_EQUAL(TDummy::Count, 0);
+
+        cont.InitNode(idx);
+        UNIT_ASSERT_EQUAL(cont.Taken(), 1);
+        UNIT_ASSERT(cont.IsTaken(idx));
+        UNIT_ASSERT(!cont.IsDeleted(idx));
+        UNIT_ASSERT_EQUAL(TDummy::Count, 1);
+
+        cont.DeleteNode(idx);
+        UNIT_ASSERT(!cont.IsTaken(idx));
+        UNIT_ASSERT(cont.IsDeleted(idx));
+        UNIT_ASSERT_EQUAL(TDummy::Count, 0);
+    }
+}
+
+Y_UNIT_TEST_SUITE(TDenseContainerTest) {
+    Y_UNIT_TEST(SmokingTest) {
+        SmokingTest<TDenseContainer<int, NSet::TStaticValueMarker<-1>>>(INIT_SIZE);
+    }
+
+    Y_UNIT_TEST(NotSimpleTypeSmokingTest) {
+        TNotSimple::ResetStats();
+        SmokingTest<TDenseContainer<TNotSimple, TNotSimpleEmptyMarker>>(INIT_SIZE);
+
+        UNIT_ASSERT_EQUAL(TNotSimple::CtorCalls + TNotSimple::CopyCtorCalls + TNotSimple::MoveCtorCalls,
+                          TNotSimple::DtorCalls);
+        UNIT_ASSERT_EQUAL(TNotSimple::CtorCalls, INIT_SIZE / 2 /* created while filling */
+                                                 + 2 /* created by empty marker */);
+        UNIT_ASSERT_EQUAL(TNotSimple::DtorCalls, 1 /* removed empty marker temporary */
+                                                 + INIT_SIZE /* half removed while resetting in container,
+                                                                half removed inserted temporary */
+                                                 + INIT_SIZE /* removed while cloning */
+                                                 + 1 /* removed empty marker temporary */
+                                                 + INIT_SIZE * 2 /* 3 containers dtors */);
+        UNIT_ASSERT_EQUAL(TNotSimple::CopyCtorCalls, INIT_SIZE /* created while constructing */
+                                                     + INIT_SIZE / 2 /* 3 created while filling */
+                                                     + INIT_SIZE /* created while copy constructing */
+                                                     + INIT_SIZE /* created while copy assigning */);
+        UNIT_ASSERT_EQUAL(TNotSimple::MoveCtorCalls, 0);
+    }
+
+    Y_UNIT_TEST(RemovalContainerSmokingTest) {
+        SmokingTest<TRemovalDenseContainer<int, NSet::TStaticValueMarker<-1>,
+                                           NSet::TStaticValueMarker<-2>>>(INIT_SIZE);
+    }
+
+    Y_UNIT_TEST(NotSimpleTypeRemovalContainerSmokingTest) {
+        TNotSimple::ResetStats();
+        SmokingTest<TRemovalDenseContainer<TNotSimple, TNotSimpleEmptyMarker,
+                                           TNotSimpleDeletedMarker>>(INIT_SIZE);
+
+        UNIT_ASSERT_EQUAL(TNotSimple::CtorCalls + TNotSimple::CopyCtorCalls + TNotSimple::MoveCtorCalls,
+                          TNotSimple::DtorCalls);
+        UNIT_ASSERT_EQUAL(TNotSimple::CtorCalls, INIT_SIZE / 2 /* created while filling */
+                                                 + 2 /* created by empty marker */);
+        UNIT_ASSERT_EQUAL(TNotSimple::DtorCalls, 1 /* removed empty marker temporary */
+                                                 + INIT_SIZE /* half removed while resetting in container,
+                                                                half removed inserted temporary */
+                                                 + INIT_SIZE /* removed while cloning */
+                                                 + 1 /* removed empty marker temporary */
+                                                 + INIT_SIZE * 2 /* 3 containers dtors */);
+        UNIT_ASSERT_EQUAL(TNotSimple::CopyCtorCalls, INIT_SIZE /* created while constructing */
+                                                     + INIT_SIZE / 2 /* 3 created while filling */
+                                                     + INIT_SIZE /* created while copy constructing */
+                                                     + INIT_SIZE /* created while copy assigning */);
+        UNIT_ASSERT_EQUAL(TNotSimple::MoveCtorCalls, 0);
+    }
+
+    Y_UNIT_TEST(DummyHalfSizeTest) {
+        using TContainer = TDenseContainer<TAlmostDummy, NSet::TEqValueMarker<TAlmostDummy>>;
+        using size_type = typename TContainer::size_type;
+
+        {
+            TContainer cont(INIT_SIZE, TAlmostDummy{-1});
+            UNIT_ASSERT_EQUAL(TAlmostDummy::Count, cont.Size() + 1); // 1 for empty marker
+
+            TVector<size_type> toInsert(cont.Size());
+            Iota(toInsert.begin(), toInsert.end(), 0);
+            Shuffle(toInsert.begin(), toInsert.end());
+            toInsert.resize(toInsert.size() / 2);
+            for (auto i : toInsert) {
+                UNIT_ASSERT(cont.IsEmpty(i));
+                UNIT_ASSERT(!cont.IsTaken(i));
+                cont.InitNode(i, (int)RandomNumber<size_type>(cont.Size()));
+                UNIT_ASSERT_EQUAL(TAlmostDummy::Count, cont.Size() + 1);
+                UNIT_ASSERT(!cont.IsEmpty(i));
+                UNIT_ASSERT(cont.IsTaken(i));
+            }
+            UNIT_ASSERT_EQUAL(cont.Taken(), toInsert.size());
+            UNIT_ASSERT_EQUAL(TAlmostDummy::Count, cont.Size() + 1);
+        }
+        UNIT_ASSERT_EQUAL(TAlmostDummy::Count, 0);
+    }
+
+    Y_UNIT_TEST(DeleteTest) {
+        using TContainer = TRemovalDenseContainer<TAlmostDummy, NSet::TEqValueMarker<TAlmostDummy>,
+                                                  NSet::TEqValueMarker<TAlmostDummy>>;
+        using size_type = typename TContainer::size_type;
+
+        TContainer cont(INIT_SIZE, TAlmostDummy{ -2 }, TAlmostDummy{ -1 });
+        auto idx = RandomNumber<size_type>(cont.Size());
+        UNIT_ASSERT(!cont.IsTaken(idx));
+        UNIT_ASSERT(!cont.IsDeleted(idx));
+        UNIT_ASSERT_EQUAL(TAlmostDummy::Count, cont.Size() + 2); // 2 for markers
+
+        cont.InitNode(idx, (int)RandomNumber<size_type>(cont.Size()));
+        UNIT_ASSERT_EQUAL(cont.Taken(), 1);
+        UNIT_ASSERT(cont.IsTaken(idx));
+        UNIT_ASSERT(!cont.IsDeleted(idx));
+        UNIT_ASSERT_EQUAL(TAlmostDummy::Count, cont.Size() + 2);
+
+        cont.DeleteNode(idx);
+        UNIT_ASSERT(!cont.IsTaken(idx));
+        UNIT_ASSERT(cont.IsDeleted(idx));
+        UNIT_ASSERT_EQUAL(TAlmostDummy::Count, cont.Size() + 2);
+    }
+
+    Y_UNIT_TEST(FancyInitsTest) {
+        {
+            using TContainer = TDenseContainer<int>;
+            TContainer cont{ INIT_SIZE, -1 };
+        }
+        {
+            using TContainer = TDenseContainer<int, NSet::TStaticValueMarker<-1>>;
+            TContainer cont{ INIT_SIZE };
+            static_assert(!std::is_constructible_v<TContainer, size_t, int>);
+        }
+        {
+            using TContainer = TDenseContainer<int, NSet::TEqValueMarker<int>>;
+            TContainer cont{ INIT_SIZE, -1 };
+            TContainer cont2{ INIT_SIZE, NSet::TEqValueMarker<int>{ -1 } };
+        }
+        {
+            using TContainer = TRemovalDenseContainer<int>;
+            TContainer cont{ INIT_SIZE, -1, -2 };
+            TContainer cont2{ INIT_SIZE, NSet::TEqValueMarker<int>{ -1 },
+                              NSet::TEqValueMarker<int>{ -2 } };
+        }
+        {
+            using TContainer = TRemovalDenseContainer<int, NSet::TStaticValueMarker<-1>,
+                                                      NSet::TStaticValueMarker<-1>>;
+            TContainer cont{ INIT_SIZE };
+            static_assert(!std::is_constructible_v<TContainer, size_t, int>);
+            static_assert(!std::is_constructible_v<TContainer, size_t, int, int>);
+        }
+    }
+}
diff --git a/library/cpp/containers/flat_hash/lib/ut/iterator_ut.cpp b/library/cpp/containers/flat_hash/lib/ut/iterator_ut.cpp
new file mode 100644
index 0000000000..0b77bf043f
--- /dev/null
+++ b/library/cpp/containers/flat_hash/lib/ut/iterator_ut.cpp
@@ -0,0 +1,85 @@
+#include <library/cpp/containers/flat_hash/lib/iterator.h>
+#include <library/cpp/containers/flat_hash/lib/containers.h>
+
+#include <library/cpp/testing/unittest/registar.h>
+
+#include <util/random/random.h>
+#include <util/generic/algorithm.h>
+
+using namespace NFlatHash;
+
+namespace {
+    constexpr size_t INIT_SIZE = 128;
+
+    template <class Container>
+    void SmokingTest(Container& cont) {
+        using value_type = typename Container::value_type;
+        using iterator = TIterator<Container, value_type>;
+        using size_type = typename Container::size_type;
+
+        iterator f(&cont), l(&cont, cont.Size());
+        UNIT_ASSERT_EQUAL(f, l);
+        UNIT_ASSERT_EQUAL((size_type)std::distance(f, l), cont.Taken());
+
+        TVector<std::pair<size_type, value_type>> toAdd{
+            { 0, (int)RandomNumber<size_type>(INIT_SIZE) },
+            { 1 + RandomNumber<size_type>(INIT_SIZE - 2), (int)RandomNumber<size_type>(INIT_SIZE) },
+            { INIT_SIZE - 1, (int)RandomNumber<size_type>(INIT_SIZE) }
+        };
+
+        for (const auto& p : toAdd) {
+            UNIT_ASSERT(cont.IsEmpty(p.first));
+            cont.InitNode(p.first, p.second);
+        }
+        UNIT_ASSERT_EQUAL(cont.Size(), INIT_SIZE);
+        f = iterator{ &cont };
+        l = iterator{ &cont, INIT_SIZE };
+        UNIT_ASSERT_UNEQUAL(f, l);
+        UNIT_ASSERT_EQUAL((size_type)std::distance(f, l), cont.Taken());
+
+        TVector<value_type> added(f, l);
+        UNIT_ASSERT(::Equal(toAdd.begin(), toAdd.end(), added.begin(), [](const auto& p, auto v) {
+            return p.second == v;
+        }));
+    }
+
+    template <class Container>
+    void ConstTest(Container& cont) {
+        using value_type = typename Container::value_type;
+        using iterator = TIterator<Container, value_type>;
+        using const_iterator = TIterator<const Container, const value_type>;
+
+        iterator it{ &cont, INIT_SIZE / 2 };
+        const_iterator cit1{ it };
+        const_iterator cit2{ &cont, INIT_SIZE / 2 };
+
+        UNIT_ASSERT_EQUAL(cit1, cit2);
+
+        static_assert(std::is_same<decltype(*it), value_type&>::value);
+        static_assert(std::is_same<decltype(*cit1), const value_type&>::value);
+    }
+}
+
+Y_UNIT_TEST_SUITE(TIteratorTest) {
+    Y_UNIT_TEST(SmokingTest) {
+        {
+            TFlatContainer<int> cont(INIT_SIZE);
+            SmokingTest(cont);
+        }
+        {
+            TDenseContainer<int, NSet::TStaticValueMarker<-1>> cont(INIT_SIZE);
+            SmokingTest(cont);
+        }
+    }
+
+    Y_UNIT_TEST(ConstTest) {
+        {
+            TFlatContainer<int> cont(INIT_SIZE);
+            ConstTest(cont);
+        }
+        {
+            TDenseContainer<int, NSet::TStaticValueMarker<-1>> cont(INIT_SIZE);
+            ConstTest(cont);
+        }
+    }
+}
diff --git a/library/cpp/containers/flat_hash/lib/ut/probings_ut.cpp b/library/cpp/containers/flat_hash/lib/ut/probings_ut.cpp
new file mode 100644
index 0000000000..593f8cbb1b
--- /dev/null
+++ b/library/cpp/containers/flat_hash/lib/ut/probings_ut.cpp
@@ -0,0 +1,34 @@
+#include <library/cpp/containers/flat_hash/lib/probings.h>
+
+#include <library/cpp/testing/unittest/registar.h>
+
+using namespace NFlatHash;
+
+namespace {
+    struct TDummySizeFitter {
+        constexpr auto EvalIndex(size_t idx, size_t) const {
+            return idx;
+        }
+    };
+
+    constexpr TDummySizeFitter SIZE_FITTER;
+
+    auto atLeast13 = [](size_t idx) { return idx >= 13; };
+}
+
+Y_UNIT_TEST_SUITE(TProbingsTest) {
+    Y_UNIT_TEST(LinearProbingTest) {
+        using TProbing = TLinearProbing;
+        UNIT_ASSERT_EQUAL(TProbing::FindBucket(SIZE_FITTER, 1, 0, atLeast13), 13);
+    }
+
+    Y_UNIT_TEST(QuadraticProbingTest) {
+        using TProbing = TQuadraticProbing;
+        UNIT_ASSERT_EQUAL(TProbing::FindBucket(SIZE_FITTER, 1, 0, atLeast13), 17);
+    }
+
+    Y_UNIT_TEST(DenseProbingTest) {
+        using TProbing = TDenseProbing;
+        UNIT_ASSERT_EQUAL(TProbing::FindBucket(SIZE_FITTER, 1, 0, atLeast13), 16);
+    }
+}
diff --git a/library/cpp/containers/flat_hash/lib/ut/size_fitters_ut.cpp b/library/cpp/containers/flat_hash/lib/ut/size_fitters_ut.cpp
new file mode 100644
index 0000000000..4167947ece
--- /dev/null
+++ b/library/cpp/containers/flat_hash/lib/ut/size_fitters_ut.cpp
@@ -0,0 +1,51 @@
+#include <library/cpp/containers/flat_hash/lib/size_fitters.h>
+
+#include <library/cpp/testing/unittest/registar.h>
+
+using namespace NFlatHash;
+
+Y_UNIT_TEST_SUITE(TAndSizeFitterTest) {
+    Y_UNIT_TEST(EvalSizeTest) {
+        TAndSizeFitter sf;
+        UNIT_ASSERT_EQUAL(sf.EvalSize(5), 8);
+        UNIT_ASSERT_EQUAL(sf.EvalSize(8), 8);
+        UNIT_ASSERT_EQUAL(sf.EvalSize(13), 16);
+        UNIT_ASSERT_EQUAL(sf.EvalSize(25), 32);
+        for (size_t i = 1; i < 100; ++i) {
+            UNIT_ASSERT_EQUAL(sf.EvalSize(i), FastClp2(i));
+        }
+    }
+
+    Y_UNIT_TEST(EvalIndexTest) {
+        TAndSizeFitter sf;
+        for (size_t j = 1; j < 10; ++j) {
+            sf.Update(1 << j);
+            for (size_t i = 0; i < 100; ++i) {
+                UNIT_ASSERT_EQUAL(sf.EvalIndex(i, 1 << j), i & ((1 << j) - 1));
+            }
+        }
+    }
+}
+
+Y_UNIT_TEST_SUITE(TModSizeFitterTest) {
+    Y_UNIT_TEST(EvalSizeTest) {
+        TModSizeFitter sf;
+        UNIT_ASSERT_EQUAL(sf.EvalSize(5), 5);
+        UNIT_ASSERT_EQUAL(sf.EvalSize(8), 8);
+        UNIT_ASSERT_EQUAL(sf.EvalSize(13), 13);
+        UNIT_ASSERT_EQUAL(sf.EvalSize(25), 25);
+        for (size_t i = 1; i < 100; ++i) {
+            UNIT_ASSERT_EQUAL(sf.EvalSize(i), i);
+        }
+    }
+
+    Y_UNIT_TEST(EvalIndexTest) {
+        TModSizeFitter sf;
+        for (size_t j = 1; j < 10; ++j) {
+            sf.Update(1 << j); // just for integrity
+            for (size_t i = 0; i < 100; ++i) {
+                UNIT_ASSERT_EQUAL(sf.EvalIndex(i, 1 << j), i % (1 << j));
+            }
+        }
+    }
+}
diff --git a/library/cpp/containers/flat_hash/lib/ut/table_ut.cpp b/library/cpp/containers/flat_hash/lib/ut/table_ut.cpp
new file mode 100644
index 0000000000..ea511e2c6a
--- /dev/null
+++ b/library/cpp/containers/flat_hash/lib/ut/table_ut.cpp
@@ -0,0 +1,411 @@
+#include <library/cpp/containers/flat_hash/lib/containers.h>
+#include <library/cpp/containers/flat_hash/lib/expanders.h>
+#include <library/cpp/containers/flat_hash/lib/probings.h>
+#include <library/cpp/containers/flat_hash/lib/size_fitters.h>
+#include <library/cpp/containers/flat_hash/lib/table.h>
+
+#include <library/cpp/testing/unittest/registar.h>
+
+#include <util/generic/algorithm.h>
+#include <util/random/random.h>
+#include <util/random/shuffle.h>
+
+using namespace NFlatHash;
+
+namespace {
+    template <class T>
+    struct TJustType {
+        using type = T;
+    };
+
+    template <class... Ts>
+    struct TTypePack {};
+
+    template <class F, class... Ts>
+    constexpr void ForEachType(F&& f, TTypePack<Ts...>) {
+        ApplyToMany(std::forward<F>(f), TJustType<Ts>{}...);
+    }
+
+/* Usage example:
+ *
+ * TForEachType<int, float, TString>::Apply([](auto t) {
+ *     using T = GET_TYPE(t);
+ * });
+ * So T would be:
+ *  int     on #0 iteration
+ *  float   on #1 iteration
+ *  TString on #2 iteration
+ */
+#define GET_TYPE(ti) typename decltype(ti)::type
+
+    constexpr size_t INIT_SIZE = 32;
+    constexpr size_t BIG_INIT_SIZE = 128;
+
+    template <class T>
+    struct TSimpleKeyGetter {
+        static constexpr T& Apply(T& t) { return t; }
+        static constexpr const T& Apply(const T& t) { return t; }
+    };
+
+    template <class T,
+              class KeyEqual = std::equal_to<T>,
+              class ValueEqual = std::equal_to<T>,
+              class KeyGetter = TSimpleKeyGetter<T>,
+              class F,
+              class... Containers>
+    void ForEachTable(F f, TTypePack<Containers...> cs) {
+        ForEachType([&](auto p) {
+            using TProbing = GET_TYPE(p);
+
+            ForEachType([&](auto sf) {
+                using TSizeFitter = GET_TYPE(sf);
+
+                ForEachType([&](auto t) {
+                    using TContainer = GET_TYPE(t);
+                    static_assert(std::is_same_v<typename TContainer::value_type, T>);
+
+                    using TTable = TTable<THash<T>,
+                                          KeyEqual,
+                                          TContainer,
+                                          KeyGetter,
+                                          TProbing,
+                                          TSizeFitter,
+                                          TSimpleExpander>;
+
+                    f(TJustType<TTable>{});
+                }, cs);
+            }, TTypePack<TAndSizeFitter, TModSizeFitter>{});
+        }, TTypePack<TLinearProbing, TQuadraticProbing, TDenseProbing>{});
+    }
+
+    using TAtomContainers = TTypePack<TFlatContainer<int>,
+                                      TDenseContainer<int, NSet::TStaticValueMarker<-1>>>;
+    using TContainers = TTypePack<TFlatContainer<int>,
+                                  TDenseContainer<int, NSet::TStaticValueMarker<-1>>>;
+    using TRemovalContainers = TTypePack<TFlatContainer<int>,
+                                         TRemovalDenseContainer<int, NSet::TStaticValueMarker<-2>,
+                                                                NSet::TStaticValueMarker<-1>>>;
+}
+
+Y_UNIT_TEST_SUITE(TCommonTableAtomsTest) {
+    Y_UNIT_TEST(InitTest) {
+        ForEachTable<int>([](auto t) {
+            GET_TYPE(t) table{ INIT_SIZE };
+
+            UNIT_ASSERT(table.empty());
+            UNIT_ASSERT_EQUAL(table.size(), 0);
+            UNIT_ASSERT_EQUAL(table.bucket_count(), INIT_SIZE);
+            UNIT_ASSERT_EQUAL(table.bucket_size(RandomNumber<size_t>(INIT_SIZE)), 0);
+        }, TAtomContainers{});
+    }
+
+    Y_UNIT_TEST(IteratorTest) {
+        ForEachTable<int>([](auto t) {
+            GET_TYPE(t) table{ INIT_SIZE };
+
+            auto first = table.begin();
+            auto last = table.end();
+            UNIT_ASSERT_EQUAL(first, last);
+            UNIT_ASSERT_EQUAL(std::distance(first, last), 0);
+
+            auto cFirst = table.cbegin();
+            auto cLast = table.cend();
+            UNIT_ASSERT_EQUAL(cFirst, cLast);
+            UNIT_ASSERT_EQUAL(std::distance(cFirst, cLast), 0);
+        }, TAtomContainers{});
+    }
+
+    Y_UNIT_TEST(ContainsAndCountTest) {
+        ForEachTable<int>([](auto t) {
+            GET_TYPE(t) table{ INIT_SIZE };
+
+            for (int i = 0; i < 100; ++i) {
+                UNIT_ASSERT_EQUAL(table.count(i), 0);
+                UNIT_ASSERT(!table.contains(i));
+            }
+        }, TAtomContainers{});
+    }
+
+    Y_UNIT_TEST(FindTest) {
+        ForEachTable<int>([](auto t) {
+            GET_TYPE(t) table{ INIT_SIZE };
+
+            for (int i = 0; i < 100; ++i) {
+                auto it = table.find(i);
+                UNIT_ASSERT_EQUAL(it, table.end());
+            }
+        }, TAtomContainers{});
+    }
+}
+
+Y_UNIT_TEST_SUITE(TCommonTableTest) {
+    Y_UNIT_TEST(InsertTest) {
+        ForEachTable<int>([](auto t) {
+            GET_TYPE(t) table{ INIT_SIZE };
+
+            UNIT_ASSERT(table.empty());
+            UNIT_ASSERT_EQUAL(table.size(), 0);
+
+            int toInsert = RandomNumber<size_t>(100);
+            UNIT_ASSERT_EQUAL(table.count(toInsert), 0);
+            UNIT_ASSERT(!table.contains(toInsert));
+
+            auto p = table.insert(toInsert);
+            UNIT_ASSERT_EQUAL(p.first, table.begin());
+            UNIT_ASSERT(p.second);
+
+            UNIT_ASSERT(!table.empty());
+            UNIT_ASSERT_EQUAL(table.size(), 1);
+            UNIT_ASSERT_EQUAL(table.count(toInsert), 1);
+            UNIT_ASSERT(table.contains(toInsert));
+
+            auto it = table.find(toInsert);
+            UNIT_ASSERT_UNEQUAL(it, table.end());
+            UNIT_ASSERT_EQUAL(it, table.begin());
+            UNIT_ASSERT_EQUAL(*it, toInsert);
+
+            auto p2 = table.insert(toInsert);
+            UNIT_ASSERT_EQUAL(p.first, p2.first);
+            UNIT_ASSERT(!p2.second);
+
+            UNIT_ASSERT_EQUAL(table.size(), 1);
+            UNIT_ASSERT_EQUAL(table.count(toInsert), 1);
+            UNIT_ASSERT(table.contains(toInsert));
+        }, TContainers{});
+    }
+
+    Y_UNIT_TEST(ClearTest) {
+        ForEachTable<int>([](auto t) {
+            GET_TYPE(t) table{ INIT_SIZE };
+
+            TVector<int> toInsert(INIT_SIZE);
+            Iota(toInsert.begin(), toInsert.end(), 0);
+            ShuffleRange(toInsert);
+            toInsert.resize(INIT_SIZE / 3);
+
+            for (auto i : toInsert) {
+                auto p = table.insert(i);
+                UNIT_ASSERT_EQUAL(*p.first, i);
+                UNIT_ASSERT(p.second);
+            }
+            UNIT_ASSERT_EQUAL(table.size(), toInsert.size());
+            UNIT_ASSERT_EQUAL((size_t)std::distance(table.begin(), table.end()), toInsert.size());
+
+            for (auto i : toInsert) {
+                UNIT_ASSERT(table.contains(i));
+                UNIT_ASSERT_EQUAL(table.count(i), 1);
+            }
+
+            auto bc = table.bucket_count();
+            table.clear();
+            UNIT_ASSERT(table.empty());
+            UNIT_ASSERT_EQUAL(table.bucket_count(), bc);
+
+            for (auto i : toInsert) {
+                UNIT_ASSERT(!table.contains(i));
+                UNIT_ASSERT_EQUAL(table.count(i), 0);
+            }
+
+            table.insert(toInsert.front());
+            UNIT_ASSERT(!table.empty());
+        }, TContainers{});
+    }
+
+    Y_UNIT_TEST(CopyMoveTest) {
+        ForEachTable<int>([](auto t) {
+            GET_TYPE(t) table{ INIT_SIZE };
+
+            TVector<int> toInsert(INIT_SIZE);
+            Iota(toInsert.begin(), toInsert.end(), 0);
+            ShuffleRange(toInsert);
+            toInsert.resize(INIT_SIZE / 3);
+
+            for (auto i : toInsert) {
+                auto p = table.insert(i);
+                UNIT_ASSERT_EQUAL(*p.first, i);
+                UNIT_ASSERT(p.second);
+            }
+            UNIT_ASSERT_EQUAL(table.size(), toInsert.size());
+            UNIT_ASSERT_EQUAL((size_t)std::distance(table.begin(), table.end()), toInsert.size());
+
+            for (auto i : toInsert) {
+                UNIT_ASSERT(table.contains(i));
+                UNIT_ASSERT_EQUAL(table.count(i), 1);
+            }
+
+            // Copy construction test
+            auto table2 = table;
+            UNIT_ASSERT_EQUAL(table2.size(), table.size());
+            UNIT_ASSERT_EQUAL((size_t)std::distance(table2.begin(), table2.end()), table.size());
+            for (auto i : table) {
+                UNIT_ASSERT(table2.contains(i));
+                UNIT_ASSERT_EQUAL(table2.count(i), 1);
+            }
+
+            table2.clear();
+            UNIT_ASSERT(table2.empty());
+
+            // Copy assignment test
+            table2 = table;
+            UNIT_ASSERT_EQUAL(table2.size(), table.size());
+            UNIT_ASSERT_EQUAL((size_t)std::distance(table2.begin(), table2.end()), table.size());
+            for (auto i : table) {
+                UNIT_ASSERT(table2.contains(i));
+                UNIT_ASSERT_EQUAL(table2.count(i), 1);
+            }
+
+            // Move construction test
+            auto table3 = std::move(table2);
+            UNIT_ASSERT(table2.empty());
+            UNIT_ASSERT(table2.bucket_count() > 0);
+
+            UNIT_ASSERT_EQUAL(table3.size(), table.size());
+            UNIT_ASSERT_EQUAL((size_t)std::distance(table3.begin(), table3.end()), table.size());
+            for (auto i : table) {
+                UNIT_ASSERT(table3.contains(i));
+                UNIT_ASSERT_EQUAL(table3.count(i), 1);
+            }
+
+            table2.insert(toInsert.front());
+            UNIT_ASSERT(!table2.empty());
+            UNIT_ASSERT_EQUAL(table2.size(), 1);
+            UNIT_ASSERT_UNEQUAL(table2.bucket_count(), 0);
+
+            // Move assignment test
+            table2 = std::move(table3);
+            UNIT_ASSERT(table3.empty());
+            UNIT_ASSERT(table3.bucket_count() > 0);
+
+            UNIT_ASSERT_EQUAL(table2.size(), table.size());
+            UNIT_ASSERT_EQUAL((size_t)std::distance(table2.begin(), table2.end()), table.size());
+            for (auto i : table) {
+                UNIT_ASSERT(table2.contains(i));
+                UNIT_ASSERT_EQUAL(table2.count(i), 1);
+            }
+
+            table3.insert(toInsert.front());
+            UNIT_ASSERT(!table3.empty());
+            UNIT_ASSERT_EQUAL(table3.size(), 1);
+            UNIT_ASSERT_UNEQUAL(table3.bucket_count(), 0);
+        }, TContainers{});
+    }
+
+    Y_UNIT_TEST(RehashTest) {
+        ForEachTable<int>([](auto t) {
+            GET_TYPE(t) table{ INIT_SIZE };
+
+            TVector<int> toInsert(INIT_SIZE);
+            Iota(toInsert.begin(), toInsert.end(), 0);
+            ShuffleRange(toInsert);
+            toInsert.resize(INIT_SIZE / 3);
+
+            for (auto i : toInsert) {
+                table.insert(i);
+            }
+
+            auto bc = table.bucket_count();
+            table.rehash(bc * 2);
+            UNIT_ASSERT(bc * 2 <= table.bucket_count());
+
+            UNIT_ASSERT_EQUAL(table.size(), toInsert.size());
+            UNIT_ASSERT_EQUAL((size_t)std::distance(table.begin(), table.end()), toInsert.size());
+            for (auto i : toInsert) {
+                UNIT_ASSERT(table.contains(i));
+                UNIT_ASSERT_EQUAL(table.count(i), 1);
+            }
+
+            TVector<int> tmp(table.begin(), table.end());
+            Sort(toInsert.begin(), toInsert.end());
+            Sort(tmp.begin(), tmp.end());
+
+            UNIT_ASSERT_VALUES_EQUAL(tmp, toInsert);
+
+            table.rehash(0);
+            UNIT_ASSERT_EQUAL(table.size(), toInsert.size());
+            UNIT_ASSERT(table.bucket_count() > table.size());
+
+            table.clear();
+            UNIT_ASSERT(table.empty());
+            table.rehash(INIT_SIZE);
+            UNIT_ASSERT(table.bucket_count() >= INIT_SIZE);
+
+            table.rehash(0);
+            UNIT_ASSERT(table.bucket_count() > 0);
+        }, TContainers{});
+    }
+
+    Y_UNIT_TEST(EraseTest) {
+        ForEachTable<int>([](auto t) {
+            GET_TYPE(t) table{ INIT_SIZE };
+
+            int value = RandomNumber<ui32>();
+            table.insert(value);
+            UNIT_ASSERT_EQUAL(table.size(), 1);
+            UNIT_ASSERT_EQUAL(table.count(value), 1);
+
+            auto it = table.find(value);
+            table.erase(it);
+
+            UNIT_ASSERT_EQUAL(table.size(), 0);
+            UNIT_ASSERT_EQUAL(table.count(value), 0);
+
+            table.insert(value);
+            UNIT_ASSERT_EQUAL(table.size(), 1);
+            UNIT_ASSERT_EQUAL(table.count(value), 1);
+
+            table.erase(value);
+
+            UNIT_ASSERT_EQUAL(table.size(), 0);
+            UNIT_ASSERT_EQUAL(table.count(value), 0);
+
+            table.insert(value);
+            UNIT_ASSERT_EQUAL(table.size(), 1);
+            UNIT_ASSERT_EQUAL(table.count(value), 1);
+
+            table.erase(table.find(value), table.end());
+
+            UNIT_ASSERT_EQUAL(table.size(), 0);
+            UNIT_ASSERT_EQUAL(table.count(value), 0);
+
+            table.erase(value);
+
+            UNIT_ASSERT_EQUAL(table.size(), 0);
+            UNIT_ASSERT_EQUAL(table.count(value), 0);
+        }, TRemovalContainers{});
+    }
+
+    Y_UNIT_TEST(EraseBigTest) {
+        ForEachTable<int>([](auto t) {
+            GET_TYPE(t) table{ BIG_INIT_SIZE };
+
+            for (int i = 0; i < 1000; ++i) {
+                for (int j = 0; j < static_cast<int>(BIG_INIT_SIZE); ++j) {
+                    table.emplace(j);
+                }
+                for (int j = 0; j < static_cast<int>(BIG_INIT_SIZE); ++j) {
+                    table.erase(j);
+                }
+            }
+            UNIT_ASSERT(table.bucket_count() <= BIG_INIT_SIZE * 8);
+        }, TRemovalContainers{});
+    }
+
+    Y_UNIT_TEST(ConstructWithSizeTest) {
+        ForEachTable<int>([](auto t) {
+            GET_TYPE(t) table{ 1000 };
+            UNIT_ASSERT(table.bucket_count() >= 1000);
+
+            int value = RandomNumber<ui32>();
+            table.insert(value);
+            UNIT_ASSERT_EQUAL(table.size(), 1);
+            UNIT_ASSERT_EQUAL(table.count(value), 1);
+            UNIT_ASSERT(table.bucket_count() >= 1000);
+
+            table.rehash(10);
+            UNIT_ASSERT_EQUAL(table.size(), 1);
+            UNIT_ASSERT_EQUAL(table.count(value), 1);
+            UNIT_ASSERT(table.bucket_count() < 1000);
+            UNIT_ASSERT(table.bucket_count() >= 10);
+        }, TContainers{});
+    }
+}
diff --git a/library/cpp/containers/flat_hash/lib/ut/ya.make b/library/cpp/containers/flat_hash/lib/ut/ya.make
new file mode 100644
index 0000000000..04d65a8c6e
--- /dev/null
+++ b/library/cpp/containers/flat_hash/lib/ut/ya.make
@@ -0,0 +1,17 @@
+UNITTEST()
+
+OWNER(tender-bum)
+
+SRCS(
+    size_fitters_ut.cpp
+    probings_ut.cpp
+    containers_ut.cpp
+    iterator_ut.cpp
+    table_ut.cpp
+)
+
+PEERDIR(
+    library/cpp/containers/flat_hash/lib
+)
+
+END()
diff --git a/library/cpp/containers/flat_hash/lib/value_markers.cpp b/library/cpp/containers/flat_hash/lib/value_markers.cpp
new file mode 100644
index 0000000000..e69de29bb2
--- /dev/null
+++ b/library/cpp/containers/flat_hash/lib/value_markers.cpp
diff --git a/library/cpp/containers/flat_hash/lib/value_markers.h b/library/cpp/containers/flat_hash/lib/value_markers.h
new file mode 100644
index 0000000000..99351586b5
--- /dev/null
+++ b/library/cpp/containers/flat_hash/lib/value_markers.h
@@ -0,0 +1,130 @@
+#pragma once
+
+#include "concepts/value_marker.h"
+
+#include <type_traits>
+#include <tuple>
+
+namespace NFlatHash {
+
+namespace NSet {
+
+template <auto Value>
+struct TStaticValueMarker {
+    using value_type = decltype(Value);
+
+    constexpr auto Create() const noexcept {
+        return Value;
+    }
+
+    template <class U>
+    bool Equals(const U& rhs) const {
+        return Value == rhs;
+    }
+};
+
+static_assert(NConcepts::ValueMarkerV<TStaticValueMarker<5>>);
+
+template <class T>
+class TEqValueMarker {
+public:
+    using value_type = T;
+
+    template <class V, class = std::enable_if_t<std::is_constructible_v<T, std::decay_t<V>>>>
+    TEqValueMarker(V&& v) : Value_(std::forward<V>(v)) {}
+
+    TEqValueMarker(const TEqValueMarker&) = default;
+    TEqValueMarker(TEqValueMarker&&) = default;
+
+    TEqValueMarker& operator=(const TEqValueMarker&) = default;
+    TEqValueMarker& operator=(TEqValueMarker&&) = default;
+
+    const T& Create() const noexcept {
+        return Value_;
+    }
+
+    template <class U>
+    bool Equals(const U& rhs) const {
+        return Value_ == rhs;
+    }
+
+private:
+    T Value_;
+};
+
+static_assert(NConcepts::ValueMarkerV<TEqValueMarker<int>>);
+
+}  // namespace NSet
+
+namespace NMap {
+
+template <auto Key, class T>
+class TStaticValueMarker {
+    static_assert(std::is_default_constructible_v<T>);
+
+public:
+    using value_type = std::pair<decltype(Key), T>;
+
+    TStaticValueMarker() = default;
+
+    TStaticValueMarker(const TStaticValueMarker&) {}
+    TStaticValueMarker(TStaticValueMarker&&) {}
+
+    TStaticValueMarker& operator=(const TStaticValueMarker&) noexcept { return *this; }
+    TStaticValueMarker& operator=(TStaticValueMarker&&) noexcept { return *this; }
+
+    std::pair<decltype(Key), const T&> Create() const noexcept { return { Key, Value_ }; }
+
+    template <class U>
+    bool Equals(const U& rhs) const {
+        return Key == rhs.first;
+    }
+
+private:
+    T Value_;
+};
+
+static_assert(NConcepts::ValueMarkerV<TStaticValueMarker<5, int>>);
+
+template <class Key, class T>
+class TEqValueMarker {
+    static_assert(std::is_default_constructible_v<T>);
+
+public:
+    using value_type = std::pair<Key, T>;
+
+    template <class V, class = std::enable_if_t<std::is_constructible_v<Key, std::decay_t<V>>>>
+    TEqValueMarker(V&& v) : Key_(std::forward<V>(v)) {}
+
+    TEqValueMarker(const TEqValueMarker& vm)
+        : Key_(vm.Key_) {}
+    TEqValueMarker(TEqValueMarker&& vm) noexcept(std::is_nothrow_move_constructible_v<Key>
+                                                 && std::is_nothrow_constructible_v<T>)
+        : Key_(std::move(vm.Key_)) {}
+
+    TEqValueMarker& operator=(const TEqValueMarker& vm) {
+        Key_ = vm.Key_;
+        return *this;
+    }
+    TEqValueMarker& operator=(TEqValueMarker&& vm) noexcept(std::is_nothrow_move_assignable_v<Key>) {
+        Key_ = std::move(vm.Key_);
+        return *this;
+    }
+
+    auto Create() const noexcept { return std::tie(Key_, Value_); }
+
+    template <class U>
+    bool Equals(const U& rhs) const {
+        return Key_ == rhs.first;
+    }
+
+private:
+    Key Key_;
+    T Value_;
+};
+
+static_assert(NConcepts::ValueMarkerV<TEqValueMarker<int, int>>);
+
+}  // namespace NMap
+
+}  // namespace NFlatHash
diff --git a/library/cpp/containers/flat_hash/lib/ya.make b/library/cpp/containers/flat_hash/lib/ya.make
new file mode 100644
index 0000000000..afaa69110b
--- /dev/null
+++ b/library/cpp/containers/flat_hash/lib/ya.make
@@ -0,0 +1,17 @@
+LIBRARY()
+
+OWNER(tender-bum)
+
+SRCS(
+    containers.cpp
+    expanders.cpp
+    iterator.cpp
+    map.cpp
+    probings.cpp
+    set.cpp
+    size_fitters.cpp
+    table.cpp
+    value_markers.cpp
+)
+
+END()
diff --git a/library/cpp/containers/flat_hash/ut/flat_hash_ut.cpp b/library/cpp/containers/flat_hash/ut/flat_hash_ut.cpp
new file mode 100644
index 0000000000..2b9d6a1dc2
--- /dev/null
+++ b/library/cpp/containers/flat_hash/ut/flat_hash_ut.cpp
@@ -0,0 +1,272 @@
+#include <library/cpp/containers/flat_hash/flat_hash.h>
+
+#include <library/cpp/testing/unittest/registar.h>
+
+using namespace NFH;
+
+namespace {
+
+constexpr size_t TEST_INIT_SIZE = 25;
+constexpr std::initializer_list<int> SET_INPUT_SAMPLE{1, 2, 3, 4, 5};
+const std::initializer_list<std::pair<const int, TString>> MAP_INPUT_SAMPLE{
+    {1, "a"},
+    {2, "b"},
+    {3, "c"},
+    {4, "d"},
+    {5, "e"}
+};
+
+}  // namespace
+
+template <class Map>
+class TMapTest : public TTestBase {
+    void AllocatorTest();
+
+    void SmokingTest() {
+        Map mp;
+        mp.emplace(5, "abc");
+
+        UNIT_ASSERT_EQUAL(mp.size(), 1);
+        UNIT_ASSERT(mp.contains(5));
+
+        auto it = mp.find(5);
+        UNIT_ASSERT_EQUAL(mp.begin(), it);
+        UNIT_ASSERT(!mp.empty());
+    }
+
+    void CopyConstructionTest() {
+        Map st(MAP_INPUT_SAMPLE);
+        auto st2 = st;
+
+        UNIT_ASSERT(!st.empty());
+        UNIT_ASSERT(!st2.empty());
+        UNIT_ASSERT_EQUAL(st, st2);
+    }
+
+    void MoveConstructionTest() {
+        Map st(MAP_INPUT_SAMPLE);
+        auto st2 = std::move(st);
+
+        UNIT_ASSERT(st.empty());
+        UNIT_ASSERT(!st2.empty());
+        UNIT_ASSERT_UNEQUAL(st, st2);
+    }
+
+    void CopyAssignmentTest() {
+        Map st(MAP_INPUT_SAMPLE);
+        Map st2;
+        UNIT_ASSERT_UNEQUAL(st, st2);
+        UNIT_ASSERT(st2.empty());
+
+        st2 = st;
+        UNIT_ASSERT_EQUAL(st, st2);
+        UNIT_ASSERT(!st2.empty());
+    }
+
+    void DoubleCopyAssignmentTest() {
+        Map st(MAP_INPUT_SAMPLE);
+        Map st2;
+        UNIT_ASSERT_UNEQUAL(st, st2);
+        UNIT_ASSERT(st2.empty());
+
+        st2 = st;
+        UNIT_ASSERT_EQUAL(st, st2);
+        UNIT_ASSERT(!st2.empty());
+
+        st2 = st;
+        UNIT_ASSERT_EQUAL(st, st2);
+        UNIT_ASSERT(!st2.empty());
+    }
+
+    void MoveAssignmentTest() {
+        Map st(MAP_INPUT_SAMPLE);
+        Map st2;
+        UNIT_ASSERT_UNEQUAL(st, st2);
+        UNIT_ASSERT(st2.empty());
+
+        st2 = std::move(st);
+        UNIT_ASSERT_UNEQUAL(st, st2);
+        UNIT_ASSERT(!st2.empty());
+        UNIT_ASSERT(st.empty());
+    }
+
+    void InsertOrAssignTest() {
+        Map mp;
+
+        auto p = mp.insert_or_assign(5, "abc");
+        UNIT_ASSERT_EQUAL(p.first, mp.begin());
+        UNIT_ASSERT(p.second);
+        UNIT_ASSERT_EQUAL(p.first->first, 5);
+        UNIT_ASSERT_EQUAL(p.first->second, "abc");
+
+        auto p2 = mp.insert_or_assign(5, "def");
+        UNIT_ASSERT_EQUAL(p.first, p2.first);
+        UNIT_ASSERT(!p2.second);
+        UNIT_ASSERT_EQUAL(p2.first->first, 5);
+        UNIT_ASSERT_EQUAL(p2.first->second, "def");
+    }
+
+    void TryEmplaceTest() {
+        Map mp;
+
+        auto p = mp.try_emplace(5, "abc");
+        UNIT_ASSERT_EQUAL(p.first, mp.begin());
+        UNIT_ASSERT(p.second);
+        UNIT_ASSERT_EQUAL(p.first->first, 5);
+        UNIT_ASSERT_EQUAL(p.first->second, "abc");
+
+        auto p2 = mp.try_emplace(5, "def");
+        UNIT_ASSERT_EQUAL(p.first, p2.first);
+        UNIT_ASSERT(!p2.second);
+        UNIT_ASSERT_EQUAL(p2.first->first, 5);
+        UNIT_ASSERT_EQUAL(p.first->second, "abc");
+    }
+
+    UNIT_TEST_SUITE_DEMANGLE(TMapTest);
+    UNIT_TEST(AllocatorTest);
+    UNIT_TEST(SmokingTest);
+    UNIT_TEST(CopyConstructionTest);
+    UNIT_TEST(MoveConstructionTest);
+    UNIT_TEST(CopyAssignmentTest);
+    UNIT_TEST(DoubleCopyAssignmentTest);
+    UNIT_TEST(MoveAssignmentTest);
+    UNIT_TEST(InsertOrAssignTest);
+    UNIT_TEST(TryEmplaceTest);
+    UNIT_TEST_SUITE_END();
+};
+
+template <>
+void TMapTest<TFlatHashMap<int, TString>>::AllocatorTest() {
+    using Map = TFlatHashMap<int, TString>;
+    Map mp(3, typename Map::allocator_type());
+}
+
+template <>
+void TMapTest<TDenseHashMapStaticMarker<int, TString, -1>>::AllocatorTest() {
+    using Map = TDenseHashMapStaticMarker<int, TString, -1>;
+    Map mp(3, NFlatHash::NMap::TStaticValueMarker<-1, TString>(), typename Map::allocator_type());
+}
+
+using TFlatHashMapTest = TMapTest<TFlatHashMap<int, TString>>;
+using TDenseHashMapTest = TMapTest<TDenseHashMapStaticMarker<int, TString, -1>>;
+
+UNIT_TEST_SUITE_REGISTRATION(TFlatHashMapTest);
+UNIT_TEST_SUITE_REGISTRATION(TDenseHashMapTest);
+
+
+template <class Set>
+class TSetTest : public TTestBase {
+    void AllocatorTest();
+    void DefaultConstructTest() {
+        Set st;
+
+        UNIT_ASSERT(st.empty());
+        UNIT_ASSERT_EQUAL(st.size(), 0);
+        UNIT_ASSERT(st.bucket_count() > 0);
+        UNIT_ASSERT_EQUAL(st.begin(), st.end());
+        UNIT_ASSERT(st.load_factor() < std::numeric_limits<float>::epsilon());
+    }
+
+    void InitCapacityConstructTest() {
+        Set st(TEST_INIT_SIZE);
+
+        UNIT_ASSERT(st.empty());
+        UNIT_ASSERT_EQUAL(st.size(), 0);
+        UNIT_ASSERT(st.bucket_count() >= TEST_INIT_SIZE);
+        UNIT_ASSERT_EQUAL(st.begin(), st.end());
+        UNIT_ASSERT(st.load_factor() < std::numeric_limits<float>::epsilon());
+    }
+
+    void IteratorsConstructTest() {
+        Set st(SET_INPUT_SAMPLE.begin(), SET_INPUT_SAMPLE.end());
+
+        UNIT_ASSERT(!st.empty());
+        UNIT_ASSERT_EQUAL(st.size(), SET_INPUT_SAMPLE.size());
+        UNIT_ASSERT(st.bucket_count() >= st.size());
+        UNIT_ASSERT_UNEQUAL(st.begin(), st.end());
+        UNIT_ASSERT_EQUAL(static_cast<size_t>(std::distance(st.begin(), st.end())), st.size());
+        UNIT_ASSERT(st.load_factor() > 0);
+    }
+
+    void InitializerListConstructTest() {
+        Set st(SET_INPUT_SAMPLE);
+
+        UNIT_ASSERT(!st.empty());
+        UNIT_ASSERT(st.size() > 0);
+        UNIT_ASSERT(st.bucket_count() > 0);
+        UNIT_ASSERT_UNEQUAL(st.begin(), st.end());
+        UNIT_ASSERT_EQUAL(static_cast<size_t>(std::distance(st.begin(), st.end())), st.size());
+        UNIT_ASSERT(st.load_factor() > 0);
+    }
+
+    void CopyConstructionTest() {
+        Set st(SET_INPUT_SAMPLE);
+        auto st2 = st;
+
+        UNIT_ASSERT(!st.empty());
+        UNIT_ASSERT(!st2.empty());
+        UNIT_ASSERT_EQUAL(st, st2);
+    }
+
+    void MoveConstructionTest() {
+        Set st(SET_INPUT_SAMPLE);
+        auto st2 = std::move(st);
+
+        UNIT_ASSERT(st.empty());
+        UNIT_ASSERT(!st2.empty());
+        UNIT_ASSERT_UNEQUAL(st, st2);
+    }
+
+    void CopyAssignmentTest() {
+        Set st(SET_INPUT_SAMPLE);
+        Set st2;
+        UNIT_ASSERT_UNEQUAL(st, st2);
+        UNIT_ASSERT(st2.empty());
+
+        st2 = st;
+        UNIT_ASSERT_EQUAL(st, st2);
+        UNIT_ASSERT(!st2.empty());
+    }
+
+    void MoveAssignmentTest() {
+        Set st(SET_INPUT_SAMPLE);
+        Set st2;
+        UNIT_ASSERT_UNEQUAL(st, st2);
+        UNIT_ASSERT(st2.empty());
+
+        st2 = std::move(st);
+        UNIT_ASSERT_UNEQUAL(st, st2);
+        UNIT_ASSERT(!st2.empty());
+        UNIT_ASSERT(st.empty());
+    }
+
+    UNIT_TEST_SUITE_DEMANGLE(TSetTest);
+    UNIT_TEST(AllocatorTest);
+    UNIT_TEST(DefaultConstructTest);
+    UNIT_TEST(InitCapacityConstructTest);
+    UNIT_TEST(IteratorsConstructTest);
+    UNIT_TEST(InitializerListConstructTest);
+    UNIT_TEST(CopyConstructionTest);
+    UNIT_TEST(MoveConstructionTest);
+    UNIT_TEST(CopyAssignmentTest);
+    UNIT_TEST(MoveAssignmentTest);
+    UNIT_TEST_SUITE_END();
+};
+
+template <>
+void TSetTest<TFlatHashSet<int>>::AllocatorTest() {
+    using Map = TFlatHashSet<int>;
+    Map mp(3, typename Map::allocator_type());
+}
+
+template <>
+void TSetTest<TDenseHashSetStaticMarker<int, -1>>::AllocatorTest() {
+    using Map = TDenseHashSetStaticMarker<int, -1>;
+    Map mp(3, NFlatHash::NSet::TStaticValueMarker<-1>(), typename Map::allocator_type());
+}
+
+using TFlatHashSetTest = TSetTest<TFlatHashSet<int, THash<int>>>;
+using TDenseHashSetTest = TSetTest<TDenseHashSetStaticMarker<int, -1>>;
+
+UNIT_TEST_SUITE_REGISTRATION(TFlatHashSetTest);
+UNIT_TEST_SUITE_REGISTRATION(TDenseHashSetTest);
diff --git a/library/cpp/containers/flat_hash/ut/ya.make b/library/cpp/containers/flat_hash/ut/ya.make
new file mode 100644
index 0000000000..1d33d36120
--- /dev/null
+++ b/library/cpp/containers/flat_hash/ut/ya.make
@@ -0,0 +1,13 @@
+UNITTEST()
+
+OWNER(tender-bum)
+
+SRCS(
+    flat_hash_ut.cpp
+)
+
+PEERDIR(
+    library/cpp/containers/flat_hash
+)
+
+END()
diff --git a/library/cpp/containers/flat_hash/ya.make b/library/cpp/containers/flat_hash/ya.make
new file mode 100644
index 0000000000..612e2c1cde
--- /dev/null
+++ b/library/cpp/containers/flat_hash/ya.make
@@ -0,0 +1,13 @@
+LIBRARY()
+
+OWNER(tender-bum)
+
+PEERDIR(
+    library/cpp/containers/flat_hash/lib
+)
+
+SRCS(
+    flat_hash.cpp
+)
+
+END()