1 / 1 / 0
Регистрация: 05.04.2012
Сообщений: 22
1

Хеширование,вычисление ключа методом вычисления адреса

15.10.2012, 16:06. Показов 5361. Ответов 9
Метки нет (Все метки)

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

не могу реализовать последний пункт. Если кто-то поможет,буду благодарен!
Задание : Поиск заданного ключа в исходном отсортированном массиве: необходимо расположить элементы исходного массива в новом массиве, используя метод хеширования, и выполнить в нем поиск заданного ключа методом вычисления адреса.
========================================================================
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
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#include "casual.h" // здесь лежит прототип функций.
 
void initArray(int *Arr, int ArrSize) // Randomize
{
    for (int i = 0; i < ArrSize; i ++)
    { 
        Arr[i] = rand()%900+100;
        for(int j = 0; j < i; j++)
        {
            if(Arr[j] == Arr[i])
            {
                Arr[i] = rand()%900+100;
            }
        }
        cout << i <<"| "<< Arr[i] << endl;
    }
}
 
void barrierSearch(int *Arr, int size, int key) // Barrier Search
{
    setlocale(LC_ALL,"Russian");
    int j = 0; 
    int counter = 0;
    Arr[size+1] = key;
    while(true)
    {
        counter++;
        if(Arr[j] == key)
        {
            break;
        }
        j++;
    }
    if (j>size)
    {
        cout <<"Not Found: " << key << "\nСравнений:" << counter << endl;
        cout << "--------------------" << endl;
    }
    else
    {
        cout <<"Found: " << key << "\nСравнений:" << counter << endl;
        cout << "--------------------" << endl;
    }
}
 
void initBarrierSearch() {
    setlocale(LC_ALL,"Russian");
    int arrSize;
    int result = 0;
    int key;
 
    cout <<"Введите размерность массива: ";
    cin >> arrSize;
 
    int *arr=new int[arrSize];
    cout<< "" << endl;
 
    cout << "[1].Мануал ключ" << endl;
    cout << "[2].Автоматический ключ" << endl;
 
    cin >> result;
 
    if (result == 1) // Manual key.
    {
        cout<<"Исходный массив: "<< endl;
        cout<< "--------------------" <<endl;
        {
            initArray(arr,arrSize);
        }
        cout<< "--------------------" <<endl;
        {
            cout << "Введите ключ: " << endl;
            cin >> key;
            barrierSearch(arr,arrSize,key); 
        }
    }
    if (result == 2) // Random key. 
    {
        cout<<"Исходный массив: "<< endl; 
        cout<< "--------------------" <<endl;
        {
            initArray(arr,arrSize);
        }
        cout<< "--------------------" <<endl;
        { 
            cout << endl; 
            key = rand()%900+100;
            //cout << "Введите ключ: " << key << endl; 
            barrierSearch(arr,arrSize,key);
            system("pause");
            system("cls");
        }
    }
}
 
void BubbleSort(int *arr, int size) // Sorting Array
{
    int i,j,x;
    for (i=0;i<size;i++) 
    {
        for (j=size-1;j>i;j--) 
        { 
            if (arr[j-1]>arr[j]) 
            { 
                x=arr[j-1]; 
                arr[j-1]=arr[j]; 
                arr[j]=x;  
            } 
        }
    }
    for (i=0;i<size;i++)
    {
        cout << i << "|" <<arr[i] <<endl;
    }
}
 
void initHashingSearch()
{
    setlocale(LC_ALL,"Russian");
    int arrSize;
    int result = 0;
 
    cout <<"Введите размерность массива: ";
    cin >> arrSize;
 
    int *arr=new int[arrSize];
    cout<< "" << endl;
 
    cout << "[1].Неотсортир. массив" << endl;
 
    cin >> result;
 
    if (result == 1) // Manual key.
    {
        cout<<"Исходный массив: "<< endl;
        cout<< "--------------------" <<endl;  
        {
            initArray(arr,arrSize);
        }
        cout<< "--------------------" <<endl;
        {
            cout<<"Отсортир. массив: "<< endl;
            cout<< "--------------------" <<endl;
            BubbleSort(arr,arrSize);
            //hashingSearch(arr,arrSize);
        }
    }
}
 
void hashingSearch(int *arr, int arrSize) // Вот здесь трабл. Не могу реализовать. Не понимаю....
{
    int key;
    int i,j,z = 0;
 
 
}
void main ()
{
    int choice = 0;
    while  (true) {
        setlocale(LC_ALL,"Russian");
        cout << "--------MENU--------: " << endl;
        cout << "[1]Поиск ключа (посл. с барьером)"<<endl;
        cout << "[2]Хеш поиск (+ коллизия)"<<endl;
        cout << "[3]Выход"<<endl;
        cin >> choice;
 
        switch (choice) {
            case 1 : initBarrierSearch(); break;
            case 2 : initHashingSearch(); break;
            case 3 : return;
        }
 
    }
}

Буду благодарен !!! +++
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
15.10.2012, 16:06
Ответы с готовыми решениями:

поиск методом вычисления адреса
Дали лабу. в которой нужно найти допустим число 1001(масив) методом вычисления адреса. А лекций...

Выполнить сортировку одномерного массива X(100) методом вычисления адреса
Разобрался наконец с заданием...оно звучит так как в заголовке...сортировка вычислением адреса

Хеширование: реализовать пользовательский поиск ключа
Всем привет! Ребята очень нуждаюсь в вашей помощи. Есть хеш функция: #include &lt;iostream&gt;...

Хеширование методом цепочек
При хешировании с цепочками списки элементов с данным хеш-значением будут упорядоченными. Как этот...

9
1 / 1 / 0
Регистрация: 01.12.2014
Сообщений: 142
11.02.2018, 02:03 2
Вот и у меня та же задача... Возрождаю тему.. Подскажите кто знает как реализовать Хеширование,вычисление ключа методом вычисления адреса
Спасибо
0
║XLR8║
1212 / 909 / 270
Регистрация: 25.07.2009
Сообщений: 4,361
Записей в блоге: 5
11.02.2018, 02:39 3
Kultanen, создай лучше свою тему.

Цитата Сообщение от Kultanen Посмотреть сообщение
как реализовать Хеширование,вычисление ключа методом вычисления адреса
А ты теорию дашь? Для тех кто не вкурсе что такое "вычисление ключа методом вычисления адреса"
1
1 / 1 / 0
Регистрация: 01.12.2014
Сообщений: 142
11.02.2018, 14:45 4
Цитата Сообщение от outoftime Посмотреть сообщение
Kultanen, создай лучше свою тему.
Зачем плодить одинаковые темы?
Цитата Сообщение от outoftime Посмотреть сообщение
как реализовать Хеширование,вычисление ключа методом вычисления адреса
А ты теорию дашь? Для тех кто не вкурсе что такое "вычисление ключа методом вычисления адреса"
Вот теория http://rsdn.org/article/alg/bintree/hash.xml#ETF
и вот теория http://kvodo.ru/hesh-funktsii.html
я просто не совсем понимаю. У меня в задании нужно вывести не отсортированный массив случайных чисел, затем этот же массив скопировать в другой массив, и расположить элементы исходного массива в новом массиве, используя метод хеширования, и выполнить в нем поиск заданного ключа методом вычисления адреса.
Допустим я выбрал хеш-функцию, вычисляющаю остаток от деления нацело вносимого ключа на число ячеек в массиве
А = х mod n;
где А – место расположения ключа в массиве (адрес),
х – ключ, помещаемый в массив;
n – количество элементов массива.
т.е. если у меня в исходном, не отсортированном массиве, 10 элементов (n=10), в цикле мне нужно брать каждый элемент(х), делить его по модулю на 10, и результат деления будет индексом/ключом (А) для элемента (х) в новом массиве ?
0
Комп_Оратор)
Эксперт по математике/физике
8950 / 4704 / 630
Регистрация: 04.12.2011
Сообщений: 14,003
Записей в блоге: 16
12.02.2018, 01:25 5
Цитата Сообщение от Kultanen Посмотреть сообщение
выполнить в нем поиск заданного ключа методом вычисления адреса
Это трудно понять потому, что кажется, что это можно понять. На самом деле те кто это придумал сами не понимают, что это такое, наверное.
Ключ, это элемент данных для поиска значения. В терминах хеш-таблиц/хеш-массивов:
- ключ находится путём хеширования (такого себе способа нахождения ключа, - поиск целого числа по данным значения, для которого он вычисляется);
- ключ связывается с индексом (обычно это целое положительное число, равное индексу) массива. Деление по модулю это простой способ выполнения данной процедуры.

Это значит, что хеш, ключ и адрес в Вашем случае, это одно и то же самое добро. Вычисление адреса по ключу хеша или хеширование ключа адреса или (вариантов размещения данных терминов много и далее представьте сами сколько можно написать ерунды), это то, что понять нельзя.
Вдобавок обычно, однозначного отображения данных на индексы нет и возникают группы коллизий. То есть, Ваша задача решается лишь, если все элементы данных имеют уникальные значения. Иначе их нельзя разместить в массиве непосредственно. В самом простом случае, ячейка такого массива содержит помимо элемента данных, указатель на таку же ячейку (то есть ячейка массива представляет собой структуру для одно-связного списка (!) ). В этом разе, разрешение коллизий называют "методом цепочек".
Обидно вот что. Когда такие сложные вещи как хеширование, предлагают изучать так топорно, то это свидетельствует о неуважительном отношении к материалу и учащимся. В предположении о том, что преподаватели, если их растормошить, обнаружат некое понимание самого материала.
1
outoftime
12.02.2018, 01:32
  #6

Не по теме:

IGPIGP, вот, то же хотел сказать, но знаний недостаточно чтобы сформулировать. О хешах знаю только асимптотику и что ключ должен быть хешируемым объектом.

0
Комп_Оратор)
Эксперт по математике/физике
8950 / 4704 / 630
Регистрация: 04.12.2011
Сообщений: 14,003
Записей в блоге: 16
12.02.2018, 02:18 7
Цитата Сообщение от outoftime Посмотреть сообщение
О хешах знаю только асимптотику и что ключ должен быть хешируемым объектом.
Я тоже знаю, что ничего не знаю.
Проблема хеширования состоит в том, что помимо скорости требуется высокая разрешающая способность. В самых общих формулировках для исчерпывающего представления, информация должна бы предоставляться в виде (для целого числа) :
val, min, max
то есть, к каждому значению ещё пара атрибутов границ. Тогда любое сложное поле (структура) может быть отображено на целое (без оверхеда). Тут есть по крайней мере две проблемы. Первая, - колоссальные размеры для массивов без коллизий (гарантирующих отсутствие повторов). Второе, - распухание данных и времени.
Третий вопрос - детальная изученность данных. А ведь при детальной изученности хешрование теряет ценность. Время доступа, учитывая потери на расчёт хеша, спорное преимущество перед деревом поиска. А найти предикат сравнения на хорошо изученных данных - не вопрос, а дело чести.
То есть хеширование, - палочка-выручалочка тогда, когда данные изучены плохо.
Иными словами, хорошо хешировать то, что хорошо изучено (известно). Но в этом случае оно уже проигрывает BST. То есть, изученные данные сравнимы и хешировать их просто не нужно. Философское (диалектическое), внутреннее противоречие.
0
1 / 1 / 0
Регистрация: 01.12.2014
Сообщений: 142
12.02.2018, 10:17 8
outoftime,
IGPIGP,
Господа, я благодарен вам за ваше мнение! Преподы - такие преподы, это правда Но лаба висит, а я всего лишь пытаюсь стать, более и менее, неплохим программистом Лекций по этой теме действительно мало, а то что есть в сети не всегда подходит.
Мне кажется, что на данном этапе я не совсем правильно понимаю "ху из ху" в моем задании.
Безусловно, я понимаю что есть массив, что есть его элемент, и что есть индекс этого элемента. Обычно, под понятием "ключ", в заданиях до этого, мы понимали некое число, введенное пользователем с клавиатуры(например), и этот "ключ", мы искали в наших массивах, перебирая индексы, сравнимая элементы с введенным пользователем "ключом" и тд. Ну вы понимаете. Но сдается мне, я не совсем понимаю что такое "ключ" в данном контексте...
В задании: взять не отсортированный массив рандомных целых чисел, и записать его в новый массив, отсортировав методом хеширования. Затем выполнить поиск в нем заданного ключа, методом вычисления адреса. Что подразумевается здесь под словом "ключ" ? То что хочет найти пользователь?
IGPIGP, Вы писали:
Цитата Сообщение от IGPIGP Посмотреть сообщение
Это значит, что хеш, ключ и адрес в Вашем случае, это одно и то же самое добро.
В моем случае я выбрал функцию хеширования, вычисляющаю остаток от деления нацело вносимого ключа на число ячеек в массиве
А = х mod n;
где А – место расположения ключа в массиве (адрес),
х – ключ, помещаемый в массив;
n – количество элементов массива.

создаю массив и заполняю рандомно:
C++
1
2
3
4
5
6
7
8
9
10
11
12
    int arrayAmount;
    cout << "Enter a size of array" << endl;
    cin >> arrayAmount;
    int *unsortArray = new int[arrayAmount];
    srand(time(NULL));
 
    for (int i = 0; i <= arrayAmount - 1; i++)
    {
        unsortArray[i] = rand() % 100;
        cout << unsortArray[i] << " ";
    }
    cout << endl;
далее создаю второй массив:
C++
1
2
3
4
5
6
7
8
9
10
11
12
   const int arr = arrayAmount;
    int *sortArray = new int[arr];
    //int key;
    //cout << "Enter key: " << endl;
    //cin >> key;
    for (int i = 0; i <= arrayAmount - 1; i++)
    {
        sortArray[i] = unsortArray[i] % arr;
        cout << unsortArray[i] << " ";
        cout << sortArray[i] << " ";
    }
    cout << endl;
тут я просто записываю в массив sortArray[i] в каждую его ячейку, значение равное unsortArray[i] % arr - каждый элемент первого, не отсортированного массива, деленное по модулю на размер массива...
В результате имеем например
первый не отсортированный массив = 14 63 78 35
второй, который должен быть отсортирован с помощью А = х mod n имеет значения 2 3 2 3.
внимание вопрос что я получил во втором массиве, ключи, элементы, индексы ???
Спасибо за участие!
0
║XLR8║
1212 / 909 / 270
Регистрация: 25.07.2009
Сообщений: 4,361
Записей в блоге: 5
12.02.2018, 13:37 9
Kultanen, http://evilcoderr.blogspot.com... ble-c.html может поможет
0
Комп_Оратор)
Эксперт по математике/физике
8950 / 4704 / 630
Регистрация: 04.12.2011
Сообщений: 14,003
Записей в блоге: 16
12.02.2018, 21:25 10
Цитата Сообщение от Kultanen Посмотреть сообщение
Обычно, под понятием "ключ", в заданиях до этого, мы понимали некое число, введенное пользователем с клавиатуры
Не имеет значения. Я понял что такое ключ задолго до того как мне доверили его во владение. Я тогда ещё читать не умел и воспринимал "Буратино", на слух. Ключ, это инструмент для достижения того, что имеет значение. Хотя, золотой ключ и сам по себе тоже имеет какое то значение. Как говорил учитель Йода "И всегда двое их". То есть - пара "ключ-значение" это взаимоопределяющие понятия.
Хеширование, это отображение множества элементов данных на целые числа. Тут больше подошло бы слово "нумерация". А вот попытка распределения по линейной структуре с целью минимизации (равномерного распределения по группам) коллизий, это и есть "размазывание", то есть hashing.
Есть простая задачка подсчёта частоты встречаемости символов в тексте. Там создают массив в котором размер равен количеству возможных char. Инициализируют нулями. Потом пробегая посимвольно текст, каждый символ приводят к целому и увеличивают значение массива по данному индексу. Тут сам символ, уже является собственным хешем и адресом в массиве-счётчике. По-этому он и является ключом доступа к данным (подсчитанной частоте). Это очень простой и логичный пример связи элемента данных с размещением связанных с ним данных как пара ключ-значение, в последовательной структуре. Ключ определяет положение (индекс).
Для структур данных, в которых множество полей всё не намного сложнее. На первый взгляд по крайней мере. Тут важны две операции. Поиск отображения и поиск места в массиве. Причём первая зависит от второй, так как конечная цель получить равномерно распределённые корзины коллизий и компактный массив указывающих на корзины ссылок. Остальное - читайте. Или кладите задание и свои наработки. Может кто-то поможет.

Добавлено через 23 минуты
Kultanen, и вот ещё что. Хешировать размещение одного целого массива в другом это значит делать бессмысленную работу. Ёе нельзя понять именно по причине её бессмысленности. Ведь для поиска числа 123 например, вам нужен будет ключ 123 который вы скормите хешфункции (деление по модулю в вашем разе) и получите индекс (адрес) где может быть (если нет коллизий в этом узле) получите 123. Как говорил кот Матроскин "Чтобы продать что-то ненужное, нужно сначала купить что-то ненужное".
Смысл хеширования в отображении сложных данных (которые сами по себе не есть целые числа) на целые числа. А потом (если не одновременно с первым) отображение данного множества на индексы массива ячеек корзинок.
Одна из самостоятельных задач - хеширование строк. Можете попробовать. Тогда хеш-таки будет ключом, а не и ключом и значением.
0
12.02.2018, 21:25
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.02.2018, 21:25
Помогаю со студенческими работами здесь

Хеширование таблицы методом деления
Разработать процедуру хеширования массива записей методом деления, в которой предполагается частое...

Создание ключа методом RegCreateKeyEx()
Здравствуйте! Ребята подскажите по такому вопросу. Пытаюсь создать ключ в реестре в разделе...

Использование GetHashCode() объекта-ключа в методе вычисления хеша
Пусть у меня есть хештаблица с методом разрешения коллизий через цепочки (которые являются...

Вычисление определенного интеграла методом центральных прямоугольников, и методом трапеции
Здравствуйте, помогите написать прогу для вычисление определенного интеграла методом трапеций и...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru