Мой вопрос в значительной степени о том, что выше. Согласно диаграммам, которые я вижу в хэш-таблице, это выглядит, например:Есть ли разница между массивом связанных списков и таблицей хэшей?
Hashtable temp1 = new Hashtable (20);
SList [] temp2 = новый SList [20];
Предполагая, что SList является одиночным списком, не является temp1 почти таким же, как temp2? Я просто пытаюсь понять хэш-таблицы немного лучше. Благодаря!
С помощью хеш-таблицы вы вставляете значение V в таблицу с ключом K. Это K может быть любым, что может быть обработано хеш-функцией.
Вставка в SList[], однако, должна быть выполнена с использованием целочисленного индекса, который является гораздо менее гибким, чем возможность использования любого хэшируемого объекта.
Наряду с этим пунктом существует несколько способов борьбы с коллизиями по ключу в хеш-таблице. Хеширование цепочкой создает что-то похожее на ваш вышеупомянутый список связанных списков, с дополнительным преимуществом индексации хешируемыми объектами вместо int.
См. here под Хэшированием для описания других способов решения столкновений хэшей в хеш-таблице.
Но не является ли значение, возвращаемое функцией hashcode() целым числом? Чтобы он мог быть помещен индексом в ведра, подобно тому, как это делает массив SLists? Но я понимаю, что вы говорите о различных сценариях обработки столкновений, таблица Хэша действительно била массив SLists в этом отношении. – Iche
Подождите, я понимаю, теперь. – Iche
Это правда, вы можете использовать целочисленный индекс, переданный через хеш-функцию, чтобы определить местоположение в таблице, чтобы поместить значение. Единственная разница в этой ситуации заключалась бы в том, что хеш-таблица будет работать хуже, чем массив связанных списков, так как выполнение функции хэширования займет больше времени, чем простая вставка индекса на основе массива. – Oli
Эти два отличные. Хэш-таблица индексируется каким-то объектом, называемым ключом типа с четко определенной операцией, называемой 'hash', определенной на нем. В зависимости от значения хеша пара (Key, Value) сохраняется в соответствующем месте в хеш-таблице. Вообще хеш-функции должны иметь совершенно разные значения для почти одинаковых объектов. Hashtables использует списки, чтобы заботиться о столкновениях - разные ключи могут давать один и тот же хеш - если это так, они сохраняются в одном и том же месте (в соответствующем списке) в этой модели разрешения столкновений. Hashtables может использовать массивы списков внутри. – lared
Я понимаю, что вы имеете в виду, но предположим, что вы определили отдельный класс HashTableImplementation с конструктором, являющимся массивом одиночных связанных списков. Поскольку вы используете одиночные связанные списки, столкновение уже позаботится, и вы можете сортировать значения одного и того же ключа в любом случае. Если вы добавили хэш-метод в HashTableImplementation, а также метод функции сжатия к нему, не могли бы вы иметь то же самое, что и хеш-таблица? – Iche
Да. Но вы могли бы также использовать другой метод разрешения конфликтов, и он был бы еще хэш-таблицей. Что используется внутри - будь то массив связанных списков или просто простой массив, это просто деталь реализации. – lared