数据结构⚓︎

#include <functional>
#include <string>
#include <unordered_map>

struct PlayerId {
    int server_id;
    std::string account_name;

    bool operator==(const PlayerId& other) const {
        return server_id == other.server_id &&
               account_name == other.account_name;
    }
};

struct PlayerIdHash {
    std::size_t operator()(const PlayerId& key) const {
        std::size_t h1 = std::hash<int>{}(key.server_id);
        std::size_t h2 = std::hash<std::string>{}(key.account_name);
        // 组合哈希，降低字段相关性导致的碰撞概率。
        return h1 ^ (h2 + 0x9e3779b9 + (h1 << 6) + (h1 >> 2));
    }
};

std::unordered_map<PlayerId, int, PlayerIdHash> scores;

#include <functional>
#include <list>
#include <memory>
#include <mutex>
#include <shared_mutex>
#include <vector>

template <typename K, typename V>
class StripedHashTable {
private:
    struct Node {
        K key;
        V value;
        Node(const K& k, const V& v) : key(k), value(v) {}
    };

    size_t num_buckets;
    size_t num_stripes;
    std::vector<std::list<Node>> buckets;
    std::vector<std::unique_ptr<std::shared_mutex>> locks;
    std::hash<K> hasher;

    size_t bucket_index(const K& key) const {
        return hasher(key) % num_buckets;
    }

    size_t stripe_index(size_t bkt) const {
        return bkt % num_stripes;
    }

public:
    StripedHashTable(size_t b = 1024, size_t s = 16)
        : num_buckets(b), num_stripes(s), buckets(b) {
        for (size_t i = 0; i < num_stripes; ++i) {
            locks.push_back(std::make_unique<std::shared_mutex>());
        }
    }

    void insert(const K& key, const V& value) {
        size_t bkt = bucket_index(key);
        size_t stp = stripe_index(bkt);
        std::unique_lock<std::shared_mutex> guard(*locks[stp]);

        auto& bucket = buckets[bkt];
        for (auto& node : bucket) {
            if (node.key == key) {
                node.value = value;
                return;
            }
        }
        bucket.emplace_front(key, value);
    }

    bool find(const K& key, V& out) const {
        size_t bkt = bucket_index(key);
        size_t stp = stripe_index(bkt);
        std::shared_lock<std::shared_mutex> guard(*locks[stp]);

        const auto& bucket = buckets[bkt];
        for (const auto& node : bucket) {
            if (node.key == key) {
                out = node.value;
                return true;
            }
        }
        return false;
    }
};

#include <iostream>
#include <vector>
#include <memory>

const int BUCKET_SIZE = 4;

struct Bucket {
    int local_depth;
    std::vector<int> values;
    Bucket(int depth) : local_depth(depth) {}
    bool is_full() const { return values.size() == BUCKET_SIZE; }
};

class ExtendibleHashTable {
    int global_depth;
    std::vector<std::shared_ptr<Bucket>> directory;

    int hash(int key) const {
        // 简单的取低位哈希处理
        return key & ((1 << global_depth) - 1);
    }

public:
    ExtendibleHashTable() : global_depth(1), directory(2) {
        directory[0] = std::make_shared<Bucket>(1);
        directory[1] = std::make_shared<Bucket>(1);
    }

    void insert(int key) {
        int dir_idx = hash(key);
        auto target_bucket = directory[dir_idx];

        if (!target_bucket->is_full()) {
            target_bucket->values.push_back(key);
            return;
        }

        // 触发分裂
        if (target_bucket->local_depth == global_depth) {
            // 扩展目录字典，全局深度翻倍
            int new_size = 1 << (global_depth + 1);
            std::vector<std::shared_ptr<Bucket>> new_dir(new_size);
            for (int i = 0; i < (1 << global_depth); ++i) {
                new_dir[i] = directory[i];
                new_dir[i + (1 << global_depth)] = directory[i];
            }
            directory = std::move(new_dir);
            global_depth++;
        }

        // 分裂局部桶
        int ld = target_bucket->local_depth;
        auto b0 = std::make_shared<Bucket>(ld + 1);
        auto b1 = std::make_shared<Bucket>(ld + 1);

        // 拆分原始数据 (根据当前增加的一位来分配)
        for (int v : target_bucket->values) {
            int bit = (v >> ld) & 1;
            (bit ? b1 : b0)->values.push_back(v);
        }

        // 更新目录的指针映射
        int mask = (1 << ld) - 1;
        int base_idx = dir_idx & mask;
        for (int i = 0; i < (1 << global_depth); ++i) {
            if ((i & mask) == base_idx) {
                int bit = (i >> ld) & 1;
                directory[i] = bit ? b1 : b0;
            }
        }

        // 数据迁移完成后重新插入当前元素
        insert(key);
    }
};

#include <cstdint>

// 反转哈希值的位数，作为映射至 Split-Ordered List 的全局排序依据
// 这里展示了 32 位整型数据的常数级运算比特反转
inline uint32_t reverse_bits(uint32_t key) {
    uint32_t v = key;
    v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1);
    v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2);
    v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4);
    v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8);
    v = ( v >> 16             ) | ( v               << 16);
    return v;
}

// 将普通哈希键转化为排序所需 Regular Key
inline uint64_t make_regular_key(uint32_t hash_val) {
    return (static_cast<uint64_t>(reverse_bits(hash_val)) | 1);
}

// 将桶序列转化为排序所需的 Dummy Key
inline uint64_t make_dummy_key(uint32_t bucket_idx) {
    return static_cast<uint64_t>(reverse_bits(bucket_idx)); // 最低位自然为 0
}

/* 
 下方为伪代码概括结构插入思想，使用 CAS 或封装的无锁结构代替直接的指针赋值 
*/
struct Node {
    uint64_t sort_key;
    int value;
    Node* next; // 实际实现中为 Atomic Marked Pointer

    Node(uint64_t k, int v) : sort_key(k), value(v), next(nullptr) {}
};

// 假设通过位反转建立的新结点，将按照 sort_key 直接嵌入已包含 dummy 节点的单链表中
// Node* new_node = new Node(make_regular_key(hash), val);
// list_insert_lockfree(head, new_node);