Хэш-функции

@Aidana · Регистрация: 16.01.2016

Author24 — интернет-сервис помощи студентам

Хэш-функции и таблицы

Задание
1. Придумайте некоторую хэш-функцию и вкратце проанализируйте ее, учитывая сложность подсчета и вероятности появления коллизий.
2. Используя Вашу хэш-функцию, реализуйте 2 подхода к построению хэш-таблиц с помощью цепочек и с открытой адресацией (к примеру, линейное или квадратичное пробирование из книги Кормена, глава «Хэш-таблицы»).
3. Для каждого из 2-х подходов оцените время (сложность, т.е. количество сравнений элементов) для поиска случайного числа х (предполагайте, что Ваши ключи должны быть большими или используйте строки, так как для малых значений существует прямой метод индексации). В итоге, в среднем случае сложность занимает O(1+eps) времени, но это зависит от Вашей хэш-функции и наша цель проверить данное утверждение.

@Еужения · 22.11.2009, 14:22

Вот реализация С++ посторение хэш-таблицы методом цепочек

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
152
153
154
155
156
157
158
159
160
161
#inclide <stdio.h>
#inclide <conio.h>
 
#define n 25
 
struct line //списочная структура для Метода цепочек
{
    int key; //ключ
    int adr; //адрес
    line *next; //указатель на след. узел
};
 
int hash (int key)
{
    //тут пишешь любую хэш-функцию
    return key%21; //коллизия при ключах 22-25
}
 
void main ()
{
    line table[n];
    int i, j=0, ch=1, key;
    line* cur=null, pcur=null;
    //очищение хэш-таблицы
    for(i=0; i<n; i++)
    {
        table[i].key = null;
        table[i].adr = null;
        table[i].next = null;
    }
    clrscr();
    while(ch != 0)
    {
        printf("\t\t\tМеню: выберите действие\n\t1 - вывести хэш-таблицу.\n\t2 - новый ключ.\n\t3 Поиск. 0 Выход\n");
        scanf("%d", &ch);
        if(ch > 1)
        {
            printf("Введите ключ: ");
            scanf ("%d", &key);
        }
        switch(ch)
            case 1: for(i=0;i<n;i++)
                {
                    ch=0;
                    cur = table[i];
                    do
                    {
                        printf("[%d][%d]", i+1, ++ch, cur->key, cur->adr);
                        cur=cur->next;
                    }
                    while(cur!=null);
                }
                ch=1;
                break;
            case 2: cur=table[hash(key)]; 
                pcur=cur;
                i=0; ch=0;
                do
                {
                    if(cur == null)
                    {
                        pcur->next = new line;
                        cur=pcur->next;
                        cur->key = key;
                        cur->adr = ++j;
                        cur->next=null;
                        printf("\tКлюч записан с %d попытки", i);
                        ch=1;
                    }
 
                    if(cur->key == null && pcur->next!=null)
                    {
                        cur->key = key;
                        cur->adr = ++j;
                        printf("\tКлюч записан с %d попытки", i);
                        ch=1;
                    }
 
                    if(cur!=null && cur->key!=key)
                    {
                        pcur=cur;
                        cur=cur->next;
                    }
 
                    i++;
                }
                while(!ch);
                break;
            case 3: i=0; ch=0;
                cur = table[hash(key)];
                do
                {
                    if(cur->key == key || cur == null)
                        ch=1;
                    i++;
                }
                while(!ch);
                if(cur->key == key)
                    printf("Ключ найден с %d попытки: \nKey: %d; Adress: %d", i, cur->key, cur->adr);
                else
                    ptintf("Ключ не найден!");
                break;
            default: ptintf("Ошибка ввода!");
    }
}
 
[size="1"][color="grey"][I]Добавлено через 1 минуту[/I][/color][/size]
а вот квадратичное опробирование: 
#inclide <stdio.h>
#inclide <conio.h>
 
#define n 25
 
int hash (int key)
{
    //тут пишешь любую хэш-функцию
    return key%21; //коллизия при ключах 22-25
}
 
void main ()
{
    int table[n][2];
    int i, j=0, ch=1, key;
    //очищение хэш-балицы
    for(i=0; i<n; i++)
    {
        table[i][0] = null; //место для ключа
        table[i][1] = null; //место для адреса в таблице
    }
    clrscr();
    while(ch != 0)
    {
        printf("\t\t\tМеню: выберите действие\n\t1 - высети хэш-таблицу.\n\t2 - новый ключ.\n\t3 Поиск. 0 Выход\n");
        scanf("%d", &ch);
        if(ch > 1)
        {
            printf("Введите ключ: ");
            scanf ("%d", &key);
        }
        switch(ch)
            case 1: printf("printf("[N]\tKey\tAdress", table[i][0], table[i][1])");  //вывод на экран хэш-таблицы
                for(i=0; i<n; n++)
                    printf("[%d]\t%d\t%d", i+1, table[i][0], table[i][1]);
                break;
            case 2: for(i=0; i<n*10; i++)                 //n*10 потому что после 250 проверок функции бессмысленно проверять дальше
                    if(table[hash(key)+i*3+i*i*7][0] != null) //проверка на свобоное место в таблице
                    {
                        table[hash(key)+i*3+i*i*7][0] = key;
                        table[hash(key)+i*3+i*i*7][1] = ++j;
                        printf("\tКлюч записан с %d попытки", i);
                    }
                if(i==n*10) ptintf("Таблица переполнена! Нужно произвести рехэширование!!!");
                break;
            case 3: for(i=0; i<n*10; i++)
                    if(table[hash(key)+i*3+i*i*7][0] != key)
                        printf("Ключ найден с %d попытки: \nKey: %d; Adress: %d", table[hash(key)+i*3+i*i*7][0], table[hash(key)+i*3+i*i*7][1]);
                if(i==n*10) ptintf("Ключ не найден!");
                break;
            default: ptintf("Ошибка ввода!");
    }
}

Новые блоги и статьи Все статьи Все блоги /
Управление зависимостями в Python с Poetry py-thonny 04.04.2025 Стандартный инструмент для установки пакетов в Python - pip - прекрасно справляется с базовыми сценариями: установил пакет командой pip install и используешь его. Но что произойдёт, когда разные. . .	Мониторинг с Prometheus в PHP Jason-Webb 04.04.2025 Prometheus выделяется среди других систем мониторинга своим подходом к сбору и хранению метрик. В отличие от New Relic, который использует агентный подход и отправляет данные во внешнее хранилище,. . .	Пакет Context в Golang: Управление потоками и ресурсами golander 04.04.2025 Работа с горутинами в Go часто напоминает управление непослушными детьми - они разбегаются кто куда, делают что хотят и не всегда завершаются вовремя. К счастью, в Go 1. 7 появился пакет context,. . .	Контейнеризация React приложений с Docker Reangularity 03.04.2025 Контейнеризация позволяет упаковать приложение со всеми его зависимостями в автономный контейнер, который можно запустить на любой платформе с установленным Docker. Это существенно упрощает процессы. . .	Свой попап в SwiftUI mobDevWorks 03.04.2025 SwiftUI, как декларативный фреймворк от Apple, предоставляет множество инструментов для создания пользовательских интерфейсов. В нашем распоряжении есть такие API как alerts, popovers, action sheets. . .
Антипаттерны микросервисной архитектуры ArchitectMsa 03.04.2025 Хорошо спроектированная микросервисная система может выдержать испытание временем, оставаясь гибкой, масштабируемой и устойчивой к большинству проблем. Такая архитектура обладает высоким уровнем. . .	std::mutex в C++: Советы и примеры использования bytestream 03.04.2025 std::mutex - это механизм взаимного исключения, который гарантирует, что критический участок кода выполняется только одним потоком в каждый момент времени. Это простое, но могущественное средство. . .	Не удержался от оценки концепции двигателя Стирлинга. Hrethgir 03.04.2025 Сколько не пытался - она выдавала правильные схемы, причём случайно рисовала горячие области в середине, холодные по краям, трубки с краёв в низ и магнит в соединяющей, но при этой выдавала описание. . .	Метод с двумя буферами (или double buffering) или ping-pong buffering Hrethgir 02.04.2025 Из ответов LM модели. Метод, который предполагает использование двух массивов для хранения промежуточных результатов сложения векторов, обычно применяется в сценариях, где необходимо минимизировать. . .	На любовном киберфронте Alexander-7 01.04.2025 Недавно на одном малоизвестном сайте знакомств мною заинтересовалась девушка: «Текст немного странный. Но, судя по адресу почты, иностранка», – подумал я. Поколебавшись пару суток, я ответил ей:. . .

@Aidana 0 / 0 / 0 Регистрация: 16.01.2016 Сообщений: 4

	Хэш-функции 15.11.2009, 12:59. Показов 4101. Ответов 1 Метки нет (Все метки) Хэш-функции и таблицы Задание 1. Придумайте некоторую хэш-функцию и вкратце проанализируйте ее, учитывая сложность подсчета и вероятности появления коллизий. 2. Используя Вашу хэш-функцию, реализуйте 2 подхода к построению хэш-таблиц с помощью цепочек и с открытой адресацией (к примеру, линейное или квадратичное пробирование из книги Кормена, глава «Хэш-таблицы»). 3. Для каждого из 2-х подходов оцените время (сложность, т.е. количество сравнений элементов) для поиска случайного числа х (предполагайте, что Ваши ключи должны быть большими или используйте строки, так как для малых значений существует прямой метод индексации). В итоге, в среднем случае сложность занимает O(1+eps) времени, но это зависит от Вашей хэш-функции и наша цель проверить данное утверждение. 0