HashMap 是一种利用 Hash Table 做多对 Pair 的存储的一种高效数据结构。
关于 HashMap 的实现方法，主要是使用 Key 的 Hash值 进行一个计算，将计算后的结果插入到数组的某一个位置。
当我们要查找 Key 的位置的时候，需要重新计算传入的 Hash值，由于每次 Hash 运算的结果是一样的，那么就会找到正确的位置。
也就是说最好情况下，查找速度可以达到 O(1)，而当所有的 Key 的 Hash值 相同时，则是最坏的查找情况 O(n)。
基于这个理论，我们可以先创建一个表，这个表需要一个索引，而索引是通过 Hash值 计算得来的，为了优化效率并节省内存，在这里可以通过 Hash值 % Hash表大小 来计算出一个 HashMap的容量下当前的索引项。
Array<LinkedList<Pair<Key, Value>>> Map;第一个 Array 是用来保存索引，只需要开扩为一个 HashMap 的容量即可，这样 Hash值 就会被分配到具有指定容量的数组中。
并将 Key 与 Value 都放到链表里。也就是说，Key 的结果为相同 Hash值 的，会被存储到同一个链表中，若所有的 Pair 都被存储到同一个链表里了。
那么此时查询时间复杂度为 O(n)。
Pair 的存储有几个优势：Hash值 （也指的是索引项） 较多时，可以一直添加下去。为了解决这个缺点问题，聪明的人类想到了一些其他的做法。
红黑树，AVL树等等，这些会使 Map 具备排序功能，并提供最坏 O(logn) 的操作速度。O(logn) 的平均操作速度。理解了基本原理之后，就可以开始着手写一个 HashMap 了
首先最基本的，我们需要实现一个 Pair 类用于存储一对元素。
template <typename KeyType, typename ValueType>
class Pair
{
KeyType Key;
ValueType Value;
public:
Pair(const KeyType& InKey, const ValueType& InValue) : Key(InKey), Value(InValue) {}
Pair(KeyType&& InKey, const ValueType& InValue) : Key(std::move(InKey)), Value(InValue) {}
Pair(const KeyType& InKey, ValueType&& InValue) : Key(InKey), Value(std::move(InValue)) {}
Pair(KeyType&& InKey, ValueType&& InValue) : Key(std::move(InKey)), Value(std::move(InValue)) {}
Pair(const Pair& InPair) = default;
Pair(Pair&& InPair) = default;
~Pair() = default;
KeyType& GetKey() { return Key; }
ValueType& GetValue() { return Value; }
const KeyType& GetKey() const { return Key; }
const ValueType& GetValue() const { return Value; }
void SetKey(const KeyType& InKey) { Key = InKey; }
void SetValue(const ValueType& InValue) { Value = InValue; }
void SetKey(const KeyType& InKey) const { Key = InKey; }
void SetValue(const ValueType& InValue) const { Value = InValue; }
Pair& operator= (const Pair& InPair) = default;
Pair& operator= (Pair&& InPair) = default;
};接下来在 HashMap 中，我们需要先创建一个用于存储的结构。并设定一个当前哈希表的容量，还需要一个 Size 来保存当前结构中存储了多少对 Pair。
template <typename KeyType, typename ValueType>
class HashMap
{
SizeType Capacity = 8;
SizeType Size = 0;
Array<LinkedList<Pair<KeyType, ValueType>>> Map;
};注意：此处的 Array | LinkedList | Pair 均为我自己的实现。
可以使用 std::vector | std::list | std::pair 做出相同的实现效果。
接下来写一些公开函数内容，首先是构造，先将 构造函数 复制构造函数 移动构造函数 复制赋值运算符 移动赋值运算符 析构函数 这 6 个函数创建出来，
并在构造函数中初始化数组大小，再将目前没有实现的函数 delete 掉，以防 bug。
HashMap()
{
Map.Init(LinkedList<Pair<KeyType, ValueType>>(), Capacity);
}
HashMap(const HashMap& NewMap) = delete;
HashMap(HashMap&& NewMap) = delete;
~HashMap() = default;
HashMap& operator= (const HashMap& NewMap) = delete;
HashMap& operator= (HashMap&& NewMap) = delete;接下来是新增函数，若我们想新增一个函数，则需要传入一对数值，也就是 Pair。
inline void Add(const Pair<KeyType, ValueType>& InPair)
{
// 此处首先利用了 std::hash<>{} 去定义了一个 Hash 转换器，并将 Key 传入进去计算哈希值。
// 最后使用 % Capacity 来转换成数组索引。
SizeType Hash = std::hash<KeyType>{}(InPair.GetKey()) % Capacity;
// 在对应索引位置加入 InPair。
// 这里的 ForEach 为我自己库的函数，可以直接用普通的 for 代替。
// 先检查一下链表中是否拥有同样名字的 Key，如果有的话，直接设置 Value 的值为新的值。
// 如果没有的话，我们将 Pair 加入这里。
SizeType Hash = std::hash<KeyType>{}(InPair.GetKey()) % Capacity;
bool bFound = false;
ForEach(Map[Hash], [&bFound, InPair](Pair<KeyType, ValueType>& TempPair)
{
if (TempPair.GetKey() == InPair.GetKey())
{
TempPair.SetValue(InPair.GetValue());
bFound = true;
return false;
}
return true;
});
if (!bFound)
{
Map[Hash].Add(InPair);
// 对 Size 进行一个扩容。
++Size;
}
}显然，我们一开始的容量只有 8，这也意味着当数据量过多的时候，只有 8 个槽位可供放入哈希索引。
所以说我们需要一个 ReHash 函数用来在超过一定容量后，重新分配所有的哈希值。
inline void ReHash()
{
// 我这里将容量直接*2了，依据实际的情况可以自己修改，也可以提前暴露出每次扩容所需要的大小。
// 如果你要存储大量的 Hash 值，则尽可能的提前分配，否则会因为多次扩容导致调用 Rehash 函数
// 增加一些性能开销。
Capacity *= 2;
// 创建一个新的存储结构，并初始化为新的容量大小。
Array<LinkedList<Pair<KeyType, ValueType>>> TempMap;
TempMap.Init(LinkedList<Pair<KeyType, ValueType>>(), Capacity);
// 重新计算所有 Key 的 Hash，并将他们模到一个新的范围内，再添加回临时 Map 中。
for (auto& Chain : TempMap)
{
for (auto& SinglePair : Chain)
{
SizeType Hash = std::hash<KeyType>{}(SinglePair.GetKey()) % Capacity;
TempMap[Hash].Add(SinglePair);
}
}
// 移动新建的 Map 到 之前的 Map 上。
Map = std::move(TempMap);
}现在我们需要决定，在什么时候来调用 ReHash。
例如我们现在的容量为 8，这也同时意味着，如果取模后的结果有多个同时分配在了一个链表中。
那么性能就会变差，我们不需要根据一个链表的长度去决定这件事情，可以使用总体的大小来判定是否需要 ReHash。
例如容量为 8 时，我们添加了 64 个元素进来，那么最乐观的情况下，每个数组插槽的链表中会拥有 8 个元素。
此时若查询链表最后一个数值的时候，会调用 8 次的 for。
如果这个时候将容量改为 16。 ReHash 后最乐观的情况下（实际中都是悲观情况），每个链表里只会存入 4 个。
所以这里在 Add 函数中做一个判定，如果这个 HashMap 的总 Pair 量超过了一定比例（暂定为 0.75，可根据需要动态调整）
则需要进行 ReHash。
// Add 函数开头。
// 当 当前容量 /
if (static_cast<float>(Size) / static_cast<float>(Capacity) >= 0.75f)
{
ReHash();
}接下来写 Remove 函数，要求传入一个 Key。
之后首先计算 Key 的哈希值索引，在对应的索引中遍历整个链表，当链表中存储的 Key 等于传入的 Key 时，从链表中删除这个索引。
并让 Size 减去 1。
inline void Remove(const KeyType& Key)
{
SizeType Hash = std::hash<KeyType>{}(Key) % Capacity;
for (SizeType i = 0; i < Map[Hash].Num(); ++i)
{
if (Map[Hash][i]->GetValue().GetKey() == Key)
{
Map[Hash].Remove(i);
--Size;
break;
}
}
}为了可以快速对 Map 进行迭代，我们需要实现一个迭代器。而元素在 Map 中的分配不是连续的，所以我们需要动态的去查找元素。
首先在 HashMap 类中定义一个迭代器，并实现基本的 解引用运算符 等于运算符 不等于运算符 构造函数等。
并定义几个变量。
class Iterator
{
// 用来存储 Map 本身的指针。
HashMap* IteratorHashMap = nullptr;
// 当前检索到的桶。
SizeType BucketIndex = 0;
// 当前检索到的 Pair 的指针。
LinkedListNode<Pair<InternalKey, InternalValue>>* CurrentNode = nullptr;
public:
// 需要在外部传入 HashMap 的指针。
explicit Iterator(HashMap* Map) : IteratorHashMap(Map) {}
// 得到当前 HashMap 指针的函数。
HashMap* GetHashMap() const
{
return IteratorHashMap;
}
// 得到当前链表节点的函数。
LinkedListNode<Pair<InternalKey, InternalValue>>* GetCurrentNode() const
{
return CurrentNode;
}
Iterator& operator++ () = delete;
bool operator== (const Iterator& Other) = delete;
bool operator!= (const Iterator& Other) = delete;
// 实现一下解引用运算符，从当前链表的指针中获取值。
[[nodiscard]] Pair<KeyType, ValueType>& operator*() const
{
return CurrentNode->GetValue();
}
};接下来我们需要一个函数，帮助我们移动到下一个空桶。
void MoveToNextBucket()
{
// 若当前持有的 HashMap 指针存在的话。
if (IteratorHashMap)
{
// 如果当前桶的索引小于桶的容量，则持续查找，如果找到某一个桶的链表不为空，将当前桶的链表的节点赋值给 CurrentNode，并切换到下一个桶，如果当前桶不为空，则直接切换到下一个桶，并重新迭代。
while (BucketIndex < IteratorHashMap->GetCapacity())
{
if (IteratorHashMap->GetMap()[BucketIndex].GetHeadNode())
{
CurrentNode = IteratorHashMap->GetMap()[BucketIndex].GetHeadNode();
++BucketIndex;
break;
}
++BucketIndex;
}
}
}
// 构造函数中一开始需要调用一下。
explicit Iterator(HashMap* Map) : IteratorHashMap(Map)
{
MoveToNextBucket();
}接下来来实现 ++ 运算符，切换到下一个节点的指针。
Iterator& operator++ ()
{
if (!IteratorHashMap)
{
return *this;
}
if (CurrentNode)
{
CurrentNode = CurrentNode->GetNextNode();
}
if (!CurrentNode)
{
MoveToNextBucket();
if (!CurrentNode)
{
IteratorHashMap = nullptr;
}
}
return *this;
}
接下来实现一波等于运算符和不等于运算符，非常简单，只需要检查一下 HashMap 和 CurrentNode 是否跟另外一个 Iterator 相等。
bool operator== (const Iterator& Other) const
{
return (IteratorHashMap == Other.GetHashMap() && CurrentNode == Other.GetCurrentNode());
}
bool operator!= (const Iterator& Other) const
{
return (IteratorHashMap != Other.GetHashMap() && CurrentNode != Other.GetCurrentNode());
}HashMap<int32, String> Map;
Map.Add(Pair(1, String("This is one.")));
Map.Add(Pair(2, String("This is two.")));
Map.Add(Pair(3, String("This is three.")));
Map.Add(Pair(4, String("This is four")));
for (auto i = Map.begin(); i != Map.end(); ++i)
{
std::cout << (*i).GetValue() << "\n";
}
Map.Remove(2);
std::cout << "\n";
for (auto i : Map)
{
std::cout << i.GetValue() << "\n";
}输出：（因为 HashMap 没有顺序，所以是正常现象）
This is four
This is one.
This is three.
This is two.
This is four
This is one.
This is three.为了给用户提供一些方便且可操作的空间，需要重载多个双参数类型的 Add 函数，分别传入 Key 与 Value。
并且为了保证性能，还需要重载右值引用的参数。
先重载一个 Pair 右值引用。
// 参数改为右值引用
void Add(Pair<KeyType, ValueType>&& InPair)
{
if (static_cast<float>(Size) / static_cast<float>(Capacity) >= 0.75f)
{
ReHash();
}
SizeType Hash = std::hash<KeyType>{}(InPair.GetKey()) % Capacity;
bool bFound = false;
ForEach(Map[Hash], [&bFound, InPair](Pair<KeyType, ValueType>& TempPair)
{
if (TempPair.GetKey() == InPair.GetKey())
{
TempPair.SetValue(InPair.GetValue());
bFound = true;
return false;
}
return true;
});
if (!bFound)
{
// 在此处调用 move 从而移动 Pair 到这里。
Map[Hash].Add(std::move(InPair));
++Size;
}
}接下来分别实现四个函数，这里实际上需要对内部链表开放万能引用原位构造接口来减少 move 增加性能，不过需要利用到 tuple 等特性，会在之后讲解一下，但这里就直接来调用右值引用参数的 Add 接口
void Add(const KeyType& Key, const ValueType& Value)
{
Add(Pair<KeyType, ValueType>(Key, Value));
}
void Add(KeyType&& Key, const ValueType& Value)
{
Add(Pair<KeyType, ValueType>(std::move(Key), Value));
}
void Add(const KeyType& Key, ValueType&& Value)
{
Add(Pair<KeyType, ValueType>(Key, std::move(Value)));
}
void Add(KeyType&& Key, ValueType&& Value)
{
Add(Pair<KeyType, ValueType>(std::move(Key), std::move(Value)));
}HashMap(const HashMap& NewMap)
{
Capacity = NewMap.GetCapacity();
Size = NewMap.GetSize();
Map = NewMap;
}
HashMap(HashMap&& NewMap) noexcept
{
Capacity = NewMap.GetCapacity();
Size = NewMap.GetSize();
Map = std::move(NewMap);
}对重要的资源进行拷贝或移动（需要数组支持移动赋值运算符与复制赋值运算符），对基本数据类型进行拷贝。
HashMap& operator= (const HashMap& NewMap)
{
Capacity = NewMap.GetCapacity();
Size = NewMap.GetSize();
Map = NewMap.GetMap();
return *this;
}
HashMap& operator= (HashMap&& NewMap) noexcept
{
Capacity = NewMap.GetCapacity();
Size = NewMap.GetSize();
Map = std::move(NewMap.GetMap());
return *this;
}// 这个作为存储 HashMap 具体内容的类型疑似有点太长了，这里可以替换成
Array<LinkedList<Pair<KeyType, ValueType>>> Map;
using MapType = Array<LinkedList<Pair<KeyType, ValueType>>>;
MapType Map;然后在实现 getter 的时候可以
[[nodiscard]] SizeType GetCapacity() const { return Capacity; }
[[nodiscard]] SizeType GetSize() const { return Size; }
[[nodiscard]] MapType& GetMap() { return Map; }
[[nodiscard]] const MapType& GetMap() const { return Map; }HashMap<int32, String> Map;
Map.Add(Pair(1, String("This is one.")));
Map.Add(Pair(2, String("This is two.")));
Map.Add(Pair(3, String("This is three.")));
Map.Add(Pair(4, String("This is four")));
HashMap<int32, String> CopyConstruction = Map;
for (auto i : CopyConstruction)
{
std::cout << i.GetValue() << "\n";
}
HashMap<int32, String> MoveConstruction = {{1, "Test1"}, {2, "Test2"}};
for (auto i : MoveConstruction)
{
std::cout << i.GetValue() << "\n";
}
HashMap<int32, String> CopyAssign = Map;
for (auto i : CopyAssign)
{
std::cout << i.GetValue() << "\n";
}
HashMap<int32, String> MoveAssign = {{1, "Test1"}};
MoveAssign = {{2, "Test2"}};
for (auto i : MoveAssign)
{
std::cout << i.GetValue() << "\n";
}均运行正常。
以后再更