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

Как уменьшить число коллизий? - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Игра "Угадай число" http://www.cyberforum.ru/cpp-beginners/thread975243.html
#include <iostream> #include <ctime> using namespace std; int main(){ setlocale(LC_ALL,"rus"); int num, ques, i, menu=1, score=0; do{
C++ ааааааааааааааааа, почему не компилируется? #include <iostream> #include <conio.h> #include <locale.h> #include <cmath> using namespace std; float distance(float v, float a) { return v*v*sin(2*a* 3.14/180)/9.81; } http://www.cyberforum.ru/cpp-beginners/thread975234.html
C++ Найти S и P четных чисел от 1 до n
Задача: Найти сумму S и произведение P четных чисел от 1 до n.
Прерываемый "бесконечный" цикл C++
требуется запилить цикл вида: /*6. Бесконечно выполнять следующий цикл: 6.1. Ждать с консоли одну из команд: - «чтение» сообщения из контейнера; - «выход» из цикла; 6.2. При поступлении команды «читать»: - ввести одно сообщение из файла, контейнера сообщений; - вывести его на консоль;
C++ Можно ли вписать в круг треугольник? http://www.cyberforum.ru/cpp-beginners/thread975224.html
Нужна помощь в решении задачи. Даны площадь круга S1 и площадь треугольника S2. Определить, поместится ли треугольник в круге. Добавлено через 6 минут Изначально решение такое: #include <stdio.h> #include <math.h> #include <conio.h> #include <stdlib.h> void main()
C++ Вычислить последовательность Задание: Вычислить сумму: S=1+1*2+1*2*3+1*2*3*4+...+1*2*3*...*n подробнее

Показать сообщение отдельно
no SOPA
0 / 0 / 1
Регистрация: 20.02.2012
Сообщений: 41

Как уменьшить число коллизий? - C++

12.10.2013, 04:30. Просмотров 262. Ответов 0
Метки (Все метки)

Задание: хеш-таблица с мультипликативной хеширующей функцией (метод умножения) и решением коллизий внутренними (срастающимися) цепочками.

вот, что у меня получилось

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); извращался, и размер таблицы менял, не помогает. Кто знает, что делать, помогите пожалуйста.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru