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

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

Войти
Регистрация
Восстановить пароль
 
no SOPA
0 / 0 / 1
Регистрация: 20.02.2012
Сообщений: 41
#1

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

12.10.2013, 04:30. Просмотров 265. Ответов 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); извращался, и размер таблицы менял, не помогает. Кто знает, что делать, помогите пожалуйста.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.10.2013, 04:30     Как уменьшить число коллизий?
Посмотрите здесь:

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

Уменьшить число в 2 раза - C++
Дано натуральное число N. Уменьшить число в 2 раза (деление нацело). Проверить, изменилось ли после уменьшения количество разрядов в ...

Введенное отрицательное число уменьшить на 2 - C++
Если введено отрицательное число требуется отнять от него 2. Так не получается ввожу -5 оно выводит -5... #include &lt;iostream&gt; ...

Уменьшить число в 2 раза (деление нацело) - C++
Дано натуральное число N. Уменьшить число в 2 раза (деление нацело). Проверить, изменилось ли после уменьшения количество разрядов в ...

Все положительные элементы массива уменьшить на заданное число - C++
Нам дали задачу, а я не понимаю как написать к ней код. Помогите кому не лень:3 Задача: Дан массив. Все его положительные элементы...

Дан массив. Все его элементы уменьшить на число А - C++
Прошу помощи. C++

Уменьшить все числа заданной последовательности, начиная с первого положительного, на указанное число - C++
Даны действительные числа a1,…, a37. Все числа этой последовательности, начиная с первого положительного, уменьшить на 0.5. Помогите плиз....

Уменьшить первое введённое число в два раза, если оно больше второго по абсолютной величине - C++
Составить программу, которая уменьшает первое введённое число в два раза, если оно больше второго введённого числа по абсолютной величине.

если сумму цифр введенного трехзначного числа N кратна трем, то увеличить число на единицу, иначе-уменьшить вдвое - C++
если сумму цифр введенного трехзначного числа N кратна трем, то увеличить число на единицу, иначе-уменьшить вдвое. Напишите текст...

Ввести целое двузначное число, 2ю цифру числа увеличить в 2 раза, 1ю - уменьшить в 2 раза - C++
я еще плохо ознакомлен с кодами с++,поэтому обращаюсь к вам задача выглядит так: 1)ввести с клавиатуры целое двузначное число ,2ю цифру...

Как уменьшить количество кода? - C++
Здравствуйте. Имеется костыль код. Этот код делает типа &quot;сколько чисел вместится в одно большое число&quot;. Так, как я с С++ недавно, решил...

Как уменьшить чувствительность мыши? - C++
Какой WIN API функцией можно на некоторое время уменьшить чувствительность мыши, не только в окне программы но и во всей винде?


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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