2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 HashSet с открытой адресацией неограниченного размера
Сообщение08.12.2017, 16:03 
Требуется реализовать HashSet с открытой адресацией, в который можно добавлять неограниченное кол-во элементов.
Язык программирования: Java.
Максимальный размер массива 2_147_483_647
Максимальное значение hashCode тоже 2_147_483_647

При кол-ве элементов много меньшем максимального размера массива я определил следующую реализацию:
Для определения размера таблицы используем статическое множество простых чисел:
$Node[] table $ - сама таблица с объектами
Node - просто обертка для T (Дженерик)
$tableSize = \{101, 211, 421, 853, 1709, 3433, 7057, 16651, 33391, 65713, 131071, 262419, 524287, 1046527\}$

При инициализации используем tableSize[0]
Далее при добавлении элементов, определяем коэффициент заполненности,
если он больше 0.7, то увеличиваем таблицу в ~2 раза (то есть берем следующее число из tableSize)
и копируем(добавляем заново) все из старого массива.

Хэш-функция проста
$hash(Object\ o) = hashCode(o) \ mod \ table.size$

Далее встают два вопроса:
Что делать, когда у двух объектов одинаковые hash
И как добиться неограниченности размера.

 
 
 
 Re: HashSet с открытой адресацией неограниченного размера
Сообщение08.12.2017, 16:10 
Аватара пользователя
hiraev в сообщении #1273161 писал(а):
Что делать, когда у двух объектов одинаковые hash
Вы знаете определение открытой адресации?

 
 
 
 Re: HashSet с открытой адресацией неограниченного размера
Сообщение08.12.2017, 16:18 
Да. Все элементы помещаются в одну таблицу. Для борьбы с коллизиями используется hash - функция специального вида
hash(k, i) - где k - это объект (в моем случае hashCode объекта), а i - это номер попытки вставить объекта в пустую ячейку.

-- 08.12.2017, 16:31 --

Для отрытой адресации я буду использовать следующую хэш-функцию
$hash(k,i) = (h_1(k)+ih_2(k))\ mod\ m$
$h_1(k)=k\ mod\ m$
$h_2(k)=1 + (k\ mod\ m-1)$
k - hashCode объекта
m - размер массива (простое число)
i - номер попытки вставки

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group