Hash算法在C++中的穩定性

在C++中，哈希算法本身并不保證穩定性。穩定性是指排序后具有相同鍵值的元素在排序前后的相對順序保持不變。然而，C++標準庫中的std::unordered_map和std::unordered_set容器是基于哈希表實現的，它們不保證穩定性。

如果你需要一個穩定的哈希表實現，你可以考慮使用第三方庫，如Boost.Unordered或者自己實現一個穩定的哈希表。以下是一個簡單的穩定哈希表實現示例：

#include <iostream>
#include <list>
#include <vector>
#include <algorithm>

template<typename Key, typename Value>
class StableHashTable {
public:
    void insert(const Key& key, const Value& value) {
        if (find(key) == buckets.end()) {
            buckets.push_back(std::make_pair(key, value));
            indices.push_back(buckets.size() - 1);
        } else {
            int index = find(key) - indices.begin();
            buckets[index].second = value;
        }
    }

    bool find(const Key& key) const {
        auto it = std::find_if(buckets.begin(), buckets.end(), [&](const auto& p) { return p.first == key; });
        return it != buckets.end();
    }

    Value get(const Key& key) const {
        auto it = find(key);
        return it != buckets.end() ? it->second : Value();
    }

    void remove(const Key& key) {
        auto it = find(key);
        if (it != buckets.end()) {
            int index = it - indices.begin();
            int last_index = --indices.end() - indices.begin();
            if (index != last_index) {
                std::swap(buckets[index], buckets[last_index]);
                std::swap(indices[index], indices[last_index]);
            }
            buckets.pop_back();
            indices.pop_back();
        }
    }

private:
    std::vector<std::pair<Key, Value>> buckets;
    std::vector<int> indices;
};

int main() {
    StableHashTable<int, std::string> table;
    table.insert(1, "one");
    table.insert(2, "two");
    table.insert(3, "three");

    std::cout << "Find 1: " << table.get(1) << std::endl;
    std::cout << "Find 2: " << table.get(2) << std::endl;
    std::cout << "Find 3: " << table.get(3) << std::endl;

    table.remove(2);
    std::cout << "Find 2 after removal: " << (table.find(2) != table.buckets.end() ? table.get(2) : "Not found") << std::endl;

    return 0;
}

這個示例實現了一個簡單的穩定哈希表，它使用std::list來存儲鍵值對，以保持插入順序。當插入、刪除或查找元素時，它會更新索引數組以保持穩定性。請注意，這個實現僅用于演示目的，實際應用中可能需要進一步優化和調整。