Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
fractalon
0 / 0 / 0
Регистрация: 11.11.2014
Сообщений: 1
#1

Реализация совершенного хеширования FKS - Алгоритмы

11.11.2014, 18:25. Просмотров 802. Ответов 0
Метки нет (Все метки)

Не знаю, в тематике ли форума говорить про реализацию. Если что - извиняйте.

Нужно реализовать совершенное хеширование. Сначало дано некоторое фиксированное множество целых чисел из [-10^9;10^9], по нему нжуно составить линейную по памяти таблицу за линейной в среднем время. В общем, используется двухуровневое хеширование по известному алгоритму:
  • Используем линейное хешировние ((ax+b) mod p) mod n, где p=2*10^9+11 - простое
  • Делаем внешнюю хеш-таблицу размера n (количество элементов)
  • Подбираем случайные a и b из [0;p] (p - простое) пока сумма квадратов количеств значений в каждой ячейке не станет меньше 3n (вероятность этого при случайных a и b больше 0.5)
  • Для каждой ячейки строим квадратичную хеш-таблицу и подбираем (тем же случайным выбором) тамошние параметры a и b таким образом, чтобы каждое значение легло в свою ячейку
  • При запросе считаем внешнюю хеш-функцию и функцию второго уровня

Попробовал реализовать алгоритм. Вот что получилось:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <iostream>
#include <algorithm>
#include <vector>
 
using std::cin;
using std::cout;
using std::endl;
using std::vector;
 
const int PRIME_MOD = 2 * 1000 * 1000 * 1000 + 11;
 
int getRandFromPrimeMod()
{
    long long nowRand;
    do
    {
        nowRand = (rand() % 10000) +
                  (rand() % 10000) * 1ll * 10000 +
                  (rand() % 25) * 1ll * 10000 * 10000;
    }while (nowRand >= PRIME_MOD);
    return static_cast<int>(nowRand);
}
 
class HashFunction
{
public:
    void generate(int m_tableSize)
    {
        tableSize = m_tableSize;
        multiplier = getRandFromPrimeMod();
        addend = getRandFromPrimeMod();
    }
    int operator()(int value)
    {
        long long toPrime = (multiplier *
                            static_cast<long long>(value) + addend) % PRIME_MOD;
        if (toPrime < 0)
        {
            toPrime += PRIME_MOD;
        }
        return toPrime % tableSize;
    }
private:
    int multiplier, addend;
    int tableSize;
};
 
class PrimitiveFixedSet
{
public:
    void initialize(const vector<int> &elements)
    {
        int dataSize = elements.size();
        if (dataSize == 0)
        {
            return;
        }
        if (dataSize == 1)
        {
            table.assign(1, elements[0]);
            getHash.generate(table.size());
            return;
        }
        table.resize(dataSize * dataSize, PRIME_MOD);
        vector<int> hashArray(dataSize);
 
        bool existCollizian;
        do
        {
            getHash.generate(table.size());
 
            existCollizian = false;
            vector<char> existAntihash(table.size(), false);
            for (int i = 0 ; i < dataSize ; ++i)
            {
                hashArray[i] = getHash(elements[i]);
                if (existAntihash[hashArray[i]])
                {
                    existCollizian = true;
                    break;
                }
                existAntihash[hashArray[i]] = true;
            }
        }while (existCollizian);
 
        for (int i = 0 ; i < dataSize ; ++i)
        {
            table[hashArray[i]] = elements[i];
        }
    }
 
    bool containts(int value)
    {
        if (table.size() == 0)
        {
            return false;
        }
        int hash = getHash(value);
        return table[hash] == value;
    }
private:
    vector<int> table;
    HashFunction getHash;
};
 
long long getSumSquare(const vector<int> &data)
{
    int dataSize = data.size();
    long long answer = 0;
    for (int i = 0 ; i < dataSize ; ++i)
    {
        answer += static_cast<long long>(data[i]) *
                  static_cast<long long>(data[i]);
    }
    return answer;
}
 
class FixedSet
{
public:
    void initialize(const vector<int> &elements)
    {
        int dataSize = elements.size();
        table.resize(dataSize);
 
        bool collizianIsLinear;
        vector<int> hashArray(dataSize);
        do
        {
            getHash.generate(table.size());
            vector<int> collizianCounter(table.size(), 0);
            for (int i = 0 ; i < dataSize ; ++i)
            {
                hashArray[i] = getHash(elements[i]);
                ++collizianCounter[hashArray[i]];
            }
            collizianIsLinear = (getSumSquare(collizianCounter) <= 3 * dataSize);
        }while (!collizianIsLinear);
 
        vector< vector<int> > hashSeparation(table.size());
        for (int i = 0 ; i < dataSize ; ++i)
        {
            hashSeparation[hashArray[i]].push_back(elements[i]);
        }
 
        for (size_t i = 0 ; i < table.size() ; ++i)
        {
            table[i].initialize(hashSeparation[i]);
        }
    }
 
    bool containts(int value)
    {
        int hash = getHash(value);
        return table[hash].containts(value);
    }
private:
    vector<PrimitiveFixedSet> table;
    HashFunction getHash;
};
Так вот, где-то здесь ошибка. Только где - отловить невозможно. Заваливается на каком-то неизвестном тесте в проверяющей системе. Когда же делаю у себя на компьютере случайные тесты, то работает хорошо, быстро. То есть в какой-то мелочи накосячил и есть контрпример.

Если будет время, посмотрите, пожалуйста, чистыми глазами. Спасибо.
http://www.cyberforum.ru/algorithms/thread158247.html
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.11.2014, 18:25
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Реализация совершенного хеширования FKS (Алгоритмы):

По поводу алгоритма хеширования Md5
Объясните плыз более менее русским языком принцип хеширования, по какому...

Как определить алгоритм хеширования?
Есть некий алгоритм очень простого хеширования, нужно определить какие операции...

Реализация алгоритма хеширования scrypt
Приветствую всех! Подскажите, существует ли реализация алгоритма...

Реализация хеширования с цепочками переполнения
Надо писать курсач. Хеширование с цепочками переполнения на Delphi. Ничего не...

Реализация поиска на основе метода хеширования
Ребята, если кто знает где можно найти толковые примеры(листинги) с применением...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.11.2014, 18:25
Привет! Вот еще темы с решениями:

Поиск совершенного числа
Совершенное число́ (др.-греч. ἀριθμὸς τέλειος) — натуральное число, равное...

Определение совершенного числа
Напишите программу, определяющую, является ли введенное пользователем...

Поиск совершенного числа
Здравствуйте ! Подскажите как найти совершенное число , т.е. число равное...

Поиск совершенного числа в массиве
Необходимо найти в массиве все совершенные числа в диапазоне от n1 до n2. Будем...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru