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

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

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

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

13.10.2013, 01:24. Просмотров 432. Ответов 2
Метки нет (Все метки)

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

вот, что у меня получилось
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); извращался, и размер таблицы менял, не помогает. Кто знает, что делать, помогите пожалуйста.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.10.2013, 01:24
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Уменьшить число коллизий хеш-таблицы (C++):

Хеш таблицы - C++
Начал изучать хеш таблицы. Подскажите насчёт хеш таблиц с открытимы адрессами: - Должны ли мы инициализировать значение ключа...

хеш-таблицы - C++
Реализовать ассоциативный массив в виде хеш-таблицы с операциями добавления, поиска . Ключом массива должна быть строка, значением – целое...

Реализация хеш-таблицы - C++
Всем привет. Нужна помощь с заданием:

Если заданное число больше 3, то увеличить число на 10, иначе уменьшить на 10 - C++
Помогите написать программу. Дано число. Если оно больше 3, то увеличить число на 10, иначе уменьшить на 10

для чего нужны хеш таблицы? - C++
для чего нужны хеш таблицы? если есть массивы )

Хеш-таблицы: string subscript out of range - C++
#include &lt;iostream&gt; #include &lt;string.h&gt; #include &lt;string&gt; using namespace std; typedef string nametype; struct celltype { ...

2
monolit
185 / 184 / 22
Регистрация: 24.03.2011
Сообщений: 667
Завершенные тесты: 1
13.10.2013, 01:27 #2
бери другую хэш функцию...
0
no SOPA
0 / 0 / 1
Регистрация: 20.02.2012
Сообщений: 41
13.10.2013, 03:28  [ТС] #3
monolit, я бы с радостью, но по заданию нужна именно такая хеш-функция

Добавлено через 1 час 52 минуты
Написал хеш-функцию тем же методом, но по другой формуле
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int Get_index(char* str)
{
    int result = 0;
    
    int x = 0;
    while (str[x] != '\0')
    {
        result += (int) str[x];   // Переводим из char в int
        x++;
    } 
    
    //result = (21 * (result))>>(16-5);   // h = (A * K) >> (w - m)
    float A =((sqrt(5) - 1)/2);    //золотое сечение по Кнуту
    result = M * fmod((A*result),1);
 
    //return (int) keyword;
    return (int) result;
}
Коллизий стало 4. Но лучше, чтобы не больше 3. Буду дальше колдовать.

Добавлено через 4 минуты
Изменил размер таблицы с 32 до 64 и коллизий стало 2.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.10.2013, 03:28
Привет! Вот еще темы с ответами:

Не могу найти ошибку. Хеш-таблицы - C++
Программа работает, в принципе, правильно, но есть маленькие погрешности при поиске элементов. То есть мы точно знаем, что элемент такой...

Данные о читателях должны быть организованны в виде хеш-таблицы - C++
Данные о каждом читателе должны содержать: № читательского билета – строка формата «ANNNN-YY», где A – буква, обозначающая права доступа...

Хеш-таблицы, сгенерировать список различных слов в тексте (с количеством вхождений их в этот текст) - C++
Напишите компьютерную программу которая использует хеширование для следующей задачи. Имеется текст на естественном языке. Требует- ся...

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


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

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

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