LINUX.ORG.RU

Подскажите готовую реализацию хэш-таблицы для строк.

 


0

3

Нужна готовая реализация контейнера в роде хэш-таблицы, который будет сам вычислять хэш из строки и хранить строку с хэшем в качестве ключа вместе в форме удобной для быстрого поиска. Т.е. нужен контейнер хранящий строки, с их быстрым поиском. Например приблизительно так:

class AnyHashTree;

AnyHashTree container;

container.add("one");
container.add("two");
container.add("three");

bool has = container.has("two");

return has;
Существует ли такое для стандарта языка < c++11? В классических алгоритмах не силён, stl знаю плохо.

Ой, парни, спасибо, нашёл решение - QHash из Qt.

normann ★★ ()

прикольно. отказываться от с++11, зато тянуть Qt.

https://github.com/Tessil/hopscotch-map

C++ implementation of a fast hash map and hash set using hopscotch hashing

#include <chrono>
#include <cstdint>
#include <iostream>
#include "hopscotch_map.h"
#include "hopscotch_sc_map.h"

/*
 * Poor hash function which always returns 1 to simulate
 * a Deny of Service attack.
 */
struct dos_attack_simulation_hash {
    std::size_t operator()(int id) const {
        return 1;
    }
};

int main() {
    /*
     * Slow due to the hash function, insertions are done in O(n).
     */
    tsl::hopscotch_map<int, int, dos_attack_simulation_hash> map;
    
    auto start = std::chrono::high_resolution_clock::now();
    for(int i=0; i < 10000; i++) {
        map.insert({i, 0});
    }
    auto end = std::chrono::high_resolution_clock::now();
    
    // 110 ms
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end-start);
    std::cout << duration.count() << " ms" << std::endl;
    
    
    
    
    /*
     * Faster. Even with the poor hash function, insertions end-up to
     * be O(log n) in average (and O(n) when a rehash occurs).
     */
    tsl::hopscotch_sc_map<int, int, dos_attack_simulation_hash> map_secure;
    
    start = std::chrono::high_resolution_clock::now();
    for(int i=0; i < 10000; i++) {
        map_secure.insert({i, 0});
    }
    end = std::chrono::high_resolution_clock::now();
    
    // 2 ms
    duration = std::chrono::duration_cast<std::chrono::milliseconds>(end-start);
    std::cout << duration.count() << " ms" << std::endl;
} 

The code is licensed under the MIT license

anonymous ()
Ответ на: комментарий от anonymous

прикольно. отказываться от с++11, зато тянуть Qt.

В реальной жизни тебе придётся отказываться от всего что недопустимо в проекте, которым руководишь не ты.

normann ★★ ()
Ответ на: комментарий от normann

просто тянуть qt ради хешей слишком уж жирно выходит. а тут тебе только хедер подключить нужно... да и лицензия MIT дает больше свободы. ты же в курсе, какие ограничения накладывает GPL/LGPL на твой проект?

anonymous ()
inline constexpr std::uint32_t fnv1a(const char* str, std::uint32_t hash = 2166136261UL) {
    return *str ? fnv1a(str + 1, (hash ^ *str) * 16777619ULL) : hash;
}

int main() {
    std::string s = "bb";

    switch (fnv1a(s.c_str())) {
    case fnv1a("a"): std::cout << "A\n"; break;
    case fnv1a("bb"): std::cout << "B\n"; break;
    case fnv1a("ccc"): std::cout << "C\n"; break;
    };    
}

код не мой, отсюда: https://ru.stackoverflow.com/questions/7920/switch-%d0%b4%d0%bb%d1%8f-string

xperious ★★ ()
Последнее исправление: xperious (всего исправлений: 1)
Ответ на: комментарий от normann

LGPL не накладывает

Накладывает. Хотя нынче модно быть пиратом, и чихать на лицензии :(

fsb4000 ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.