# flat_hash_map

**Repository Path**: shines77/flat_hash_map

## Basic Information

- **Project Name**: flat_hash_map
- **Description**: A very fast hashtable (Mirror)
- **Primary Language**: C++
- **License**: BSL-1.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2022-06-17
- **Last Updated**: 2024-05-01

## Categories & Tags

**Categories**: Uncategorized

**Tags**: Cpp

## README

# flat_hash_map

## Introduction

A new fast hash table in response to Google’s new fast hash table

by `Malte Skarupke`

[https://github.com/skarupke/flat_hash_map](https://github.com/skarupke/flat_hash_map)

Hi, I wrote my new favorite hash table. This came about because last year I wrote the fastest hash table (I still make that claim) and this year one of the organizers of the C++Now conference asked me to give a talk. My problem was that Google had also announced a new fast hash table last year, and I wasn’t sure if mine would compare well against theirs.

The main benefit of Google’s hash table over mine was that Google’s has less memory overhead: It has a higher max_load_factor (meaning how full can the table get before it grows to a bigger array) and it has only 1 byte overhead per entry, where the overhead of my table depended on the alignment of your data. (if your data is 8 byte aligned, you’ll have 8 bytes overhead)

So I spent months working on that conference talk, trying to find something that would be a good response to Google’s hash table. Surprisingly enough I ended up with a chaining hash table that is almost as fast as my hash table from last year, while having even less memory overhead than Google’s hash table and which has this really nice property of having stable performance: Every hash table has some performance pitfalls, but this one has fewer than most and will cause problems less often than others will. So what that does is that it’s a hash table that’s really easy to recommend.

## Chinese / 中文版

这是 `Malte Skarupke` 写的高性能哈希表的镜像仓库。

原仓库地址：[https://github.com/skarupke/flat_hash_map](https://github.com/skarupke/flat_hash_map)

为了能够在 [https://gitee.com/shines77/hashmap-benchmark](https://gitee.com/shines77/hashmap-benchmark) 中编译和测试，

本人对代码做了如下修改：

* 修复了 `ska::detailv3::KeyOrValueHasher<K, V, Hasher>` 存在的问题, 以便能够在 `/bench/time_hash_map.cpp` 中使用 `ska::flat_hash_map<K,V>` 和 `ska::bytell_hash_map<K,V>`;
* 修复了 `ska::bytell_hash_map<K,V>` 几个会导致死循环的 `bug`;
* 添加了 `bytell_hash_map.hpp` 中缺失的头文件 "#include \<limits\>";
* 为 `ska::flat_hash_map<K,V>` 和 `ska::bytell_hash_map<K,V>` 添加了静态成员函数 `name()`;

## 视频

作者 `Malte Skarupke` 在 `CppCon 2018` 上做了演讲，视频在这里：

1. `[C++Now 2018: You Can Do Better than std::unordered_map: New Improvements to Hash Table Performance]`

    [https://www.youtube.com/watch?v=M2fKMP47slQ](https://www.youtube.com/watch?v=M2fKMP47slQ)

## English / 英文版

This is a mirror repository for high performance hash tables written by `Malte Skarupke`.

Original repository: [https://github.com/skarupke/flat_hash_map](https://github.com/skarupke/flat_hash_map)

To be able to compile and test in [https://gitee.com/shines77/hashmap-benchmark](https://gitee.com/shines77/hashmap-benchmark),

I made the following modifications to the code:

* Fixed ska::detailv3::KeyOrValueHasher<K, V, Hasher> for /bench/time_hash_map.cpp to use ska::flat_hash_map<K,V> and ska::bytell_hash_map<K,V>;
* Fixed some bugs about ska::bytell_hash_map<K,V> some dead cycle codes;
* Added missing header file "#include \<limits\>" in bytell_hash_map.hpp;
* Added static name() member method for ska::flat_hash_map<K,V> and ska::bytell_hash_map<K,V>;

## Video

Author `Malte Skarupke` gave a talk at `C++Now 2018`, the video is here:

1. `[C++Now 2018: You Can Do Better than std::unordered_map: New Improvements to Hash Table Performance]`

    [https://www.youtube.com/watch?v=M2fKMP47slQ](https://www.youtube.com/watch?v=M2fKMP47slQ)