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

хеш-функция, линейное опробование - C++

Восстановить пароль Регистрация
 
\\Olka
 Аватар для \\Olka
0 / 0 / 0
Регистрация: 05.09.2011
Сообщений: 10
26.10.2013, 17:52     хеш-функция, линейное опробование #1
Привет всем кто кликнул эту тему!)
Прошу помочь тех кто хорошо понимает хеш-функции. Используется функция:
h(K) = K mod M, где К — числовая характеристика идентификатора, М — размер таблицы в строках.Для разрешения коллизий использовать схему линейного опробования, согласно которой, если строчка h(K) занята другим идентификатором, то поиск свободной строчки производится в отроках h(K) – 1, h(K) – 2, …, 0, M – 1, M – 2, …, h(K) + 1, (h(K) < M).

Объясните пожалуйста как действует заполнение таблицы

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
#include "stdafx.h"
#include <iostream>
#include <fstream>
using namespace std;
 
typedef int T;  // тип элементов
typedef int hashTableIndex;// индекс в хеш-таблице
int hashTableSize;
T *hashTable;
bool *used;
 
hashTableIndex myhash(T data);
void insertData(T data);
void deleteData(T data);
bool findData (T data);
int dist (hashTableIndex a,hashTableIndex b);
 
int _tmain(int argc, _TCHAR* argv[]){
  int i, *a, maxnum;
  cout << "Enter the number of elements [maxnum] : ";
  cin >> maxnum;
    cout << "Enter the size of the hash table [hashTableSize] : ";
  cin >> hashTableSize;
  a = new int[maxnum];
  hashTable = new T[hashTableSize];
  used = new bool[hashTableSize];
  for (i = 0; i < hashTableSize; i++){
    hashTable[i] = 0;
    used[i] = false;
  }
  // генерация массива
  for (i = 0; i < maxnum; i++)
    a[i] = rand();
  // заполнение хеш-таблицы элементами массива
  for (i = 0; i < maxnum; i++)
    insertData(a[i]);
  // поиск элементов массива по хеш-таблице
  for (i = maxnum-1; i >= 0; i--) 
    findData(a[i]);
  // вывод элементов массива в файл List.txt
  ofstream out("List.txt");
  for (i = 0; i < maxnum; i++){
    out << a[i];
    if ( i < maxnum - 1 ) out << "\t";
  }
  out.close();
  // сохранение хеш-таблицы в файл HashTable.txt
  out.open("HashTable.txt");
  for (i = 0; i < hashTableSize; i++){
    out << i << "  :  " << used[i] << " : " << hashTable[i] << endl;
  }
  out.close();
  // очистка хеш-таблицы
  for (i = maxnum-1; i >= 0; i--) {
    deleteData(a[i]);
  }
  system("pause");
  return 0;
}
 
// хеш-функция размещения величины
hashTableIndex myhash(T data) {
    return (data % hashTableSize);
}
 
// функция поиска местоположения и вставки величины в таблицу
void insertData(T data) {
  hashTableIndex bucket;
    bucket = myhash(data);
  while  ( used[bucket] && hashTable[bucket] != data)
    bucket = (bucket + 1) % hashTableSize;
  if ( !used[bucket] ) {
    used[bucket] = true;
    hashTable[bucket] = data;
  }
}
 
// функция поиска величины, равной data
bool findData (T data) {
  hashTableIndex bucket;
  bucket = myhash(data);
  while ( used[bucket] && hashTable[bucket] != data )
    bucket = (bucket + 1) % hashTableSize;
  return used[bucket] && hashTable[bucket] == data;
}
 
//функция удаления величины из таблицы
void deleteData(T data){
  int bucket, gap;
  bucket = myhash(data);
  while ( used[bucket] && hashTable[bucket] != data )
    bucket = (bucket + 1) % hashTableSize;
  if ( used[bucket] && hashTable[bucket] == data ){
    used[bucket] = false;
    gap = bucket;
    bucket = (bucket + 1) % hashTableSize;
    while ( used[bucket] ){
      if ( bucket == myhash(hashTable[bucket]) )
        bucket = (bucket + 1) % hashTableSize;
      else if ( dist(myhash(hashTable[bucket]),bucket) < dist(gap,bucket) )
        bucket = (bucket + 1) % hashTableSize;
      else {
        used[gap] = true;
        hashTable[gap] = hashTable[bucket];
        used[bucket] = false;
        gap = bucket;
        bucket++;
      }
    }
  }
}
 
// функция вычисления расстояние от a до b (по часовой стрелке, слева направо) 
int dist (hashTableIndex a,hashTableIndex b){
  return (b - a + hashTableSize) % hashTableSize;
}
В книжке написано что линейное опробование сводится к последовательному перебору сегментов таблицы с некоторым фиксированным шагом: адрес=h(x)+ci,где i – номер попытки разрешить коллизию;c – константа, определяющая шаг перебора. А в этой программе непонятно как оно происходит
Например для 5 элементов (41,18467,6334,26500,19169) в таблицу из 6 строк:
0 : 1 : 18467
1 : 1 : 26500
2 : 1 : 19169
3 : 0 : 0
4 : 1 : 6334
5 : 1 : 41
Почему 41 не в начале таблицы и другие элементы не пойму как выбирают местоположение, помогите кто понимает этот метод
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.10.2013, 17:52     хеш-функция, линейное опробование
Посмотрите здесь:

Хеш-функция, двойное хеширование C++
C++ Шаблоны. Хеш-функция
Хеш функция C++
C++ Метод открытого хеширования и хеш-функция, основанная на методе деления с остатком
C++ Объясните как работает хеш-функция
Хеш функция C++
Создать производные классы линейное уравнение и квадратное уравнение, в которых данная функция переопределена C++
C++ Перегруженная функция (линейное и квадратное уравнение)

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

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

Текущее время: 17:54. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru