iLab/Hash.cpp at master · GreenSeal/iLab · GitHub

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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include "Node.cpp"

//#define N 1

typedef struct List_ List;

struct List_ {
    Node* head = NULL;
    int size;
};

int BaseOfData (List* Table);
int HashTable(unsigned long long tel_number, List* Table);
int HashFunction1 (unsigned long long tel_number);
int HashFunction2 (unsigned long long tel_number);
int HashFunction3 (unsigned long long tel_number);
int HashFunction4 (unsigned long long tel_number);
int HashFunction5 (unsigned long long tel_number);

const int SizeTable = 1000;
const int SizeNumber = 12;

int main() {
    srand(time(NULL));

    List* Table = new List [SizeTable];
    int i = 0;

    for(i = 0; i <= SizeTable-1; i++)
        Table[i].size = 0;

    BaseOfData(Table);

    FILE* Hash = NULL;
    Hash = fopen("Hash5.csv", "w");

    if (Hash == NULL)
        printf("File couldn't open\n");

    for (i = 0; i <= SizeTable-1; i++) {

        fprintf(Hash, "%d ; %d\n", i, Table[i].size);
        //printf("%d %d\n", i,  Table[i].size);
    }

    fclose(Hash);

	return 0;
}

int BaseOfData (List* Table) {

    int i = 0, j = 0;
    for (i = 0; i <= (SizeTable - 1)*100; i++) {

        unsigned long long tel_number = 0;

        for (j = 0; j <= SizeNumber - 2; j++)
            tel_number = tel_number*10 + rand()%10;                                                                                //Создаю Рандомный телефонный номер
            //printf("%llu ", tel_number);
            HashTable(tel_number, Table);
        }
    return 0;
    }

int HashTable(unsigned long long tel_number, List* Table) {

    int num = HashFunction5(tel_number);                                                                                        //Вычисляю номер, в который закинуть номер

    if (Table[num].head == NULL) {                                                                                              //Если еще нет узла под Listом, создаю
        Node* AddNewNode = Create(tel_number);
        Link(NULL, (Table + num) -> head, AddNewNode);
        Table[num].head = AddNewNode;
        Table[num].size++;
        return 0;
    }

        Node* buf = Table[num].head;

        while(buf != NULL) {                                                                                                       //Проверка на совпадение

            if (buf -> data == tel_number){
                //printf("Already add");
                return 0;
            }

            buf = buf -> next;
        }

        buf = Table[num].head;

        while(buf -> next != NULL)                                                                                                  //Запись в конец
            buf = buf -> next;

        Node *AddNewNode = Create(tel_number);
        Link(NULL, buf, AddNewNode);
        (Table[num].size)++;

    return 0;
}

int HashFunction1(unsigned long long tel_number) {                                                                                                   //Все в один

    int num = 0;
    return num;
}

int HashFunction2(unsigned long long tel_number) {                                                                                               // По первой цифре

    int num = tel_number/(pow(10, SizeNumber - 3));
    //printf("%llu  ", tel_number);
    return num;
}

int HashFunction3 (unsigned long long tel_number) {                                                                                             // По сумме цифр

    int sum = 0, buf = 0;
    int i = 0;
    for (i = 0; i <= SizeNumber - 2; i++) {                                                                                         // -2 из-за счёта с нуля и размера номера
        buf = tel_number%10;
        sum = sum + buf;
        tel_number = (tel_number - buf)/10;
    }

    return sum;
}

int HashFunction4 (unsigned long long tel_number) {                                                                                              //Побитовое смещение

    int val1 = (tel_number >> (SizeNumber - 2)) & 1u;
    int val2 = (tel_number >> 0) & 1u;
    if (val1 == 1)
        tel_number = tel_number | (1u << (SizeNumber - 2));
    if (val1 == 0)
        tel_number = tel_number & ~(1u << (SizeNumber - 2));
    if (val2 == 1)
        tel_number = tel_number | (1u);
    if (val2 == 0)
        tel_number = tel_number & ~(1u);

    return tel_number%SizeTable;
}

int HashFunction5 (unsigned long long tel_number) {                                                                                                 //Долден быть Пуассон

    unsigned long start = 7, sum = start, buf = 0;
    int i = 0;
    for(i = 0; i <= (SizeNumber - 2); i++) {
        //printf("%d  ", sum);
        buf = tel_number%10;
        sum = sum*2 + buf;
        tel_number = (tel_number - buf)/10;
    }

    return sum%SizeTable;
}