Меню
Что нового?

Хеши

hell0w0rd

hell0w0rd

Продвинутый новичок
Я тут с хешами пытаюсь разобраться. Написал реализацию, где таблицей - является массив. А что правильно использовать в качестве таблицы? И что используется в php?
 

Mols

Новичок
шото не пойму. Если уже до стд дело дошло то почему сразу не юзать std::unordered_map ?
 
hell0w0rd

hell0w0rd

Продвинутый новичок
Mols, ну блин, хочется разобраться как оно работает. С связными списками все понятно - можно и stl-ные юзать
 

Mols

Новичок
WMix, ну дык это и есть коллизия.
Есть разные механизмы их разрешения.
 
hell0w0rd

hell0w0rd

Продвинутый новичок
Не, мой вопрос касается алгоритма еще до работы с коллизиями, а точнее того как хранить эти структуры, которые разрешают коллизии. неужели в простом массиве - вот в чем мое удивление)
 
WMix

WMix

герр M:)ller
Партнер клуба
2 поинтера на ключ и значение? а основа это поинтер на данную структуру.
те вычислил индекс структуры от ключика, вышел по поинтеру на записанный ключик, если не коллизия, пошел по алгоритму пойска следующего
 
Последнее редактирование:

Mols

Новичок
hell0w0rd, Вопрос какой-то сумбурный.
Но по сути гарантировать константное время поиска может только арифметика указателя в памяти.
Поэтому обьекты хранят именно в массиве или структурах подобных массивам.
Чтобы при поиске по индексу работала арифметика указателей + развязка коллизий
Ну если например массив большой.
Тогда мы можем сделать двумерный массив.
Это избавит нас от необходимости выделять огромные блоки непрерывной памяти.
Но по сути в конце концов всё сведётся к "обычному массиву", (чтобы работала арифметика указателей.)
Поэтому хеши "кушают" больше памяти чем массивы.
Они сразу аллокируют некоторую область под указатели (ну или что там технология позволяет).
И зачастую многое остаётся не использованным (правда для людей привыкших к обьемам ПХП мира это "многое" стремится к нулю)))
Ну и вообще... хеш мапы вполне могут перестраивать внутренние хранилища при определённых условиях.
В общем не знаю зачем это пробовать сделать своими руками, но в прод я бы всё таки использовал стандартное решение.
(по крайней мере пока я не столкнулся с задачей, где мне бы пришлось делать свой хеш контейнер)
 
hell0w0rd

hell0w0rd

Продвинутый новичок
WMix, если правильно понял все что ты написал - это мне ясно.
Меня пугает что постоянно приходится перевыделять память, копировать тучу элементов.
@Mols, я не хочу в проде юзать свой контейнер. хочу просто написать в образовательных целях.

Вот допустим у нас хеш из 100 значений. Мы добавляем 101 - перезаписываем весь хеш? Получается запись в хеш O(n)?
 
WMix

WMix

герр M:)ller
Партнер клуба
тебе нужно перестроить только поинтеры на структуры это очень быстро
сейчас не помню но количество элементов всегда удобно 2^n держать и при перегрузке n+1 и чтото про золотое сечение кнута вспоминается этва 128
 

Mols

Новичок
Вот допустим у нас хеш из 100 значений. Мы добавляем 101 - перезаписываем весь хеш? Получается запись в хеш O(n)?
Нажмите для раскрытия...
hell0w0rd, не обязательно. Хотя в целом вполне можно сделать хеш, где в худшем случае будет такая сложность.
Представить себе можно так.
В нашем хеш контейнере есть хеш функция, которая даёт при обработке ключа число от 0 до 100 000.
При создании контейнера мы аллокируем массив под указатели размером 100 000 штук. (меньше мегабайта памяти надо)
Потом мы хотим вставить 100 элементов с разными ключами.
Что происходит?
Мы вычисляем нашей функцией хеш от ключа и получаем значение индекса гарантированно попадающее в наш массив.
Пусть нам везёт и все ключи после обработки нашей функцией дали разные индексы.
Мы тупо создаём обьекты и вставляем указатель в позицию индекса.
Тоже самое будет происходить и с 101 и с 102 и т.д.
До возникновения коллизий.
Ну а когда возникнут коллизии - вот тут и будет зависимость от механизма их разрешения.
З,Ы.
Но конечно можно и деревом хеш сделать.
Тут другие плюсы-минусы.
 
fixxxer

fixxxer

К.О.
Партнер клуба
hell0w0rd

hell0w0rd

Продвинутый новичок
fixxxer, спасибо, почитаю
Mols, какая-то не реальная ситуация, вы часто вставляете в php, или других языках в контейнеры данные не последовательно?
Можно сделать вот как, допустим хеш-функция возвращает long, берем MAX_LONG, создаем массив указателей на хеши размером 100, сам размер хеша равен MAX_LONG/100 и когда получаем результат от хеш-функции берем остаток от деления на 100, получаем смещение по первому массиву, остаток от деления на MAX_LONG/100 - смещение по второму массиву. Соответсвенно лишняя память будет выделена позже, ничего перезаписывать не надо
 

Mols

Новичок
Ну конечно это был просто пример.
Хотя мне вообще не понятно, что значит "последовательно" в случае с хеш?
Да и про многомерные массивы я тоже выше писал.
В общем, похоже, я потерял нить этой дискуссии.
 
WMix

WMix

герр M:)ller
Партнер клуба
PHP: 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct{
  char* key;
  char* val;
}el;

el*  el_new( char* key, char* val);

typedef struct{
  int size;
  int step;
  int count;
  el** data;
  int* keys;
}ht;


ht*  ht_new( int size );
ht*  ht_inc( ht* h );
ht*  ht_add( ht* h, char* key, char* val );
int  ht_idx( ht* h, char* key );
int  ht_has( ht* h, int idx );
int  ht_hsh( ht* h, char* key, int step);
char*  ht_get( ht* h, char* key );

el* el_new( char* key, char* val){
  el* e = ( el* )malloc ( sizeof( el ) );
  e->key = ( char* ) malloc( strlen( key ) * sizeof(char) );
  e->val = ( char* ) malloc( strlen( val ) * sizeof(char) );
  strcpy(e->key, key);
  strcpy(e->val, val);
  return e;
}

ht* ht_new( int size ){
  ht* h = (ht*) malloc ( sizeof(ht));
  h->size = size;
  h->step = 7;
  h->count = 0;
  h->data = (el**)malloc( h->size * sizeof( el* ) );
  h->keys = (int*)malloc( h->size * sizeof(int) );
}

ht* ht_inc( ht* h ){
  ht* nh = ht_new( h->size*2 );
  int i;
  for( i = 0; i < h->count; i++ ){
  int k = ht_idx( nh, h->data[ h->keys[i] ]->key );
  nh->keys[ i ] = k;
  nh->data[ k ] = h->data[ h->keys[i] ];
  nh->count++;
  }
  return nh;
}

int ht_has( ht* h, int idx ){
  int i;
  for( i = 0; i < h->count; i++ ) if( h->keys[i] == idx) return 1;
  return 0;
}

int ht_idx( ht* h, char* key ){
  int i, step = 0;
  do i = ht_hsh( h, key, step++ );
  while( ht_has( h, i ) );
  return i;
}

ht* ht_add( ht* h, char* key, char* val ){
  if(h->count == h->size ) h = ht_inc( h );
  int i = ht_idx( h, key );
  h->keys[ h->count ] = i;
  h->data[ i ] = el_new( key, val );
  h->count++;
  return h;
}

char* ht_get( ht* h, char* key ){
  int i, step = 0;
  do i = ht_hsh( h, key, step++ );
  while( strcmp(h->data[ i ]->key, key) != 0);
  return h->data[ i ]->val;
}

int ht_hsh( ht* h, char* key, int step){
  int sum = 0, i=0, max = strlen(key);
  for(; i<max; i++) sum += (int)key[i];
  return ( sum + step * h->step ) % h->size;
}


int main(){
  ht* h = ht_new(2);

  h = ht_add(h, "aaa","mama");
  h = ht_add(h, "bbb","papa");
  h = ht_add(h, "ccc","deda");
  h = ht_add(h, "aab","baba");

  printf("%s = %s\n","aaa",ht_get(h,"aaa"));
  printf("%s = %s\n","bbb",ht_get(h,"bbb"));
  printf("%s = %s\n","ccc",ht_get(h,"ccc"));
  printf("%s = %s\n","aab",ht_get(h,"aab"));
  return 0;
}
 
Войдите или зарегистрируйтесь для ответа.
Сверху