(См. Следующую версию.)
Следующая структура данных реализует набор на основе хэш-таблицы для int
ценности:
com.github.coderodde.util.IntHashSet
package com.github.coderodde.util;
/**
* This class implements a simple hash set for non-negative {@code int} values.
* It is used in the {@link com.github.coderodde.util.LinkedList} in order to
* keep track of nodes that are being pointed to by fingers.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Aug 29, 2021)
* @since 1.6 (Aug 29, 2021)
*/
class IntHashSet {
private static final int INITIAL_CAPACITY = 8;
private static final float MAXIMUM_LOAD_FACTOR = 0.75f;
static final class IntHashTableCollisionChainNode {
IntHashTableCollisionChainNode next;
int integer;
IntHashTableCollisionChainNode(
int integer,
IntHashTableCollisionChainNode next) {
this.integer = integer;
this.next = next;
}
@Override
public String toString() {
return "Chain node, integer = " + integer;
}
}
void add(int integer) {
if (contains(integer)) {
return;
}
size++;
if (shouldExpand())
expand();
final int targetCollisionChainIndex = integer & mask;
final IntHashTableCollisionChainNode newNode =
new IntHashTableCollisionChainNode(
integer,
table[targetCollisionChainIndex]);
newNode.next = table[targetCollisionChainIndex];
table[targetCollisionChainIndex] = newNode;
}
boolean contains(int integer) {
final int collisionChainIndex = integer & mask;
IntHashTableCollisionChainNode node = table[collisionChainIndex];
while (node != null) {
if (node.integer == integer) {
return true;
}
node = node.next;
}
return false;
}
void remove(int integer) {
if (!contains(integer)) {
return;
}
size--;
if (shouldContract())
contract();
final int targetCollisionChainIndex = integer & mask;
IntHashTableCollisionChainNode current =
table[targetCollisionChainIndex];
IntHashTableCollisionChainNode previous = null;
while (current != null) {
IntHashTableCollisionChainNode next = current.next;
if (current.integer == integer) {
if (previous == null) {
table[targetCollisionChainIndex] = next;
} else {
previous.next = next;
}
return;
}
previous = current;
current = next;
}
}
public void clear() {
size = 0;
table = new IntHashTableCollisionChainNode[INITIAL_CAPACITY];
mask = table.length - 1;
}
private IntHashTableCollisionChainNode[] table =
new IntHashTableCollisionChainNode[INITIAL_CAPACITY];
private int size = 0;
private int mask = INITIAL_CAPACITY - 1;
// Keep add(int) an amortized O(1)
private boolean shouldExpand() {
return size > table.length * MAXIMUM_LOAD_FACTOR;
}
// Keep remove(int) an amortized O(1)
private boolean shouldContract() {
if (table.length == INITIAL_CAPACITY) {
return false;
}
return MAXIMUM_LOAD_FACTOR * size * 4 < table.length;
}
private void expand() {
IntHashTableCollisionChainNode[] newTable =
new IntHashTableCollisionChainNode[table.length * 2];
rehash(newTable);
table = newTable;
mask = table.length - 1;
}
private void contract() {
IntHashTableCollisionChainNode[] newTable =
new IntHashTableCollisionChainNode[table.length / 4];
rehash(newTable);
table = newTable;
mask = table.length - 1;
}
private void rehash(IntHashTableCollisionChainNode[] newTable) {
for (IntHashTableCollisionChainNode node : table) {
while (node != null) {
final IntHashTableCollisionChainNode next = node.next;
final int rehashedIndex = rehash(node.integer, newTable);
node.next = newTable[rehashedIndex];
newTable[rehashedIndex] = node;
node = next;
}
}
}
private static int rehash(
int integer,
IntHashTableCollisionChainNode[] newTable) {
return integer & (newTable.length - 1);
}
}
com.github.coderodde.util.IntHashSetTest
package com.github.coderodde.util;
import java.util.Random;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
import org.junit.Before;
import org.junit.Test;
public class IntHashSetTest {
private final IntHashSet set = new IntHashSet();
@Before
public void beforeTest() {
set.clear();
}
@Test
public void add() {
for (int i = 0; i < 500; i++) {
set.add(i);
}
for (int i = 0; i < 500; i++) {
assertTrue(set.contains(i));
}
for (int i = 500; i < 1_000; i++) {
assertFalse(set.contains(i));
}
for (int i = 450; i < 550; i++) {
set.remove(i);
}
for (int i = 450; i < 1_000; i++) {
assertFalse(set.contains(i));
}
for (int i = 0; i < 450; i++) {
assertTrue(set.contains(i));
}
}
@Test
public void contains() {
set.add(10);
set.add(20);
set.add(30);
for (int i = 1; i < 40; i++) {
if (i % 10 == 0) {
assertTrue(set.contains(i));
} else {
assertFalse(set.contains(i));
}
}
}
@Test
public void remove() {
set.add(1);
set.add(2);
set.add(3);
set.add(4);
set.add(5);
set.remove(2);
set.remove(4);
set.add(2);
assertFalse(set.contains(4));
assertTrue(set.contains(1));
assertTrue(set.contains(2));
assertTrue(set.contains(3));
assertTrue(set.contains(5));
}
@Test
public void clear() {
for (int i = 0; i < 100; i++) {
set.add(i);
}
for (int i = 0; i < 100; i++) {
assertTrue(set.contains(i));
}
set.clear();
for (int i = 0; i < 100; i++) {
assertFalse(set.contains(i));
}
}
@Test
public void bruteForceAdd() {
long seed = System.currentTimeMillis();
System.out.println(
"--- IntHashSetTest.bruteForceAdd: seed = " + seed + " ---");
Random random = new Random(seed);
int[] data = new int[10_000];
for (int i = 0; i < data.length; i++) {
int datum = random.nextInt(5_000);
data[i] = datum;
set.add(datum);
}
for (int i = 0; i < data.length; i++) {
assertTrue(set.contains(data[i]));
}
}
@Test
public void bruteForceRemove() {
long seed = System.currentTimeMillis();
System.out.println(
"--- IntHashSetTest.bruteForceRemove: seed = " + seed + " ---");
Random random = new Random(seed);
int[] data = new int[10_000];
for (int i = 0; i < data.length; i++) {
int datum = random.nextInt(5_000);
data[i] = datum;
set.add(datum);
}
shuffle(data, random);
for (int i = 0; i < data.length; i++) {
int datum = data[i];
if (set.contains(datum)) {
set.remove(datum);
}
assertFalse(set.contains(datum));
}
}
private static void shuffle(int[] data, Random random) {
for (int i = data.length - 1; i > 0; --i) {
final int j = random.nextInt(i + 1);
swap(data, i, j);
}
}
private static void swap(int[] data, int i, int j) {
int tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
}
Запрос на критику
Пожалуйста, расскажите мне все, что придет в голову! ^^
5 ответов
Ошибка: массив слишком сильно сжимается
Логика в shouldContract
похоже, он предназначен для предотвращения уменьшения размера ниже INITIAL_CAPACITY
, но этого не происходит. Например, предположим, что текущий размер таблицы равен 16, тогда table.length == INITIAL_CAPACITY
ложно и MAXIMUM_LOAD_FACTOR * size * 4 < table.length
может быть истинным, поэтому выполняется изменение размера, и новый размер равен 4. Затем table.length == INITIAL_CAPACITY
является все еще ложь, а также MAXIMUM_LOAD_FACTOR * size * 4 < table.length
снова может быть истинным, если будет удалено больше элементов, и следующий размер будет равен 1. Вы можете видеть, к чему это идет: следующий размер после этого будет равен нулю. Это приводит к сбою повторного хеширования.
Код для воспроизведения:
for (int i = 0; i < 9; i++)
set.add(i);
for (int i = 0; i < 9; i++)
set.remove(i);
Модификаторы доступа несовместимы
clear
является public
но остальная часть «общедоступного интерфейса» имеет уровень доступа по умолчанию, который может быть нормальным, но тогда почему clear
общественные. Рекомендую выбрать один из них.
Неотрицательный?
В описании сказано, что это набор для неотрицательных целых чисел, но, похоже, он подходит для любых целых чисел.
Слабый хеш (идентификационный хеш)
Идентификационное хеширование (т.е. использование значения в качестве хэш, применяя только сокращение диапазона) для целых чисел в основном работает, но может легко привести к неравномерному распределению некоторых значений по сегментам. Например, если все значения четные (или все нечетные), то используется только половина сегментов. Или, если все значения кратны 256, то можно использовать только 1 из 256 сегментов. Во многих случаях этого просто не произойдет, потому что входные данные хорошо распределены, но набор целых чисел, кратных степени двойки, не является редкостью. Опасность может быть уменьшена (не устранена полностью, но наборы значений, которые вызывают плохое поведение) с участием хеширование — довольно необычные наборы) путем применения некоторого «диффузного» биективного преобразования к значению перед его уменьшением, например (заимствуя «финализатор хеширования» из MurmurHash3):
static int hash(int x) {
x ^= x >>> 16;
x *= 0x85ebca6b;
x ^= x >>> 13;
x *= 0xc2b2ae35;
x ^= x >>> 16;
return x;
}
// elsewhere in the code ...
int targetCollisionChainIndex = hash(integer) & mask;
Конечно, здесь есть компромисс: этот хеш нельзя оценивать бесплатно.
Просто неупорядоченный список вещей, которые пришли мне в голову:
У вас есть два
rehash()
методы, делающие очень разные вещи,int
-возврат одного, вычисляя индекс для целого числа содержимого, а другойvoid
один делает процесс перефразирования.У вас есть (по крайней мере) два места, где вы вычисляете индекс массива для целого числа содержимого, одно из которых находится внутри
add()
метод, другой —int rehash()
метод.Вы заново изобрели колесо. Функционально
HashSet<Integer>
выполняет свою работу, хорошо протестирован и оптимизирован. Возможно, вы сделали свою реализацию из соображений эффективности, но я сомневаюсь, что ваш класс превосходитHashSet<Integer>
относительно времени выполнения или объема памяти. Но если у вас есть данные о производительности, мне было бы любопытно их увидеть.Ваше «хеширование» с использованием битовой маски может привести к ненужным конфликтам в некоторых (весьма вероятных) случаях использования.
Вы используете односвязный список в сегментах. В ваших тестовых примерах для
remove()
Я не нашел явных для крайних случаев: удаление первой записи и удаление последней записи из списка. Случайные тесты могут покрыть это с некоторой вероятностью, но «некоторая вероятность» — плохая идея для тестирования.
Встроенный JDK
HashSet<Integer>
на самом деле довольно плохо оптимизированная реализация. Это не только тратит время и память из-за примитивного (не) бокса, но и фактическиHashMap
маскируется и, таким образом, также тратит впустую пространство для хранения указателей на неиспользуемые значения карты и время для их обновления. Он также довольно склонен к столкновениям, и, хотя он справляется с ними прилично хорошо (по сути, возвращается кTreeMap
), что само по себе добавляет немного сложности и накладных расходов на производительность. Что-то вроде HPPCIntHashSet
было бы гораздо лучшим сравнением.— Илмари Каронен
IntHashTableCollisionChainNode
уже вложен вIntHashSet
, делаяIntHashTable
часть его названия избыточна. Плюс тот факт, что он является частью «цепочки», подразумевается тем, как он используется, на самом деле это не свойство самого класса.Подумайте, возможно, просто
IntHashSet.Node
.IntHashTableCollisionChainNode
может бытьprivate
Вы не указали, какую версию Java используете, но если она выше 10, вам следует использовать
var
для вывода типа по локальным переменным. Это снизит частоту таких вещей, как:final IntHashTableCollisionChainNode newNode = new IntHashTableCollisionChainNode( integer, table[targetCollisionChainIndex]);
Что может просто стать:
final var newNode = new Node(integer, table[targetCollisionChainIndex]);
Маркировка локальных переменных в Java довольно утомительна. ИМО, это много шума без особой отдачи. Взгляните на ключевые слова, используемые для объявления констант и переменных на разных языках:
Language | Constant keyword | Mutable keyword ------------|------------------+----------------- Java | final | <blank> JavaScript | const | let Swift | let | var Rust | let | let mut
Обратите внимание на большую разницу: в других языках объявление константы практически так же просто, как и объявление переменной. В Java это аддитивно и очень утомительно. Учитывая, что Java
final
также не влияет на изменчивость объекта, на который указывает ссылка (он заботится только о неизменности самой ссылки), я думаю, что это довольно низкое значение и не стоит спама, чтобы использовать его для всех локальных переменных.
Хороший, но я не согласен final
: если ничего другого, он документирует, что переменная / ссылка не изменилась в текущем методе.
— кодеродде
Представление
Если принять во внимание скорость (что кажется целью, так как нет никакой системы безопасности, такой как HashSet
есть), я бы сказал, что вы в хорошем состоянии, но некоторые улучшения можно сделать.
- Проверка
contains
Внутриadd
а такжеremoves
делает цикл кода дважды через узлы, когда элемент отсутствует. Подумайте о том, чтобы проверить позже в своемadd
а такжеremove
метод. - Рассмотрите возможность кэширования часто используемых чисел, таких как
table.length * MAXIMUM_LOAD_FACTOR
знак равноnextExpandSize
?).
Читаемость
Мне сложно читать код. Я читал несколько кодов, связанных с производительностью, и они стали более разборчивыми.
- Рассмотрите возможность переименования
IntHashTableCollisionChainNode
чтобы простоNode
. Он выражает то же самое, но намного короче. - Теперь мы близки к Java 17. Просто используйте
var
вместо полного имени типа. - Удалить
final
для локальных переменных. В вашем коде нет абсолютно никакой дополнительной ценности, тем более что в Java теперь есть концепция эффективных конечных переменных. - Рассмотрите возможность слияния
expand
а такжеcontract
вresize
с параметром: код абсолютно идентичен, за исключением нового размера. - ИЛИ рассмотрите возможность слияния
shouldExpand
а такжеexpand
вместе (expandIfNeeded
), а такжеshouldContract
а такжеcontract
(contractIfNeeded
). - Есть магические числа, такие как
4
а также2
. Выразите их как константы, такие какEXPAND_FACTOR
а такжеCONTRACT_FACTOR
.
Тестирование
- В
bruteForceAdd
а такжеbruteForceRemove
тесты не воспроизводятся, потому что начальное число является текущей меткой времени. Если ваша реализация содержит ошибки, у вас может быть тот же тест, который иногда проходит успешно, а иногда — нет. Тесты на воспроизводимость. Так что лучше иметь постоянное семя. - В
bruteForceRemove
еще более проблематично, потому что есть условное удаление. Я бы написал это так:
for (int i = 0; i < 10000; i++) {
data[i] = i;
set.add(i);
}
shuffle(data);
for (var i : data) {
assumeTrue(data.contains(i)); // not assert.
data.remove(i);
assertFalse(data.contains(i));
}
Я не собираюсь тратить время на детали вашей реализации, так как я думаю, что вы лаете не на то дерево.
Если целые числа не используются в качестве ключей для доступа к некоторым другим данным, то, по сути, у вас есть растровое изображение. Создание сложной структуры с объектами вместо узлов кажется неудобным, неэлегантным, занимающим много места и, вероятно, будет плохо работать.
Рассмотрение источника java.util.EnumSet и java.util.JumboEnumSet может быть полезным в качестве примера обработки растрового изображения (фиксированного размера). Немного изобретательности покажет, как можно динамически изменять размер дизайна.
Замечу, что в вашем коде нет синхронизации. Вы собираетесь добавить это, если синхронный доступ будет обеспечиваться пользователем или должна быть доступна оболочка? Если вы заставили свой класс реализовать интерфейс Set <>, тогда можно было бы использовать механизм оболочки SynchronizedSet …