powered by simpleCommunicator - 2.0.59     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Delphi [игнор отключен] [закрыт для гостей] / Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
25 сообщений из 62, страница 2 из 3
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
    #40057876
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov,

Да.
...
Рейтинг: 0 / 0
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
    #40057877
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Kazantsev Alexey,

там еще про заголовки непонятка
...
Рейтинг: 0 / 0
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
    #40057879
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov
вставляем 3 раза по 3 дубликата

Нет, вставляются 100K уникальных ключей 3 раза.

Aleksandr Sharahov
непонятно как выглядят заголовки процедур?

Не понял...
...
Рейтинг: 0 / 0
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
    #40057881
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Kazantsev Alexey,

по идее хеш-таблица не содержит дубликатов,
поэтому возникают 2 вопроса:
- есть ли возможность хранить дубликаты в твоей таблице?
- если есть, то каков API?
...
Рейтинг: 0 / 0
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
    #40057885
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov,

Да, хранить дубликаты можно.
Код: pascal
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.
//
function TPtrSet.GetPtrHash(APtr : Pointer) : THash;
begin

 Cardinal(Result) := {PtrUInt(APtr);{ Shr 4;//}BJ32BitFAHash(PtrUInt(APtr));

end;
//

//
procedure TPtrSet.Add(APtr : Pointer);
var

 ctx : TPtrSet.TSearchContext;

begin

 EnsureGrowth;

 if FindFirst(GetPtrHash(APtr), ctx) then
  repeat
  until not FindNext(ctx);

 RegisterItem(ctx){$IF SizeOf(Pointer) = 8}

                   .Data := PtrUInt(APtr) Shr 32;

                  {$IFEND};

end;
//

//
function TPtrSet.Remove(APtr : Pointer) : Boolean;
var

 ctx  : TPtrSet.TSearchContext;
 ictx : TPtrSet.TSearchContext;

 {$IF SizeOf(Pointer) = 8}

  data : Cardinal;

 {$IFEND}

begin

 Result := False;

 ictx.Items := nil;

 if FindFirst(GetPtrHash(APtr), ctx) then
  begin

   {$IF SizeOf(Pointer) = 4}

    ictx := ctx;

    if FindNext(ctx) then
     Result := true;

   {$ELSEIF SizeOf(Pointer) = 8}

    data := PtrUInt(APtr) Shr 32;

    if ctx.Item.Data = data then
     begin

      ictx := ctx;

      while FindNext(ctx) do
       if ctx.Item.Data = data then
        begin

         Result := true;
         break;

        end;

     end;

   {$ELSE}

    {$MESSAGE ERROR 'Unknown situation'}

   {$IFEND}

  end;

 if Assigned(ictx.Items) then
  UnregisterItem(ictx);

end;
//

//
function TPtrSet.Contains(APtr : Pointer) : Boolean;
var

 ctx : TPtrSet.TSearchContext;

begin

 result := False;

 if FindFirst(GetPtrHash(APtr), ctx) then

  {$IF SizeOf(Pointer) = 4}

   Result := True;

  {$ELSEIF SizeOf(Pointer) = 8}

   repeat

    if ctx.Item.Data = PtrUInt(APtr) Shr 32 then
     begin

      Result := True;

      Break;

     end;

   until not FindNext(ctx);

  {$ELSE}

   {$MESSAGE ERROR 'Unknown situation'}

  {$IFEND}

end;
//



Удаление делается по условию топикстартера, т.е. функция удаления возвращает булево в зависимости от наличия в таблице дубликатов ключа.
...
Рейтинг: 0 / 0
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
    #40057887
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Kazantsev Alexey,

понятно.

На мой взгляд, как-то костыльно хранить дубликаты с доступом только к первому,
то топикстартеру видней, конечно.
...
Рейтинг: 0 / 0
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
    #40057894
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov,

Нет смысла делать доступ к каждому из дубликатов, когда нет ассоциированных данных.
...
Рейтинг: 0 / 0
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
    #40057897
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Kazantsev Alexey,

в данном случае - да (дубликаты просто выполняют роль счетчика),
но в общем случае это не так.
...
Рейтинг: 0 / 0
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
    #40057906
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
О! Нашёл ошибку в удалении
...
Рейтинг: 0 / 0
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
    #40057971
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Kazantsev Alexey,

ну а если добавить все "красивости": KeyNotify, ValueNotify (с виртуальностью и с поддержкой OnKeyNotify OnValueNotify естественно), стандартный IComparer<T> а не статик функции.
взять простые типы вроде Integer, взять данные без существенных коллизий (ну хоть последовательно от 1 до млн)

и какая будет разница?
...
Рейтинг: 0 / 0
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
    #40057989
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan),

Дефолтный словарь <integer, integer>, 1M элементов вставка: 221.
Таблица с робингудом повторяющая обес словаря с виртуализованными вызовами нотификаций и дефолтным компарером: 154. Если увеличить фактор заполнения таблицы до 0.97, то скорость снижается до: 207, но и расход памяти сокращается в 2 раза.
...
Рейтинг: 0 / 0
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
    #40058001
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Коллеги
Мы так и не ответили на вопрос, почему плохая хеш-функция, дающая большое количество коллизий, в итоге даёт многократный прирост
...
Рейтинг: 0 / 0
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
    #40058004
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOU,

Прирост даёт, как раз, функция не имеющая коллизий (даже в 64-битном тесте все указатели не выходят за пределы 32 бит).
...
Рейтинг: 0 / 0
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
    #40058006
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Kazantsev Alexey,

BJ32BitFAHash даёт хороший результат
Но NativeUInt(P) and ACapacityMask работает в полтора раза быстрее

Посмотри вот это сообщение 22301081

Для тех, кто пропустил
Эксперименты с архивом hash_table_2.zip, который указан в 22301038
...
Рейтинг: 0 / 0
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
    #40058008
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOU
Но NativeUInt(P) and ACapacityMask работает в полтора раза быстрее

Я об этом и говорю. NativeUInt(P) - не имеет коллизий в твоём тесте.
...
Рейтинг: 0 / 0
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
    #40058013
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Kazantsev Alexey,

На 32 битах гранулярность указателей 8, на 64 - вообще 16
Это значит, что для всех указателей как минимум 3 младших бита равны нулю
Это значит, что NativeUInt(P) даёт пустоты в 7 пунктов, а, следовательно, огромное число коллизий
...
Рейтинг: 0 / 0
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
    #40058020
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOU,

Это не коллизии хеш-функции. Это даже не коллизии входов в таблицу, это ухудшение распределения.

Вот распределение на робингуде при проекции указателя на хеш (300K элементов, уникальных 100K):
...
Рейтинг: 0 / 0
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
    #40058021
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
А вот так выглядит распределение на робингуде при проекции и сдвиге:
...
Рейтинг: 0 / 0
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
    #40058022
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOU
...огромное число коллизий


а после каждого слота с коллизиями - огромное количество свободных слотов, куда они прекрасно лягут
...
Рейтинг: 0 / 0
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
    #40058025
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Кстати, прямая проекция будет страдать от большого количества дубликатов сильнее, чем использование хеш-функции.
...
Рейтинг: 0 / 0
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
    #40058028
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov,

Ну с таким же успехом можно просто возвращать 0
Тогда они ещё лучше лягут
...
Рейтинг: 0 / 0
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
    #40058029
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOU,

вот же меня опять угораздило, ушел
...
Рейтинг: 0 / 0
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
    #40058030
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov,
...
Рейтинг: 0 / 0
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
    #40058110
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Kazantsev Alexey
kealon(Ruslan),

Дефолтный словарь <integer, integer>, 1M элементов вставка: 221.
Таблица с робингудом повторяющая обес словаря с виртуализованными вызовами нотификаций и дефолтным компарером: 154. Если увеличить фактор заполнения таблицы до 0.97, то скорость снижается до: 207, но и расход памяти сокращается в 2 раза.
хм,нашёл описание - это ж мой вариант с отсортированными значениями, такой вариант действительно будет не хуже, однако он уже таблицу хэшей срезал.
...
Рейтинг: 0 / 0
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
    #40058111
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOU
Kazantsev Alexey,

На 32 битах гранулярность указателей 8, на 64 - вообще 16
Это значит, что для всех указателей как минимум 3 младших бита равны нулю
Это значит, что NativeUInt(P) даёт пустоты в 7 пунктов, а, следовательно, огромное число коллизий


SOFT FOR YOU
тут вот вполне сносное объяснение твоему вопросу
авторСхемы открытой адресации также предъявляют более жесткие требования к хэш-функции: помимо более равномерного распределения ключей по сегментам, функция также должна минимизировать кластеризацию последовательных хэш-значений в порядке проверки.
как раз то, что я тебе писал в 22301251

ещё у майла интересная статейка была
...
Рейтинг: 0 / 0
25 сообщений из 62, страница 2 из 3
Форумы / Delphi [игнор отключен] [закрыт для гостей] / Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]