Форум программистов, компьютерный форум CyberForum.ru

Уменьшить число коллизий хеш-таблицы - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Замена кода символа на его значение http://www.cyberforum.ru/cpp-beginners/thread975883.html
Здравствуйте, есть строка string url = "«Открой меня!™»"; как можно заменить коды символов на их значения?
C++ Не могу разобраться с алгоритмом Проанализируйте блок-схему алгоритма на рис.5. Определите, какое сообщение необходимо выводить вместо ??? На входе алгоритма: вводится последовательность чисел, 0 - конец последовательности, x0 - текущий член последовательности, x1 - следующий член последовательности. http://www.cyberforum.ru/cpp-beginners/thread975876.html
C++ По поводу расширения окна
Здравствуйте, очень хочу узнать. Как в играх делают окно игры на весь экран? И возможно ли это в простых формах. Допустим при запуске формы, форма полностью занимала размер твоего экрана. Не так чтоб ее можно было растянуть, а полностью. Чтоб ни пуска не было видно ничего.
Заполнить массив случайными символами C++
Нужно заполнить массив случайными символами(буквами и числами). Как это можно сделать с помощью rand?
C++ Дана целочисленная матрица A (N,M), в которой имеются ровно два одинаковых элемента. Найти индексы этих элементов http://www.cyberforum.ru/cpp-beginners/thread975855.html
Дана целочисленная матрица A (N,M), в которой имеются ровно два одинаковых элемента. Найти индексы этих элементов. Написал такую хрень, но она мне не нравится, слишком все как то запутано, попроще нельзя? #include <iostream> #include <cstdlib> #include <clocale> #include <ctime> using namespace std;
C++ Выход из программы по нажатию Esc подскажите как сделать чтобы по нажатию ESC выводился результат.затупил чутка int main(){ setlocale(LC_ALL, "RUS"); toll_Both car_1; char button; cout << "y - заплатил, n - не заплатил, esc - вывести результат." << endl; while(1){ cout << "выберете нужный Вам вариант: y/n/esc." << endl; cin >> button; switch(button){ подробнее

Показать сообщение отдельно
no SOPA
0 / 0 / 1
Регистрация: 20.02.2012
Сообщений: 41
13.10.2013, 01:24     Уменьшить число коллизий хеш-таблицы
Задание: хеш-таблица с мультипликативной хеширующей функцией (метод умножения) и решением коллизий внутренними (срастающимися) цепочками.

вот, что у меня получилось
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
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
 
#define table_items 17         // число элементов таблицы
#define M 32                  // размер таблицы
 
typedef struct 
{
    char* k;
    char* p;
} tab_elem; 
 
tab_elem table[M];
 
tab_elem tabtemp = table[0];
 
int Get_index(char* str)
{
    int result = 0;
    
    int x = 0;
    while (str[x] != '\0')
        {
        result += (int) str[x];   // Переводим из char в int
        x++;
    } 
    
    result = (31 * (result))>>(16-6);   // h = (A * K) >> (w - m)
 
    //return (int) keyword;
    return (int) result;
}
 
void make_table (char* items[table_items])    //создание таблицы
{
    int Index;
    int i, j, h, b=0;
    tab_elem *pointer;       // Указатель на элемент
 
    for (i=0; i<M; i++)            //Очищаем таблицу
    { 
        table[i].k="";    //В поле ключа помещаем признак незанятости
        table[i].p=NULL;  //указатели на null
    }
    
    for (i=0; i<table_items; i++)          //заполнение таблицы
    { 
        h = Get_index(items[i]);    // Вызов генератора ключа        
 
        if (table[h].k=="")   // пустота элемента
        {
            table[h].k=items[i];
        }
        else
        {
                b++;            //считаем коллизии
            if (table[h].p == NULL) // ищем пустую таблицу
            {
                j=h;
                do
                {
                    j++;
                }while (table[j].k != ""); //первый пустой ключ
 
                table[j].k = items[i]; 
 
                table[h].p=(char*)&table[j]; // указатель с текущей таблицы на первую пустую найденную
            }
            else
            {
                pointer = (tab_elem*)table[h].p;
                while (pointer->p != NULL) // поиск первого пустого указателя
                {
                    pointer=(tab_elem*)pointer->p; 
                }
 
                j=h; 
 
                do 
                {
                    j++;
                }while (table[j].k!=""); //первый пустой ключ
 
                table[j].k = items[i]; 
 
                pointer->p = (char*)&table[j]; // указатель с текущей таблицы на первую пустую найденную
            }
        }           
    }
    std::cout<<"coll="<<b<<"\n";
    printf("---HASH_TABLE---\n\n");    //печатаем таблицу
    for (i=0; i<M; i++)
    {
        printf("%i: %s\n", &tabtemp - &table[i], table[i].k);
    }
}
 
void Check_Hash_Table(char* u_key) 
{
    int u_h;
    tab_elem *pointer;
 
    printf("\nFIND \"%s\"\n", u_key);
    u_h = Get_index(u_key); 
    if (table[u_h].k==u_key) // поиск по ключу
    {
        printf("%i: %s\n", &tabtemp - &table[u_h] , u_key);
    }
    else
    { 
        if (table[u_h].p==NULL)  // поиск по указателю
        {
            printf("None\n");
        }
        else
        { 
            pointer = (tab_elem*)table[u_h].p;
            while (pointer->p!=NULL)
            { 
                if (pointer->k==u_key)
                {
                    printf("%i: %s\n", &tabtemp - pointer,u_key);
                }
                pointer = (tab_elem*)pointer->p;
            }
            printf("None\n"); 
        }
    }
}
 
int main()
{
    char* items[table_items] = 
    {
        "START","BYTE","WORD","RESB",
        "RESW","END","CMP","MOV","NOT",
        "ADD","XOR","OR","TEST","DIV","MUL",
        "PUSH","POP"
    };
 
    make_table(items);
    Check_Hash_Table("ADD");
    Check_Hash_Table("OR");
    Check_Hash_Table("JNE");
    Check_Hash_Table("START");
    Check_Hash_Table("BYTE");
    Check_Hash_Table("CMP");
 
    system("pause");
}
Но число коллизий слишком большое. Я и с числами в result = (31 * (result))>>(16-6); извращался, и размер таблицы менял, не помогает. Кто знает, что делать, помогите пожалуйста.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 18:28. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru