Advertisement
Guest User

hash with DH

a guest
Nov 20th, 2017
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.34 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cstdlib>
  3.  
  4. #define EMPTY 0
  5. #define EMPTY_DEL 1
  6. #define FULL 2
  7.  
  8. int hash(int value) {
  9.     return value % 11;
  10. }
  11.  
  12. int hash2(int value) {
  13.     return 1 + value % 10;
  14. }
  15.  
  16. //ubacuje *value* u hash tabelu
  17. void add(int *table, int *table_indicators, int size, int value) {
  18.     if(hash(value) >= size || hash(value) < 0) {
  19.         printf("SOMETHING VERY WRONG\n");
  20.         exit(1);
  21.     }
  22.  
  23.     int idx = hash(value);
  24.    
  25.     for(int i=0; i<size; i++) {
  26.         int idx2 = (idx+i*hash2(value))%size;
  27.         if(table_indicators[idx2] == EMPTY || table_indicators[idx2] == EMPTY_DEL) {
  28.             table[idx2] = value;
  29.             table_indicators[idx2] = FULL;
  30.             return;
  31.         }
  32.     }
  33.  
  34.     printf("NO MORE SPACE\n");
  35.     exit(1);
  36. }
  37.  
  38. //vraca index iz hash tabele za vrednost *value*
  39. int find(int *table, int *table_indicators, int size, int value) {
  40.     if(hash(value) >= size || hash(value) < 0) {
  41.         printf("SOMETHING VERY WRONG\n");
  42.         exit(1);
  43.     }
  44.  
  45.     int idx = hash(value);
  46.     for(int i=0; i<size; i++) {
  47.         int idx2 = (idx+i*hash2(value))%size;
  48.         if(table_indicators[idx2] == EMPTY) {
  49.             printf("NOT FOUND\n");
  50.             exit(1);
  51.         }
  52.         if(table_indicators[idx2] == EMPTY_DEL)
  53.             continue;
  54.         if(table[idx2] == value)
  55.             return idx2;
  56.     }
  57.  
  58.     printf("NOT FOUND\n");
  59.     exit(1);
  60. }
  61.  
  62. //brise element iz hash tabele po vrednosti *value*
  63. void remove(int *table, int *table_indicators, int size, int value) {
  64.     int idx = find(table, table_indicators, size, value);
  65.     table_indicators[idx] = EMPTY_DEL;
  66.     return;
  67. }
  68.  
  69. int main(int argc, char **argv) {
  70.     int size = 11;
  71.    
  72.     int *table_indicators = (int*)malloc(sizeof(int) * size);
  73.     for(int i=0; i<size; i++)
  74.         table_indicators[i] = EMPTY;
  75.  
  76.     int *table = (int*)malloc(sizeof(int) * size);
  77.  
  78.     for(int i=1; i<argc; i++) {
  79.         add(table, table_indicators, size,
  80.             strtol(argv[i], NULL, 10));
  81.     }
  82.  
  83.     for(int i=0; i<size; i++)
  84.         if(table_indicators[i] == FULL)
  85.             printf("%d : %d\n", i, table[i]);
  86.  
  87.     printf("Remove?\n");
  88.     int input = -1;
  89.     while(input != 0) {
  90.         scanf("%d", &input);
  91.         if(input == 0) break;
  92.         remove(table, table_indicators, size, input);
  93.     }
  94.  
  95.     printf("Add?\n");
  96.     input = -1;
  97.     while(input != 0) {
  98.         scanf("%d", &input);
  99.         if(input == 0) break;
  100.         add(table, table_indicators, size, input);
  101.     }
  102.  
  103.     for(int i=0; i<size; i++)
  104.         if(table_indicators[i] == FULL)
  105.             printf("%d : %d\n", i, table[i]);
  106.  
  107.     free(table);
  108.     free(table_indicators);
  109. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement