Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Gabe
0 / 0 / 0
Регистрация: 31.05.2012
Сообщений: 15
#1

Хеш-таблица. Двойное хеширование, функция – вариант с умножением. При ключе 10 все элементы заполняются, а при 701 - нет - C++

29.04.2014, 12:04. Просмотров 644. Ответов 0
Метки нет (Все метки)

Помогите разобраться почему так, хеш-таблица на 3000 элементов. При ключе 10 все элементы заполняются, а при 701, нет.

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
#ifndef HASH_H
#define HASH_H
 
#include<vector>
#include<math.h>
#include<iostream>
 
const  int m=3000;
 
template <typename T>
class Hash_Table{
    std::vector<std::pair<int, T>> table;
public:
    //-1 - nil
    //-2 - del
    Hash_Table():table(m) {
        for (int i=0; i<table.size(); i++)
            table[i] = std::pair<int, T>(-1, T());
    }
 
    int h(int k) {
        auto a=(sqrt(5)-1)/2;
        return (int)(m*(k*a - (int)(k*a)));
    }
 
    int Double_Hash (int x, int i) {
        std::hash<int> a;
        return ((a(x) + i * h(x)) % m);
    }
 
    void Hash_Ins (int key, T value) {
        int i=0;
        do {
            int j=Double_Hash(key,i);
            if (table[j].first < 0)
            {
                table[j].first = key;
                table[j].second = value;
                return;
            }
            else
                i++;
        }
            while (i!=m);
            throw "Overflow";
    }
 
    int Hash_Search (int key) {
        int i=0;
        int j=0;
        do {
            j=Double_Hash(key,i);
            if (table[j].first == key)
                return table[j].second;
            i++;
        }
            while ((table[j].first!=-1)&&(i!=m));
            return -1;
    }
 
    bool Hash_Del (int key) {
        int i=0;
        int j=0;
        do {
            j=Double_Hash(key,i);
            if (table[j].first == key) {
                table[j].first = -2;
                table[j].second = T();
                return 1;
            }
            i++;
        }
            while ((table[j].first!=-1)&&(i!=m));
            return 0;
    
    }
 
    void print () {
        for (int i=0; i<table.size(); i++) {
            std::cout<<i<<". ";
            if (table[i].first==-1)
                std::cout<<"NUL"<<std::endl;
            else if (table[i].first==-2)
            std::cout<<"DEL"<<std::endl;
            else
            std::cout<<Double_Hash (table[i].first, 0)<<"; Key: "<<table[i].first<<"; Value: "<<table[i].second<<std::endl;
        }
    }
 
    void fill (int key, T value, int p) {
        for (int i = 0; i<(m*p/100); i++)
            Hash_Ins(key, value);
        }
 
    bool chek () {
        for (int i=0; i<m; i++) {
            if (table[i].first==-1)
                return 0;
        }
        return 1;
    }
 
    int largest () {
        int max = 0;
        int max0= 0;
        for (int i=0; i<m; i++) {
            if (table[i].first > -1)
                max0++;
            else
                if (max0>max) {
                    max=max0;
                    max0=0;
                }
                else
                    max0=0;
        }
        return max;
    }
 
};
 
#endif
Косяк какой то в функции h(). С ключом 701, заполняет чуть больше 100 из 3000.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.04.2014, 12:04
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Хеш-таблица. Двойное хеширование, функция – вариант с умножением. При ключе 10 все элементы заполняются, а при 701 - нет (C++):

Хеш-функция, двойное хеширование - C++
Всем привет! Пишу курсач, нужна хеш-функция, которая принимала бы строку и возвращала некий индекс. Написал нечто вроде unsigned...

Почему при загрузке отображается вариант ВИНДЫ, которой уже нет на диске? - Windows XP
Помогите пожалуйста! Когда-то ВиндовсИксПи стоял на диске D, сейчас переустановил на C, почему при загрузке отображается список двух...

Элементы массива заполняются по формуле x*(x-3)*(sqr(x)-81). Найти первые 20 элементов и указать значение x, при которых значения элементов - 0 - Pascal
1. Элементы массива заполняются по формуле x*(x-3)*(sqr(x)-81). Найти первые 20 элементов и указать значение x, при которых значения...

Все просто. Код работает при редактировании, а при добавлении нет - MS Access
Собственно форма открывается с кнопки: Private Sub Кнопка9_Click() DoCmd.OpenForm &quot;FormInbox_New&quot;, acNormal DoCmd.GoToRecord ,...

Все четные элементы массива инвертировать умножением на -1 - C (СИ)
Ввести с клавиатуры количество элементов массива N, потом сами элементы массива – целые числа. Все четные элементы инвертировать умножением...

Все четные элементы массива инвертировать умножением на -1 - C (СИ)
Помогите, пожалуйста, найти ошибки. Задача А. Ввести с клавиатуры количество элементов массива N, потом сами элементы массива – целые...

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

При добавлении в хеш таблицу нового элемента, все остальные данные меняются на последний - C (СИ)
При добавлении в хеш таблицу нового элемента, все остальные данные меняются на последний. Я так понял, ошибка в выделении памяти. Как это...

Как сделать при событии один пункт активным, а все остальные неактивны при условии что это общая функция - jQuery
Вот к примеру: http://jsbin.com/uhiqap/1/edit на галерею когда клацаешь - чтоб была одна фотка большая, только активная при...

Удаление записей при внешнем ключе - Базы данных
Добрый день. Столкнулся с такой проблемой (пока теоритически). Есть база данных с двумя таблицами. Эти таблицы связаны внешним ключом по...

Будет ли течь ток в схеме, при разомкнутом ключе? - Электротехника
Доброго времени суток! Не могу сообразить будет ли течь ток в данной схеме, при разомкнутом ключе, и, если будет, то как? Заранее...


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

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

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